?

Log in

No account? Create an account
To the man on trail Below are the 10 most recent journal entries recorded in the "Записки" journal:

[<< Previous 10 entries]

July 18th, 2015
05:52 pm

[Link]

Потрясающий сайт для изучения биоинформатики через решение задач
http://rosalind.info - классный сайт, зарегистрировался ещё месяц назад, в прошлую субботу часа три решал задачи. Прекрасно подойдёт как желающим изучить биоинформатику, так и тем, кто соскучился по решению алгоритмических задач. Есть рейтинг участников, за достижения даются значки и ачивки!

(Leave a comment)

November 28th, 2013
08:17 pm

[Link]

Алгоритмы, пятая неделя - "Красно-чёрные деревья"
Речь о совершенно для меня структурах данных пошла на пятой неделе. Детали реализации некоторых структур и алгоритмов (а уж тем более оценки их эффективности), конечно же, не были мне ранее знакомы, но всё-таки я знал, что такое стеки, очереди, алгоритмы сортировки, деревья поиска и т.д.

На пятой неделе было продолжение темы добавления/поиска/удаления элементов в символьных таблицах, или ассоциативных массивах. Последовательно изучили способы представления и эффективности таких структур: представление в обычном массиве (неупорядоченном), представление в отсортированном массиве, представление в виде двоичного дерева. Попутно был разобран алгоритм сортировки Heapsort - сортировка деревом.

Так вот, на пятой неделе был изучен гораздо более приемлемый с точки зрения эффективности способ хранения данных. Он называется "красно-чёрные деревья", но перед его разбором была разобрана его абстракция - "2-3 деревья". Обе структуры ведут себя совершенно одинаково и имеют эффективность заметно выше, чем предыдущие разобранные случаи.

Идея 2-3 деревьев состоит в том, чтобы делать узлы в деревьях не с двумя потомками, а с тремя. Таким образом, получается два вида узлов: узлы, у которых 2 потомка (2-узлы) и узлы, у которых 3 потомка (3-узлы). Если у узла два потомка (2-узел), то потомок слева имеет значение меньше, чем в самом узле, а потомок справа имеет значение больше, чем в самом узле. Если у узла три потомка (3-узел), то, во-первых, в самом узле будут два значения, а не одно, а во-вторых, вводится ещё "средний" потомок, значение (или значения, если это тоже 3-узел) которого находится между значениями узла-родителя. Делается это для тго, чтобы любой путь от корня дерева до нулевого узла (это узел, в котором не содержится ни одного значения) всегда имел одну и ту же длину. Кроме того, подобная структура позволит возвращать значения в упорядоченном виде.

Поиск элемента в 2-3 дереве происходит очень просто: элемент поиска сравнивается с очередным узлом, если значение не найдено, то поиск рекурсивным образом переходит к следующему узлу, в зависимости от того, больше элемент значений в узле, меньше или находится между ними (если это 3-узел).

Добавление элемента: если это 2-узел (имеет не более двух потомков), то добавление происходит так же, как в случае обычных двоичных деревьев. Немного интереснее происходит процесс добавления элемента в 3-узел. Итак, для этого создаётся временный 4-узел - содержит 3 элемента (стоит напомнить, что в этой реализации может быть максимум 2 элемента в узле, поэтому 4-узел и называется временным). Далее средний элемент 4-узла перемещается "вверх" по дереву - в узел-предок. Эта процедура продолжается рекурсивно по мере необходимости. Если процедура достигает корня дерева, и оно тоже оказывается временным 4-узлом, то оно делится на три 2-узла, причём средний узел становится корнем дерева, а другие два элемена - его потомками.

Стоит заметить несколько важных вещей: во-первых, разбиение 4-узла является локальной операцией, то есть касается очень ограниченного числа элементов и выполняется за константное количество операций. Во-вторых, эта реализация сохраняет симметричность дерева и его сбалансированность: все пути от нулевых узлов до корня равны. Таким образом, эта реализация в любом случае поддерживает логарифмическую эффективность - в худшем случае это будет логарифм по основанию два (если в дереве только 2-узлы), в лучшем случае это логарифм по основанию три (все 3-узлы).

Но явная реализация этого алгоритма довольно неудобна, поэтому были придуманы красно-чёрные деревья. Идея состоит в том, чтобы ввести "красные" и "чёрные" связи между узлами: "красные" ветви будут соединять узлы со значениями, которые находились бы в одном узле в реализации 2-3 деревьев, "чёрные" ветви будут соединять все остальные узлы. Выводы: во-первых, ни один узел не будет обладать двумя "красными" ветвями, во-вторых, аналогично 2-3 деревьям, все пути от нулевых узлов до корня дерева равны, в-третьих, "красные" узлы будут указывать налево от себя.

Теперь о выполнении некоторых элементарных операций. Поиск будет выполняться аналогично обычным двоичным деревьям поиска (цвет ветви, будь она красной или чёрной, можно игнорировать). Немного посложнее дело обстоит с добавлением элемента в дерево. Для каждого узла вводится булевая переменная, определяющая, является ли ветвь, выходящая из него, "красной". Теперь введём в рассмотрение несколько элементарных операций над КЧ-деревьями, которые потребуется выполнять. Первый сценарий: красная ветвь указывает не влево, а вправо, то есть нужно осуществить переориентацию дерева. Я регулярно забывал идею этого сценария, поэтому остановлюсь на нём подробнее. Итак, что здесь происходит: красная ветвь дерева должна указывать на узел с меньшим значением, а у нас оказалось, что он указывает на узел с большим значением. Чтобы устранить эту ошибку, создадим новый узел, равный тому узлу, на который указывает красная ветвь. Затем присвоим правому узлу, из которого исходит красная ветвь, левый узел нового узла, а левому узлу нашего нового узла присвоим тот узел, из которого изначально исходила красная ветвь, но теперь уже направим красную ветвь из нового узла на его левый узел. После этого порядок будет восстановлен.

Иногда может потребоваться заставлять красную ветвь указывать направо, то есть на больший узел-потомок. В этом случае всё делается совершенно аналогично предыдущему пункту, но все операции производятся с точностью до наоборот.

