Проектирование и анализ алгоритмов
Введение
В этом курсе мы будем в первую очередь реализовывать классические алгоритмы из разных областей информатики. Приоритет отдается алгоритмам, которые либо легко объяснить, либо легко реализовать.
Алгоритмы вы можете разрабатывать на любом языке программирования. Берите знакомый язык или тот, который хотите изучать.
Для каждого алгоритма будут выданы файлы с тестами, в них данные для запуска алгоритма. И для каждого файла с тестом будет файл с правильным ответом.
Ваша программа должна быть «консольной», это значит, что она не имеет графического интерфейса, запускается, берет данные из стандартного входа, выводит в стандартный вывод. Если вы запускаете ее из командной строки, условие для задачи дано в test.in, то делайте это так:
program.exe <test.in >program.out
Для проверки правильности ответа:
diff program.out test.out
Это сравнит вывод программы и правильный ответ.
Либо вы можете пользоваться возможностями среды разработки, чтобы она при отладочном запуске программы перенаправляла стандартный ввод и вывод.
Кроме того, среда разработки может использоваться и для сравнения файлов. Чтобы проверить, совпадает ли ваш ответ с правильным.
Выкладывание решений
Для каждого задания я даю ссылку, куда надо выкладывать ваши решения. По ссылке вы можете выкладывать мне файлы с решениями — кодом программ. Для выкладывания нужна регистрация на alpha.multivariant.ru. При регистрации напишите Имя, Фамилию и группу. Пожалуйста, не теряйте пароль, потому что сейчас сайт не умеет его восстанавливать.
Ответьте, пожалуйста, на вопросы анкеты, чтобы я мог правильно выстроить курс: http://alpha.multivariant.ru/room/6021085db58dc4e3c252b7a1
Лекция 1
Практические задания
Тренировка. Сложение чисел.
http://alpha.multivariant.ru/room/60210a48b58dc4e3c252bb8b
Двоичный поиск
Классический двоичный поиск значения в массиве
Проверьте, сможете ли вы написать это с первого раза. Не запутавшись в условиях. Подробное условие и алгоритм по ссылке http://alpha.multivariant.ru/room/602a5fe9b58dc4e3c259f16c
Двоичный поиск по ответу
Двоичный поиск можно применять не только для поиска значения в массиве. Прочитайте об этом по ссылке https://wiki.algocode.ru/index.php?title=%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%BF%D0%BE_%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%83
Задача для тренировки: Покрыть точки на прямой отрезками минимальной длиныhttp://alpha.multivariant.ru/room/602bbcddb58dc4e3c25ae235
Двоичные деревья
Двоичные деревья — это структуры данных, которые хранят данные в узлах дерева, у каждого узла не более двух потомков.
Двоичные деревья бывают разные для разных целей. Двоичные деревья поиска. Они хранят упорядоченное множество объектов, например, хранят множество чисел, и позволяют - добавлять, удалять элементы - проверять, есть ли элемент в множестве - искать минимальные, максимальные элементы множества - перечислять элементы множества в порядке возрастания или убывания. - находить для заданного элемента следующий по порядку, или предыдущий.
Если вы знакомы с хэш-таблицами, то можете сравнить двоичные деревья поиска с ними. В отличие от хэш таблиц, деревья поиска знают о порядке элементов множества. Но это достигается за счет более медленных операций.
Куча Это тоже двоичное дерево, но оно позволяет только добавлять элементы в множество, находить минимальный, удалять минимальный. Куча используется в основном как очередь с приоритами — у вас есть очередь из элементов, и вы добавляете туда новые элементы. А когда нужно выбрать очередной элемент из очереди, берется тот, у которого самый высокий приоритет.
В нашем курсе, судя по анкетам, многие участники уже реализовывали двоичные деревья и кучи, потому что это классические алгоритмы, которые часто обсуждаются при изучении структур данных. Второй раз их реализовывать не нужно. Для тех, кто еще не реализовывал двоичные деревья и кучи, я предлагаю задачу:
Двоичные деревья и операции с ними
Материалы. Вы можете читать только те разделы, которые нужны для решения задачи.
Двоичные дервья, наивная реализация
Сбалансированные двоичные деревья Если программировать двоичное дерево наивно, без оптимизаций, оно может работать очень неэффективно. Чтобы операции поиска элемента, добавления, удаления гарантированно работали эффективно, нужно, чтобы дерево было сбалансированным. Есть очень много подходов к тому, как балансировать деревья. Возможно, вы слышали об АВЛ-деревьях, красно-черных деревьях и других аналогичных породах деревьев. Такие деревья постоянно балансируются разными способами, чтобы гарантировать эффективную работу. Но их довольно трудно программировать из-за необходимости разбирать больше число случаев того, как могла нарушиться балансировка.
В этом курсе я предлагаю реализовать Декартово дерево. Его особенность в том, что его очень легко программировать, все операции занимают буквально несколько строчек. Для тех, кто участвует в соревнованиях, где нельзя пользоваться стандартной библиотекой со структурами данных, такое дерево незаменимо. Подвох с этим деревом только в том, что оно использует случайные числа, и, хоть и с очень небольшой вероятность, может выполнять запрос долго. На практике этими вероятностями можно пренебречь, и только в приложениях, от которых зависит жизнь или финансы, использовать Декартово дерево не стоит. В этом случае лучше все-таки реализовать, например, красно-черное дерево.
Реализуйте декартово дерево, задача про него аналогична задаче о двоичном дереве, повторяю ссылку: Двоичные деревья и операции с ними
Материалы: Декартово дерево
Система непересекающихся множеств:
Реализуйте структуру данных «система непересекающихся множеств». Обязательно добавьте эвристику об обновлении ссылок на корень в момент выполнения поиска, и попробуйте эвристику с оценкой высоты дерева. Ускорит ли вторая эвристика ваши программы.
Условие двух задач на систему непересекающихся множеств: