8-9-ый семестры , ПМК, кафедра информатики
1.1.Машины с произвольным доступом к памяти. Меры сложности вычислений. ПДП-машины и машины Тьюринга.
1.2. Линейные программы. Битовые линейные программы.Ветвящиеся программы (деревья сравнений).
1.3. Модельный алгоритмический язык. Сложность реализации основных конструкций на ПДП-машине.
2.1. Списки, стеки (магазины), очереди.Алгоритмы выполнения основных операций.
2.2. Графы, деревья, бинарные деревья. Способы представления. Алгоритмы обхода деревьев.
2.3. Метод разработки алгоритмов "разделяй и властвуй". Алгоритм умножения двоичных чисел. Техническая лемма об оценке роста функций, заданных реккурентными соотношениями.
2.4. Динамическое программирование. Оптимальное умножение последовательности матриц. Алгоритм распознавания кс-языков.
3.1. Нижние оценки числа сравнений (в "худшем" и в "среднем").
3.2. Алгоритм сортировки обменами (методом "пузырька").
3.3. Алгоритм сортировки слиянием.
3.4. Алгоритм быстрой сортировки Хоара. Оценка сложности "в среднем".
3.5. Алгоритм пирамидальной сортировки (с помощью дерева).
3.6. Алгоритм лексикографической сортировки.
3.7. Алгоритмы нахождения k-го наименьшего элемента.
3.8. Нижняя оценка числа сравнений для нахождения 2-го по величине элемента множества (теорема Кислицына).
4.1. Алгоритмы выполнения основных операций при использовании "внешних" и "внутренних" цепей.
4.2. Повторное хеширование. Выбор хеш-функции.
5.1. Деревья двоичного поиска. Алгоритм построения оптимального дерева двоичного поиска.
5.2. 2-3-деревья. Алгоритмы вставки и удаления элементов из 2-3-дерева.
5.3. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием массивов и списков.
5.4. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием древовидных структур (сжатие путей).
5.5. Алгоритм проверки эквивалентности конечных автоматов.
5.6. В-деревья и алгоритмы работы с ними.
6.1. Минимальное остовное дерево.
6.2. Поиск в глубину и поиск в ширину в неориентированных и ориентированных графах.
6.3. Алгоритм Дойча-Шорра-Уэйта для обхода ориентированного графа.
6.4. Алгоритм определения двусвязных компонент графа.
6.5. Алгоритмы построения транзитивного замыкания графа и нахождения кратчайших путей.
6.6. Задача о кратчайших путях из одного источника.
6.7. Задача о максимальном потоке в сетях. Алгоритм Форда-Фалкерсона.
6.8. Алгоритм нахождения максимального потока за кубическое время.
6.9. Простые сети и задача о максимальном паросочетании для двудольных графов.
7.1. Алгоритм Штрассена для умножения матриц.
7.2. НВП-разложение иатриц.
7.3. Сложность обращения матриц, вычисления определителя и решения системы линейных уравнений.
7.4. Алгоритм ЧР для умножения булевых матриц.
7.5. Связь между умножением булевых матриц и нахождением транзитивного замыкания графа.
8.1. Регулярные выражения, языки и недетерминированные конечные автоматы. Распознавание образцов, задаваемых регу- лярными выражениями.
8.2. Алгоритм Морриса-Пратта для задачи вхождения подцепочек.
8.3. Позиционные деревья и решаемые с их помощью задачи. Алгоритм построения позиционного дерева за линейное (от его размера) время.
9.1. Классы P и NP. Сводимость за полиномиальное время. Теорема Кука-Левина о NP-полноте задачи выполнимости булевых формул. 9.2. Примеры NP-полных задач в логике, теории графов, алгебре, комбинаторике, математическом программировании: 3-КНФ, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ГАМИЛЬТОНОВ ЦИКЛ, РАСКРАСКА, 3-СОЧЕТАНИЕ, РАЗБИЕНИЕ, РЮКЗАК, 0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ, КОММИВОЯЗЖЕР, МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ, УРАВНЕНИЯ В СЛОВАХ и др.
9.3. Сильная NP-полнота задачи 3-РАЗБИЕНИЕ. Задача о бартерных сделках (выводимость в коммутативной полугруппе).
9.4. Подходы к решению NP-полных задач с использованием эвристических и приближенных алгоритмов.
ЛИТЕРАТУРА
1.А.Ахо, Дж.Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов.- М.:Мир, 1979.
2.Д.Кнут. Искусство программирования для ЭВМ. т.3. Сортировка и поиск.- М.: Мир, 1978.
3. Э.Рейнгольд, Ю.Нивергельт,Н.Део. Комбинаторные алго- ритмы. Теория и практика.- М.:Мир, 1980.
4. М.Сибуя, Т. Ямамото. Алгоритмы обработки данных. - М.:Мир, 1986.
5. Н.Вирт. Алгоритмы и структуры данных.- М.:Мир, 1989.
6. Х.Пападимитриу, К.Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность.- М.:Мир, 1985.
7. В.Липский. Комбинаторика для программистов.-М.:Мир,1988.
8. М.Гэри, Д.Джонсон. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982.