Перемена цветов - может случиться, что из одного узла будут исходит две красные ветви. Для устранения этого недостатка надо просто сделать их обе чёрными, а вот ветвь, указывающую на этот узел - красной.

Будучи вооружёнными этими тремя базовыми операциями, можно реализовать операцию добавления нового элемента. В первом варианте (добавление элемента в 2-узел) понадобится сценарий переориентации красной ветви справа налево.

Второй вариант: пусть требуется добавить в 3-узел. В этом случае требуется проделать обычную процедуру добавления в 3-узел и пометить ветвь, указывающую на новый узел, красным цветом. Далее нужно сбалансировать узел, если он оказался 4-узлом и переменить цвета, если из узла выходили две красные ветви и если красная ветвь указывала направо, то осуществить переориентацию.

В этом вся суть идеи этой структуры данных. Повторюсь, что её изящество в том, что любая операция осуществляется за логарифмическое время. Кроме того, она позволяет вернуть элементы в упорядоченном виде с помощью рекурсивного перебора по узлам.

(Leave a comment)

November 24th, 2013
12:00 pm

[Link]

Алгоритмы, четвертая неделя
Часть 1: Приоритетные списки

Четвёртая неделя курса началась с изучения новых структур данных. Впервые речь о составных структурах данных зашла на второй неделе, когда изучались стеки и очереди. На четвёртой неделе изучалось нечто похожее идейно - приоритетные списки (не думаю, что перевёл грамотно, вообще говорят "Priority queues").
Как происходило удаление в предыдущих изученных типах данных? В стеках удалялся последний добавленный элемент, в очередях - первый, в рандомизированных очередях удалялся произвольный элемент. Потребность в приоритетных списках возникает, когда требуется удалять максимальные (или минимальные) элементы.
Скажем, может потребоваться искать M наибольших элементов в потоке из N объектов. Сортировка позволяет осуществлять это за линеарифмичное время, примитивный приоритетный список - за время порядка MN, двоичное дерево - за время NlogM. О двух последних способах речь пойдёт дальше.
Самый простой способ - держать элементы в неупорядоченном массиве. Тогда внесение нового элемента будет происходить мгновенно, но извлечение будет затруднительно - известно, что поиск максимального элемента в массиве пропорционально его размеру. Если это делать M раз, то как раз и получится MN. Упорядоченные массивы немного лучше - максимальный элемент находится мгновенно (всегда в конце или начале массива), но внесение нового элемента занимает довольно много времени - пропорционально размеру массива.
Хорошим способом является двоичное дерево, подчиняющееся простым принципам: индексирование начиначется с 1, а не с 0, объекты находятся в узлах, объект "родительского" узла не может быть меньше объектов, находящихся в узлах-потомках. В таком способе представления не требуется прописывать никаких дополнительных связей между узлами - потомками узла с индексом k являются узлы с индексами 2k и 2k + 1, предком узла с индексом k является, соответственно, узел с индексом k/2.
Как происходит построение такого двоичного дерева? Сценарий 1: объект-потомок становится больше объекта-предска. Чтобы избежать этого, надо всего лишь последовательно обменивать этот объект с объектами, значение которых меньше его, находящимися выше по дереву. Таким образом, больший объект как бы "всплывает" в направлении дерева до тех пор, пока не окажется меньше или равен объекту, находящемуся в узле-предке. Этот базовый сценарий используется при добавлении новых объектов в дерево: очередной объект добавляется в самый конец, после этого "всплывает" вверх. Сценарий 2: объект-предок становится меньше, чем один (или оба) его потомка. Для восстановления равновесия следует объект обменять с большим из его потомком и продолжать это, пока баланс не будет восстановлен. Иначе говоря, узел, нарушающий баланс дерева, "тонет" в направлении, обратном от корня дерева, до тех пор, пока равновесие не будет восстановлено.
Каково быстродействие такой структуры? Чтобы удалить максимальный элемет, нужно обменять значение корня дерева с последним элементом, затем "утопить" новый корень, то есть обменивать его с потомками, если его значение окажется меньше. В худшем случае эта операция потребует 2lgN сравнений. Чтобы добавить новый элемент, следует добавить его в конец дерева, а затем поднимать его вверх, то есть обменивать его значение с предком, если оно больше. Эта операция тоже пропорциональна логарифму от количества элементов.
Описанное двоичное дерево может быть легко использовано для сортировки массивов (к слову, именно этот способ я использовал для оптимизации одной из программ, доставшихся мне в наследство). Идея алгоритма сортировки деревом ("Heapsort" на английском) состоит в двух пунктах:
- Создать дерево из всех элементов массива
- Последовательно удалять максимальный элемент, записывая его в конец массива.

Какова эффективность такой сортировки? Создание дерева требует порядка 2N сравнений и перемещений, сортировка заниает меньше 2NlgN сравнений и перемещений. Этот алгоритм примечателен тем, что в любом случае его сложность не превышает ~NlgN и он не использует дополнительного места в памяти компьютера.

Часть 2: Таблицы символов

