Вопросы

• Понятия (определения) алгоритмов
• Алгоритмы и автоматы
• Машины Тьюринга
• Рекурсивные функции
• Вычислимость и разрешимость
• Модели автоматов (Мура, Мили)
• Диаграммы состояний
• Детерминированные и недетерминированные автоматы.

М2

1. Понятие алгоритма и графическая форма его представления.
2. Организация циклов: с параметром, с предусловием и постусловием; обработка векторов и матриц, основные алгоритмы: сортировка, поиск.
3. Сложность алгоритмов.
4. Функции и процедуры, формальные и фактические параметры, рекурсия.

****************************************************************************************************************************************************************************************

1. Динамическое программирование. Основные принципы, примеры алгоритмов: выравнивание текста по ширине, выравнивание
   последовательностей.

2. Основные алгоритмы на графах. Представление графов в виде списков смежности и матрицы смежности. Обход графа в глубину и ширину. Связность в ориентированных и неориентированных графах. Двунаправленный поиск путей в графах. Поиск кратчайших путей во взвешенном графе, алгоритмы Беллмана – Форда, Флойда – Уоршелла. Поиск кратчайших путей в графе при помощи алгоритма Дейкстры. Минимальные остовные деревья: алгоритмы Прима и Крускала.

3. Структуры данных. Система непересекающихся множеств. Хеш-таблицы. Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.

4. Потоки в сетях. Определение потока, циркуляции. Задача о максимальном потоке. Алгоритм Форда – Фалкерсона. Максимальный поток и минимальный разрез. Максимальное паросочетание в двудольном графе. Совершенное паросочетание с минимальным весом во взвешенном двудольном графе.

5. Конечные автоматы, регулярные выражения, контекстно-свободные грамматики. Регулярные языки. Замкнутость регулярных языков по объединению. Минимизация конечного автомата. Регулярные выражения. Недетерминированные конечные автоматы. Замкнутость регулярных языков относительно регулярных операций. Построение конечного автомата по регулярному выражению. Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки. Лемма о накачке. Контекстно-свободные грамматики. Автоматы с магазинной памятью. Эквивалентность контекстно-свободных грамматик и автоматов с магазинной памятью. Построение автомата по грамматике. Лемма о накачке для контекстно-свободных языков. 

Основная литература

1. Вирт Н. Алгоритмы и структуры данных. – М.: ДМК Пресс, 2012. – 272 с.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: учеб. Пособие. - М.: Издательский дом «Вильямс», 2008. – 369 с.К
3. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 2- е издание: Пер. с англ. — М.: Вильямс, 2007. 
4. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МНЦМО, 2014.
 

Дополнительная литература

1. Сенилов М.А. Методические указания для самостоятельной работы студентов по дисциплине «Структуры и алгоритмы обработки данных в ЭВМ». – Ижевск: Изд-во ижгту, 2008.
2. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных: учеб. Пособие. – М.: Финансы и статистика; ИРФРА-М, 2009. – 304 с.
3. Кнут Д. Искусство программирования для ЭВМ. Том 1.: Основные алгоритмы. - М.: Издательский дом «Вильямс», 2008. – 690 с.
4. Кнут Д. Искусство программирования для ЭВМ. Том 3.: Сортировка и поиск. - М.: Издательский дом «Вильямс», 2008. – 720 с.
5. Бабенко М.А., Левин М.В. Введение в теорию алгоритмов и структур данных. – М.: ФМОП, МЦНМО, 2012. – 144 с.
6. Круз Р.Л. Структуры данных и проектирование программ. – М.: БИНОМ. Лаборатория знаний, 2012. – 765 с.
7. Окулов С.М. Абстрактные типы данных. – М.: БИНОМ. Лаборатория знаний, 2013. – 250 с.