Таблицы символов являются обобщением идеи массивов. Массив позволяет установить связь индекса (натурального числа) с целым объектом, таблицы символы устанавливают связи между двумя объектами. Эта идея должна служить двум базовым целям: добавление нового объекта с заданным ключом и поиск объекта по заданному ключу. Пара "ключ - значение" и является обобщение идеи массива: заданное значение (объект) ищется по ключу.
Кроме добавления и поиска возможны и другие функции этой структуры данных, а именно: удаление значения, проверка, содержит ли таблица значение для заданного ключа, проверка таблица на пустоту, размер таблицы и итератор для всех ключей в таблице.
Если значения таблицы символов могут быть объектами любого типа и любой природы, то ключи таблицы должны поддаваться сравнению, аналогично целочисленным индексам массива - для того, чтобы поиск по таблице был вообще возможен.
Первый вариант реализации - динамически связанный список (стек), содержащий в качестве полей ключи и сами объекты. Поиск заданного ключа осуществляется простым перебором до тех пор, пока будет найдено нужное значение; добавление нового ключа осуществляется тоже перебором: если ключ найден, то обновляется его значение, если ключа нет, то добавляется новый элемент в начало списка. Оценка эффективности показывает, что добавление нового элемента в этой реализации в любом случае будет занимать линейное время, поиск в худшем случае будет пропорционален количеству элементов, в среднем случае - половине количества (N/2). Упорядоченной итерации по всем элементам эта реализация не осуществляет.
Второй вариант - упорядоченный массив пар "ключ-значение". Поиск в такой структуре осуществляется двоичным перебором и время этой операции логарифмично в худшем случае, а вот с добавлением нового ключа возникают проблемы: для этого придётся сдвигать все большие ключи, что является довольно дорогой операцией.
Список функций, которые также полезно иметь в этой структуре данных:
- определение ключа минимального/максимального элемента;
- определение наибольшего ключа, который меньше или равен заданному ключу;
- определение наименьшего ключа, который больше или равен заданному ключу;
- определение количества ключей, которые меньше/больше заданного ключа;
- выборка ключей заданного ранга;
- количество ключей, находящихся в заданном интервале;
- итерация по ключам в заданном интервале.
Эффективность почти всех этих функций в случае первой реализации (связанный список) линейна, кроме упорядоченной итерации - её порядок составляет NlogN (сортировка). В случае второй реализации (упорядоченный массив) ситуация поинтереснее: добавление/удаление и упорядоченная итерация линейны, функции поиска, ранга и т.д. логарифмичны, поиск максимального и выбор ключа заданного ранга выполняются моментально.
Казалось бы, реализация с помощью упорядоченного массива довольно эффективна, но то, что одни из самых часто используемых функций (добавление/удаление) выполняются за линейное время, не может устраивать. Существуют более подходящие реализации, которые были рассмотрены в следующих лекциях.

(Leave a comment)

November 16th, 2013
05:00 pm

[Link]

Алгоритмы, третья неделя - "Быстрая сортировка"
Вторая тема третьей недели - алгоритм так называемой "быстрой сортировки". Я написал "так называемой" потому что, вообще говоря, этот алгоритм (лично мое мнение) не является самой быстрой сортировкой. Самой быстрой сортировкой мне кажется сортировка деревом, которая по-английски называется "Heapsort" (о ней речь пойдёт дальше).

Алгоритм быстрой сортировки (Quicksort) был придуман Чарльзом Хоаром, за что в 1980 году ему была вручена Премия Тьюринга. В общих словах идея алгоритма описывается следующими пунктами:
1. Перемешать исходный массив
2. Разделить его на две части следующим образом: некоторый элемент находится на "своём" месте (то есть, на котором он находился бы в отсортированном массиве); элементы меньше него находятся слева от него, элементы больше - справа от него.
3. Рекурсивно повторять пункт 2 для каждой из двух частей массива (правой и левой).

Элемент, который оказывается на "своем" месте, называют "разделяющим элементом" и обычно для этого берут элемент, который в данный момент находится в начале сортируемого массива.

Разделение массива на две части происходит несложным образом:
 - элементы сканируются слева направо до тех пор, пока не будет найден элемент больше разделяющего элемента (пусть его индекс будет i)
 - элементы сканируются справа налево до тех пор, пока не будет найден элемент меньше разделяющего элемента (пусть его индекс будет j)
 - элементы с индексами i и j меняются местами, а процесс продолжается до тех пор, пока точки сканирования не пересекутся на каком-либо элементе; как только они пересекаются, следуем обменять разделяющий элемент с точкой пересечения.

Перемешивание исходного массива делается на всякий случай: дело в том, что в худшем случае производительность этого алгоритма квадратична (это если массив уже отсортирован, как это ни парадоксально). Перемешивание производится для того, чтобы исключить этот случай и добиться высокой производительности. В общем случае алгоритм линеарифмичен.

(Leave a comment)

November 13th, 2013
10:00 pm

[Link]

Алгоритмы, третья неделя - "Сортировка слиянием"
На третьей неделе речь пошла о двух известных алгоритмах сортировки - сортировка слиянием (mergesort) и быстрая сортировка (quicksort). В этом посте речь пойдёт о первом из них.

Суть сортировки слиянием заключается в следующем: разбить сортируемый массив на две половины, рекурсивно отсортировать каждую из частей, объединить две половины. Рекурсивная сортировка означает, что каждую из половин тоже нужно разделить на две части, каждую из которых надо отсортировать таким же образом и т.д. Буквально, это означает, что сначала сортируются фрагменты по 2 элемента, которые затем объединяются во фрагменты по 4 элемента, по 8 и т.д., пока не объединятся две части исходного массива (то есть пока не получится отсортированный массив).

Объединение двух отсортированных массивов довольно просто описывается в двух словах. Первым элементом нового массива становится минимальных из первых элементов исходных массивов, счётчик того массива, откуда берётся минимальный элемент, сдвигается на 1 вправо, на второе место нового массива вновь становится минимальный из исходных массивов (не забываем, что счётчик у одного из них сдвинут) и т.д. Алгоритм довольно прост, но зато требует введения дополнительного массива.

Оценка времени работы: сортировка слиянием линеарифмична (то есть порядка NlgN). Эта оценка верна для любого случая, будь то отсортированный массив, отсортированный по убыванию и т.д.

Другой вид этого алгоритма - начинать "сверху вниз", то есть изначально сортировать массивы размера 2, 4, и т.д. Эта версия не является рекурсивной, но по-прежнему требует введения дополнительного массива.

Другие темы, затронутые в этой лекции: доказательство того, что не существующих алгоритмов, гарантирующих скорость сортировки быстрее, чем NlgN, объяснение сути интерфейса Comparator (это когда одни и те же данные можно сортировать по различным признакам), о принципе стабильности - это когда сортировка не нарушает порядка одинаковых элементов относительно друг друга. Так, Insertion и Mergesort являются стабильными, в то время как Selection и Shellsort - нет.

(Leave a comment)

November 9th, 2013
10:00 pm

[Link]

Алгоритмы, вторая неделя - "Введение в сортировку"
В этой лекции проходили введение в сортировку, три простых алгоритма сортировки и пример применения алгоритма сортировки.

Постановка задачи сортировки проста: отсортировать массив некоторых объектов в порядке возрастания или убывания. Обычно изучается на примере чисел, но в этом курсе сразу было сказано, что объекты могут быть любой природы (даты, строки, файлы и т.д.). Чтобы можно было сравнить два объекта друг с другом, у них должен присутствовать интерфейс Comparator, в котором должна быть реализована функция compare, сравнивающая два объекта. Эта функция возвращает 1, если первый объект больше, -1, если больше второй объект и 0, если они равны. Вроде это всё из того, что было для меня в новинку. Я так понял, что интерфейс Comparator - это фишка Java, было сказано, что в C/C++ это реализуется с помощью указателей (ну ещё бы), в C# - с помощью делегатов. Вот насчёт последнего не совсем понял, потому что в C# тоже есть интерфейсы и почему бы не сделать, как в Java?

Selection sort (не помню точного названия по-русски, поэтому переводить не буду) - один из простейших алгоритмов. Инвариант состоит в том, чтобы на i-й итерации найти индекс минимального элемента от i до конца массива и поменять его (элемент, конечно же, а не индекс) с i-м элементом. Таким образом, на каждом шаге все элементы слева от текущего будут отсортированы и приведены в конечный вид, а справа - пока нет, на предпоследнем шаге массив будет отсортирован полностью. Алгоритм очень простой и наверное, самый очевидный для тех, кто впервые задумывается о реализации сортировки (по крайней мере я, когда писал небольшие программы, где была нужна сортировка, всегда писал его - у меня на это уходит минуты 3). Но самое простое не всегда означает самое лучшее, поэтому нужно обратиться к анализу этого алгоритма. И тут становится видно, что он использует число сравнений порядка квадрата от общего количества элементов в массиве, причём даже в том случае, когда массив отсортирован.

Insertion sort (вроде называется "сортировка вставками" по-русски) - тоже один из простейших алгоритмов. Инвариант состоит в том, чтобы на каждом шаге перемещать текущий элемент влево, пока там встречаются элементы больше него. Таким образом, на каждом шаге все массива слева будут отсортированы (но необязательно в конечном виде), справа - пока нет и более того, массив справа останется в неизменном виде. Анализ этого алгоритма говорит о том, что для произвольного массива с достаточно большим количеством различных элементов количество сравнений и перемещений будет пропорционально квадрату количества элементов (это так называемый "средний случай"). В лучшем случае (массив уже отсортирован, что редкость) количество сравнений будет пропорционально количеству элементов, количество перемещений - 0, в худшем случае (массив отсортирован по убыванию) количество и сравнений и перемещений будет пропорционально квадрату общего количества элементов. Этот вид сортировки будет также линейным (и по сравнениям и перемещениям) в том случае, когда массив частично отсортирован (массив частично отсортирован, если количество пар, нарушающих порядок, пропорционально размеру массива), что, пожалуй, полезно, если знать, что данные, которые нужно сортировать, всегда будут частично отсортированы - это случается редко, но всё же случается.

Shellsort - идея в том, чтобы применять Insertion sort к отдельным фрагментам исходного массива: фрагмент, состоящий из каждого 13-го элемента, фрагмент, состоящий из каждого 4-го элемента и, наконец, весь массив. Идея этого алгоритма в том, что для небольших фрагментов сортировка будет занимать немного времени, а когда дойдёт дело до маленьких фрагментов, то массив будет частично отсортирован и, следовательно, их сортировка будет происходить очень быстро. Анализ роста - порядка 1.5 от общего количества элементов в худшем случае, если использовать фактор 3х + 1 (то есть фрагменты 1, 4, 13, 16, 19 и т.д.).

В качестве применения была рассмотрена задача минимальной выпуклой оболочки. Постановка звучит так: пусть на плоскости имеется набор точек, как найти минимальную выпуклую оболочку, которая "захватывала" бы эти точки? (вот статья на Википедии: http://ru.wikipedia.org/wiki/Выпуклая_оболочка) Для решения этой задачи в лекции был предложен алгоритм Graham scan: выбрать точку, отсортировать оставшиеся точки по увеличению угла, который они составляют с данной точкой, проложить путь через те точки, которые составляют минимальный угол, перейти к следующей точке и т.д. В общем, звучит несложно, если понимать все детали.

В качестве проекта было предложено реализовать два типа данных: так называемый Deque и Randomized queue. Deque - это обобщение стека и очереди, в котором нужно было реализовать возможность удаления/добавления первого и последнего элементов. Randomized queue - тоже в некотором роде аналог стека или очереди с той разницей, что нужно было реализовать возможность извлечения или удаления произвольного элемента и итерацию по всем элементам в произвольном порядке.

(Leave a comment)

November 6th, 2013
10:00 pm

[Link]

Алгоритмы, вторая неделя - "Стеки и очереди"
К сожалению, в последнее время мало было возможности писать, да ещё и компьютер домашний сломался, но постараюсь всё же дописать эту серию постов. Сегодня речь пойдёт о стеках, очередях, коллекциях и о том, как это реализуется.

Впервые с этой темой я познакомился во втором семестре первого курса на практикумах по программированию. Препод у нас был хороший, готовил хорошие материалы, беда только в том, что он был нетребовательный, иначе говоря, программирование у нас считался халявным предметом. Первый семестр я занимался очень хорошо и наверное, это способствовало тому, что одним из немногих своих одногруппников я до сих пор этим интересуюсь и регулярно программирую. А вот во втором семестре начал расслабляться и я и поэтому тема про стеки и подобные им алгоритмические конструкции как-то прошла мимо меня...

Что из себя представляет стек? Стек - это один из способов хранения группы объектов одного типа. Один из способов его представления - через связанный список. В этом случае стек представляет из себя структуру или класс, одним из полей которого является ссылка на объект этого же типа. Таким образом, первый объект содержит ссылку на второй, второй - на третий, третий - на четвёртый и т.д. Стек поддерживает несколько операций: 1) добавление нового элемента; 2) удаление элемента; 3) проверка на пустоту. Получить произвольный элемент из стека невозможно - для этого нужно итерировать по всем элементам (речь об этом пойдёт дальше). Стек подчиняется принципу LIFO - "last in, first out", что означает, что удаляемый (извлекаемый) из стека элемент является в нём самым новым (наиболее недавно добавленным). Например, если в стек поочерёдно добавлять числа 1, 2, 3, 4, 5, а потом 5 раз вызвать операцию извлечения (удаления), то порядок будет обратным : 5, 4, 3, 2, 1.

Другой способ реализации стека - через массив. Это довольно простой способ: надо всего лишь добавлять новые элементы в конец массива, извлекать элементы из конца массива и при необходимости менять размер массива. Но как менять размер массива? Если менять его после каждой операции добавления/извлечения, то это будет довольно затратно по отношению к времени выполнения - каждый раз при создании нового массива нужно будет постоянно копировать элементы туда-сюда. Оценка показывает, что затраченное время будет пропорционально количеству элементов в стеке во второй степени, что, как известно, плохо (кажется, я уже писал, что квадратичная сложность - это плохо). Был найден довольно изящный способ избежать этого: если добавляемый элемент оказывается в конце массива, то следует создать новый массив размером в два раза больше старого; если же после удаления очередного элемента количество элементов в массиве составляет одну четверть от его размера, то массив следует уменьшить в два раза. Это решение хорошо тем, что время, потраченное на последовательность добавлений/извлечений некоторого количества элементов, будет пропорционально этому количеству в первой степени.

Отличие очередей от стеков заключается только в том, что операция извлечения применяется к элементу, который был добавлен самым первым. Например, если в очередь добавлять числа 1, 2, 3, 4, 5, а потом 5 раз применить операцию извлечения, то порядок останется таким же: 1, 2, 3, 4, 5. Реализация с помощью связанного списка отличается только тем, что надо хранить ещё и ссылку на последний элемент в очереди - это сложнее, но ненамного. Реализация с помощью массива тоже имеет некоторые отличия, но не очень существенные.

Для получения произвольного элемента из стека/очереди нужно реализовать поддержку итераций. На языке Java это делается с помощью реализации интерфейса Iterable. В этом интерфейсе нужно реализовать две функции: hasNext и Next. Первая из них проверяет, есть ли ещё объекты после данного, вторая просто возвращает следующий (ненулевой) объект.

О применении - стеки и очереди применяются при создании списков и коллекций во многих стандартных библиотеках. Списки - очень удобная вещь, я люблю ими пользоваться и прежде даже злоупотреблял их использованием (в этой лекции рассказывалось, что они работают медленнее, чем обычные массивы), но благодаря этой лекции понял, что делать это нужно избирательно, хотя и до этого подозрения об их "медленности" у меня уже были.

Другие известные применения - разработка компиляторов, распознавание арифметических выражений (правильное определение порядков операций и операндов), вычисление рекурсивных функций и т.д.

(Leave a comment)

October 24th, 2013
07:00 pm

[Link]

Алгоритмы, первая неделя - "Анализ алгоритмов"
Продолжаю записывать краткое резюме прослушанного курса "Алгоритмы". Сегодня речь пойдёт о второй части первой недели - "Анализе алгоритмов".
Анализ алгоритмов нужен для следующих задач:
1. Оценка производительности
2. Сравнение алгоритмов
3. Обеспечение гарантии работы
4. Понимание теоретических основ
Первые три задачи рассматривались в этом курсе, последнюю лучше изучать более подробно в рамках курса "Теория алгоритмов".
Для анализа алгоритмов принято использовать научный метод, а именно:
- изучить некоторую особенность объекта
- предложить модель, которая подходит под проведённые наблюдения
- предсказать поведение объекта используя выдвинутую модель
- проверить истинность предсказаний путём дальнейших наблюдений
- повторять эти шаги до тех пор, пока гипотеза и наблюдения не совпадут.
Описанные шаги подразумевают, что эксперименты должны быть повторяемыми, а модель - фальсифицируема (вот этот принцип я не совсем понял).
1. Наблюдения

Эта часть касается эмпирического анализа изучаемого алгоритма. А именно, это означает, что надо запускать алгоритм на различных входных данных и измерять время его выполнения. Затем следует построить полученные данные на декартовой оси, соединить их плавной кривой (или прямой, если повезёт) и попытаться продолжить эту кривую, чтобы предсказать поведение времени выполнения программы для других входных данных. Но чаще используется построение кривых в логарифмических координатах, так как это лучше помогает определить угол наклона и степень роста графика. Этот метод обладает эффектами, как зависящими, так и не зависящими от компьютера, на котором выполняется программа. К зависимым эффектам относятся, разумеется железо, софт, на котором работает компьютер и то, насколько компьютер загружен в момент выполнения программы. К эффектам, не зависящим от системы, относятся только сам алгоритм и входные данные. К минусам метода можно отнести сложность получения точных оценок, к плюсам - то, что этот способ относительно прост.

2. Математические модели оценок времени выполнения

Общее время выполнения программы вычисляется как сумма всех произведений выполняемых в программе операций на время их выполнения. Что требуется для проведения подобного анализа? Это требует, во-первых, полного анализа всей программы для определения всех выполняемых операций, во-вторых, оценки времени выполнения каждой из операций (которое, конечно же, отличается для разных компьютеров), в-третьих, оценки эффективности самого алгоритма в зависимости от рода входных данных. Например, элементарные операции, такие как сложение, умножение, сравнение чисел и т.д. требуют ничтожно мало времени, но что более важно, это время постоянно. Операция выделения памяти под массив длины N тоже занимает мало времени, но в этом случае время уже зависит от числа N, то есть длины массива. Понятно, что оценивать время выполнения константных (то есть занимающих постоянное время) операций неинтересно, поэтому всегда делается анализ тех операций, которые зависят от размеров входных данных (количество элементов в массиве, стеке и т.д.). Например, однократное выполнение одиночного цикла со счётчиком от 1 до N с 10 внутренними операциями занимает 10*N условного времени (условным я называю время, которое разное для разных компьютеров), а вот такого цикла со вложенным циклом с таким же количеством итераций будет занимать уже 10*N^2 условного времени. Если же счётчик внешнего цикла не увеличивается на единицу во время каждой итерации, а например увеличивается в два раза, то выполнение его будет занимать уже 10*N*logN условного времени. (Сейчас я привёл примеры линейной, квадратичной и линеарифмической сложностей выполнения алгоритма.)

В моделях оценок очень важно понятие эквивалентности алгоритмов. Это значит, что когда у нас есть оценка времени выполнения алгоритма, представляющая собой сумму из нескольких слагаемых, то мы можем рассматривать только то из них, которое растёт наиболее быстро. Например, при оценке 3*N^2 + NlogN + N мы можем учитывать только член 3*N^2, так как для больших N он растёт намного быстрее других (а маленькие N нас в анализе обычно не интересуют). Это значительно упрощает задачу анализа алгоритмов, так как часто можно сразу заметить ту часть алгоритма, которая требует больше всего времени (например, три вложенных массива с одним и тем же количеством итераций дают сложность порядка 3*N^3, а всем остальным можно пренебречь).

Основные функции, используемые для классификации: 1 (константа), logN, N, NlogN, N^2, N^3, 2^N.

3. Понятия лучшего, худшего и типичного случаев

Лучший случай: нижняя оценка эффективности алгоритма. Она определяется "простейшим" набором входных данных и представляет собой тот случай, к которому следует стремиться при всех остальных наборах входных данных.

Худший случай: верхняя оценка эффективности алгоритма. Она, напротив, определяется "сложнейшим" набором входных данных и указывает на то, что все остальные случаи будут гарантированно выполняться быстрее.

Типичный случай: оценка, которую мы ожидаем получить для произвольного набора входных данных. Эта оценка нуждается в разработке модели, определяющей случайный набор данных и позволяет оценить производительность алгоритма.

Для всех этих оценок существуют специальные обозначения. Так называемая оценка "большое Тета" (Theta-notation, Тета-нотация) служит для классификации алгоритмов в принципе и позволяет оценивать асимптотику роста работы алгоритма (то есть служит для оценки типичных случаев). Оценка "большое О" (Big-Oh notation) служит для разработки верхних оценок выполнения алгоритмов (то есть худших случаев). Оценка "большое Омега" (Big Omega) служит для разработки нижних оценок (то есть лучших случаев).

4. Используемая память

Также в курсе изучались способы измерения памяти, используемой алгоритмом. Это было довольно интересно и ново для меня, потому что никогда до этого я этим не занимался. И всё же писать я про это не буду, так как в основном материал представлен примерами, перепечатывать которые будет несколько долго и утомительно. Вкратце скажу, что это действительно дало мне новейшее понимание принципиальных вещей, ну и многое я стал после этого понимать лучше. В каждом из проектов, которые нужно было выполнять по ходу курса, были тесты на память, то есть программа должна была использовать строго не больше определённого количества ресурсов компьютера. Но на самом деле для того, чтобы пройти эти тесты, на мой взгляд, требовался лишь здравый смысл и те знания, которые были у меня до этого, так что в этом плане этот материал не очень-то помог - все тесты на память я вроде прошёл во всех проектах. Но тем не менее, это была одна из самых интересных и познавательных частей курса.

Уже после окончания курса на Хабре появился перевод статьи (в 4-х частях) про анализ алгоритмов. Возможно, я написал о своих впечатлениях от курса немного сумбурно и в основном про то, что интересно мне, а вот эта статья довольно хорошо описывает эту тему (и даже с картинками!).

http://discrete.gr/complexity/ - оригинал

Первая часть на хабре - http://habrahabr.ru/post/196560/
Вторая часть - http://habrahabr.ru/post/195482/
Третья часть - http://habrahabr.ru/post/195996/
Четвёртая часть - http://habrahabr.ru/post/196226/

(Leave a comment)

October 15th, 2013
10:00 pm

[Link]

Алгоритмы, первая неделя - "Объединения и поиск"
Первая неделя курса "Алгоритмы, часть 1" была посвящена задачам объединения множеств (с возможностью поиска элементов) и, собственно, введению в анализ алгоритмов (я написал "введение", потому что тема эта очень большая и гораздо более подробно рассматривается в других курсах - например "Анализ алгоритмов" тех же авторов).

Итак, что такое объединение множеств с возможностью поиска? Допустим, у нас есть конечный набор неких элементов, которые мы хотим иногда объединять в группы (одну или несколько), иногда проверяя, принадлежит ли какой-либо элемент данной группе. Например, есть набор чисел от 0 до 9. Примерами групп могут являться 2 множества {0, 1, 2, 3, 5, 7} и {3, 4, 8, 9}. Элементы первого множества не содержатся во втором, элементы второго - в первом. Если эти два множества объединить, то, естественно, все элементы будут содержаться в одном "общем" объединении. Понятие объединения является отношением эквивалентности: а) отдельно взятый элемент объединён с самим собой; б) если элемент "x" объединён с элементом "y", то "y" тоже объединён с "x" и наоборот - если "x" не объединён с "y", то "y" не объединён с "x"; в) если "x" объединён с "y", а "y" объединён с "z", то "x" объединён с "z". Ничего сложного, самое интересное заключается в деталях реализации - причём как операции объединения, так и операции поиска.

Если есть набор каких-то объектов, над которыми надлежит проводить эти операции (природа объектов не важна), становится естественным их пронумеровать и работать уже с массивом. Тогда операции объединения и поиска сведутся к операциям над целыми числами - индексами массивов. Собственно, все примеры в курсе были связаны просто с массивами целых чисел.

Первый подход, называемый также "быстрым поиском" (quick-find), состоит в том, чтобы каждому объекту ставить в соответствие идентификатор. Если требуется объединить один объект с другим (или одну группу с другой), надо присвоить идентификатору первого объекта значение идентификатора второго объекта (если объединяются две группы, то количество присваиваний будет намного больше). Таким образом, любые два объекта (группы) объединены, если их идентификаторы равны и наоборот. Чтобы узнать, находятся ли объекты "x" и "y" в одной группе, надо просто сравнить значения их идентификаторов.

Большим преимуществом этого подхода является очень высокая скорость операции поиска (то есть выяснения, состоят ли два объекта в одной группе) - всего одна операция сравнения. Большим недостатком в данном случае является операция объединения - например, N вызовов операции объединения на группе из N объектов потребует N ^ 2 обращений к элементам массива. Это называется квадратичной сложностью и вообще это очень нежелательное явление, с которым можно столкнуться при составлении алгоритмов по причине того, что время выполнения программ с такой сложностью растёт очень быстро с увеличением N. Существуют алгоритмы, в которых без квадратичной сложности не обойтись - например, умножение матриц, но если есть возможность, этого следует избегать.

Другой подход, именуемый "быстрым объединением" (quick-union), тоже предполагает хранение идентификаторов для каждого объекта, но теперь в качестве идентификатора должен служить индекс объекта, являющегося "корневым" для данного объекта. Согласно этому подходу, каждую группу, состоящую из отдельных элементов, можно представить в виде дерева с одним корнем, все потомки которого будут иметь идентификаторы, равные индексу корня.

Для объединения групп по этому методу надо всего лишь присвоить идентификатору первой группы значение идентификатора второй, образно говоря - объединить деревья. Для выяснения, принадлежать ли два элемента одной группе, надо просто сравнить значения идентификаторов соответствующих корней. Улучшением этого способа является также хранение размеров "деревьев", представляющих собой группы объединений. Тогда при операции объединения надо учитывать размеры соответствующих "деревьев" объединяемых групп - присваивать значение "корня" другого "дерева" тому "дереву", которое на данный момент "ниже", то есть имеет меньше элементов. Это позволит избежать появления длинных "ветвей" - то есть "деревья" будут более "раскидистыми", что будет плюсом при выполнении операции поиска в таком дереве.

В качестве практического применения полученных знаний было предложено реализовать одну довольно интересную задачу. Имеется квадратная пластинка, разбитая на ячейки. Ячейки могут быть полными или пустыми. Пластинка называется проводящей, если можно проложить путь сверху вниз по полным ячейкам. Эта задача называется "перколяцией" (percolation - просачивание, фильтрация, проникновение) и встречается, собственно, при моделировании процессов фильтрации жидкости или моделировании проводимостей каких-либо материалов. Если путь в пластинке сверху вниз существует, то пластинка называется проводящей. Задача состоит в том, чтобы эмпирически (методом Монте-Карло) определить среднее количество полных ячеек, которое требуется для того, чтобы пластинка была проводящей. Делается это следующий образом: берётся пластинка, состоящая изначально исключительно из пустых ячеек. Затем ячейки поочерёдно открываются (случайным образом) и как только образуется путь сверху вниз, нужно посчитать количество полных ячеек. Этот процесс повторяется несколько раз, а затем вычисляется средний результат (это уже суть метод Монте-Карло). А вот для того, чтобы определить, существует путь или нет, как раз и служат методы объединения и поиска - открывающиеся ячейки, находящиеся по соседству друг с другом, объединяются в группы, и как только появляется группа, объединяющая верхний и нижний ряды пластинки, она сразу объявляется тем самым путём, по которому проходит фильтрация (протекание или что угодно, что можно смоделировать).

Другие применения этого алгоритма: компьютерные сетяи (находятся два компьютера в одной сети или нет), социальные сети (связаны ли два пользователя через общих друзей), программирование (находятся ли переменные в одной области видимости или нет) и так далее.

Тема интересная и частично пересекается с теорией графов (изучается во второй части этого курса). Задание выполнять было тоже интересно, особенно захватывающе было наблюдать за тем, как работает реализованный тобой алгоритм в программе-визуализаторе (ну и вообще, когда программа работает как надо, это всегда приносить положительные эмоции).

Жаль, что нет времени добавить картинок к посту. Впрочем, куда лучше почитать материалы курса или посмотреть обучающее видео - там даже есть анимации, которые демонстрируют работу алгоритма.

Пост про анализ алгоритмов постараюсь написать завтра.

(Leave a comment)

October 8th, 2013
10:00 pm

[Link]

Курс "Algorithms, Part I" от Coursera
Заканчиваю слушать курс про основные алгоритмы "Algorithms, Part I" Принстонского университета, выложенный на coursera.org. Это моя вторая попытка с данным курсом и, в отличие от первой, я ей очень доволен. Собственно, я попал на coursera только потому, что искал ресурс, где можно изучить алгоритмы: сначала я узнал, что там есть курс "Algorithms: design and analysis" от Стэнфордского университета, но когда я там зарегистрировался, выяснилось, что он уже кончился, а курс от Принстонского как раз начинался. Ну я и решил на него записаться.

Первая попытка не удалась отчасти из-за того, что я переоценил свои возможности и записался сразу на несколько курсов. Конечно же, в силу занятности уделить время всему было невозможно и когда на второй неделе я застрял на одном из заданий, это сказалось на общей успеваемости - ни один из курсов я тогда так и не прошёл.

Теперь же я поставил чёткую цель и сконцентрировался только на этом курсе, так как он интересовал меня больше остальных. Целью моей является получить 100% по контрольным работам (всего 11 штук - по 2 в конце каждой недели и одна в конце последней недели) и не меньше 80% по каждому из проектов (всего 5 штук - по 1 на каждую из недель обучения, кроме последней). Насчёт финального экзамена у меня неопределённость - хочется набрать 100%, так как он преимущественно составлен из тех задач, которые были в недельных контрольных работах, но дело осложняется тем, что там намного больше задач (10 против 3) и даётся меньше попыток (3 против 10). Если будут только задачи, то 100% получить будет намного легче, а если ещё и вопросы по теории, то здесь нет такой определённости - вопросы бывают самые разнообразные, а некоторые даже каверзные. В общем, буду удовлетворён, если наберу 90%.
Насчёт концентрации - снова было сильное искушение проходить несколько курсов сразу, но я его подавил и, в общем-то, правильно сделал - оглядываясь назад, понимаю, что всё равно полноценно заниматься по нескольким курсам, учитывая мою прочую занятость, я бы не смог. К сожалению, действительно интересных курсов очень много и тяжело выбрать, когда нет какого-то чёткого приоритета. В этот раз приоритет был, но как я буду выбирать дальше, я плохо представляю.

По продуктивности - пока иду по плану. А именно - сделал все проекты, по всем набирал не меньше 85%, как и планировал, а по последнему внезапно набрал больше 90% (проект считается успешно завершённым, если сделан на 70%). Недельные контрольные все сдал на 100%, осталась последняя, но с учётом того, что даётся 10 попыток, а тема не самая сложная, уверен, что и её сдам на максимальный балл. Про финальный экзамен уже писал - даётся 3 попытки, экзамен состоит из 10 заданий. Хорошая подготовка заключается, пожалуй, в том, чтобы подготовить набор исходных программ, которые давались в течение курса, подготовить список таблиц с ключевыми характеристиками алгоритмов, ну и повторить как можно подробнее весь изученный материал. Думаю, что за какие-нибудь выходные с этим всем можно справиться, если постараться.

Курс очень понравился. Было не очень трудно, я бы сказал, что можно было сделать жёстче, а именно заставлять студентов самих реализовывать "референсные" программы, а не выдавать их уже в готовом виде, но тогда, наверное, намного снизилась бы успеваемость. Лично я бы потратил намного больше времени (хотя с другой стороны и приобрёл бы больше).

Отдельно сожалею, что не занимался плотно разделом "Задачи, задаваемые на собеседованиях". Это опциональная часть курса, то есть её прохождение ни на что не влияет, но мне она была довольно интересна. Тешу себя надеждой, что когда-нибудь вернусь к ней (курс ещё будет доступен в онлайне некоторое время), но если думать рационально, то вряд ли. Вообще задачи, задаваемые на собеседованиях, для меня представляют исключительно спортивный интерес, потому что работу я пока искать не собираюсь, так что, может быть, это и правильно.

Вроде это все заключительные мысли. Скоро начну писать о впечатлениях о каждой неделе - это поможет как-то сохранить в памяти пройденный материал и подготовиться к финальному экзамену. Постараюсь подготовить шесть постов, публиковать буду по одному в неделю.
Вторая часть курса (называется так же, но "Part II") начнётся 1 ноября.

Другие курсы, которые меня интересуют:

1. "Введение в интерактивное программирование на языке Python" от университета Райс в Техасе (https://www.coursera.org/course/interactivepython). Профессионально на Пайтоне не программирую, но программируют (и хвалят) некоторые коллеги, которых считаю хорошими программистами, да и сам язык, в тех пределах, в которых я его знаю, кажется довольно простым и элегантным. Собственно, сам разработчик языка (Гвидо ван Россум) подчёркивал в интервью, что хотел создать именно язык, на котором было бы удобно вести разработку.

2. "Управление стартапом" от Стэнфордского университета (https://www.coursera.org/course/startup). Этот курс, я так понял, про создание приложения и веб-сайта для его продвижения. Судя по лекциям, там обучают абсолютно всем технологиям (разумеется, в базовом варианте), которые могут пригодится при разработке. И даже есть рейтинг заключительных проектов, где победитель вроде даже получает какие-то профиты в виде продвижения (а может даже денег).

3. "Алгоритмы: разработка и анализ" (тоже в двух частях) от Стэнфордского университета (https://www.coursera.org/course/algo). Собственно, тот курс, из-за которого я оказался на coursera. Меня интересует производительность используемых алгоритмов, а в этом курсе, я так понял, рассказывается именно о теоретических основах оценки производительности.

4. "Научные вычисления" (https://www.coursera.org/course/scientificcomp) и "Высокопроизводительные научные вычисления" (https://www.coursera.org/course/scicomp) от Вашингтонского университета. Курсы по названию похожи, да и подготовлены одним университетом, так что пока не могу сказать, чем они отличаются. Надо почитать подробнее. Эти два курса могут для меня представлять и большой профессиональный интерес, так как именно научными вычислениями я и занимаюсь.

5. "Дискретная оптимизация" от Мельнбурнского университета (https://www.coursera.org/course/optimization). Пока не понял, про что конкретно, но название очень интересное.

6. "Программируя матрицу" от университета Брауна (https://www.coursera.org/course/matrix). Матрицы, ну куда же без них. В курсе рассказывается о задачах, связанными с матрицами, которые возникают в современной науке (задачи, а не матрицы). Создание эффективных программ для проведения вычислений с матрицами. Я сам столкнулся с этой темой недавно, когда в моих работах понадобилось решать системы линейных уравнений. Пришлось реализовать ряд методов для эффективной работы с матрицами, уверен, что этот курс поможет ещё больше отточить свои навыки.

7. "Линейное программирование" (https://www.coursera.org/course/linearprogramming) от университета Боулдера. Линейное программирование, исследование операций применяются во многих задачах оптимизации, типа машинного обучения, статистике, компьютерном зрении и т.д. Очень интересно.

8. "Анализ алгоритмов" от Принстонского университета (https://www.coursera.org/course/aofa). Кстати, читает Роберт Седжвик - автор того курса, который я сейчас заканчиваю. Седжвик - ученик Дональда Кнута и очень известный теоретик в разработках алгоритмов. Курс отличается от просто "Алгоритмов" большим упором на теоретические основы. Если в "Алгоритмах" просто изучались алгоритмы с небольшими упоминаниями о производительности, то в "Анализе" следует ожидать больше теории, формул, асимптотических оценок и разборов сценариев.

9. "Аналитическая комбинаторика" (https://www.coursera.org/course/ac). Читает тоже Седжвик. Как я понимаю, здесь речь пойдёт о комбинаторных объектах, функциях и всех их порождениях. Тоже обещает быть интересным.
Также из интересующих меня курсов, не имеющих отношения к программированию, можно отметить "Историю рока" и "Введение в игру на гитаре", но это скорее для души :-)

К сожалению, многие курсы идут почти одновременно, так что не думаю, что это всё удастся изучить за обозримое время (полгода-год). Может уйти и года 3. И да, не стоит, конечно же, ожидать, что отдельно взятый курс обучит предмету от и до - аналогичный курс, полноценно прослушанный в "оффлайновом" университете (с хождением на лекции, решением задач) по-любому лучше (хотя насчёт российских университетов можно поспорить). Но всё же это даёт пищу для размышления, даёт новую информацию, ну и вообще помогает держаться в тренде, а это уже очень хорошо!

(4 comments | Leave a comment)

[<< Previous 10 entries]

Powered by LiveJournal.com