Нелинейные структуры данных.

Рекурсии. Общие сведения о деревьях. Представление деревьев в памяти ЭВМ. Операции над деревьями.

 

Алгоритмы решения задач выбора.

Способы решения задач. Применение рекурсий. Дерево решений. Переборные задачи. Алгоритмы с возвратом. Метод ветвей и границ. Метод проб и ошибок. Динамическое программирование. Жадные алгоритмы.

 

Сортировка данных.

Общие понятия. Внутренняя сортировка: основные методы, быстрые методы. Внешняя сортировка.

 

Алгоритмы комбинаторики.

Генерация комбинаторных объектов. Перебор всех вариантов. Перестановки. Сочетания.

 

Табличные структуры.

Виды таблиц. Линейные таблицы. Древовидные таблицы. Таблицы с вычисляемыми входами.

 

Алгоритмы на графах.

Основные определения. Представление графов. Пути в графе. Кратчайшие пути. Обходы графов. Остовное дерево наименьшего веса.

 

Перечень рекомендуемой литературы:

1. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М., Изд. "Вильямс", 2000 г.

2. Вирт Н. Алгоритмы + структуры данных = программы. М., Изд. "Мир", 1985 г.

3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., «Мир», 1982 г.

4. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., "Мир", 1976 г., (переиздание - М., Изд. "Вильямс", 2000 г.)

5. Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., "Мир", 1978 г., (переиздание - М., Изд. Изд. Вильямс", 2000 г.)

6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Анализ и построение. М., Изд. "БИНОМ", 2000 г.

7. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. – М.: Вильямс, 2005.

8. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

9. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учебное пособие. – М.: Финансы и статистика, 2004.

 

Вопросы САОД

 

1. Динамические типы данных: список, стек, очередь, дек.

2. Нелинейные структуры данных: деревья, представление деревьев в ЭВМ, операции над деревьями.

3. Идеально сбалансированное бинарное дерево. Сбалансированные деревья поиска.

4. Алгоритмы с возвратом.

5. Динамическое программирование.

6. Методы сортировки массивов.

7. Внешняя сортировка.

8. Генерация комбинаторных объектов. Перебор всех вариантов.

9. Генерация комбинаторных объектов. Перестановки.

10. Линейные таблицы: поиск в неупорядоченных и упорядоченных таблицах.

11. Таблицы с вычисляемыми входами.

12. Построение матрицы достижимости (путевая матрица).

13. Кратчайшие пути: алгоритм Дейкстры, алгоритм Флойда.

14. Поиск в ширину и глубину на графе.

15. Остовное дерево минимального веса: алгоритм Прима, алгоритм Крускала.

 

Задачи САОД

1. Для задачи «Бросание кубика» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q.

2. Для задачи «Выражение» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Расставить между заданными N целыми числами знаки «+» и «-» так, чтобы значение получившего выражения было равно заданному S.

3. Для задачи «Дележ» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Заданные N предметов разделить на две примерно одинаковые части.

4. Для задачи «Максимальный квадрат» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: На заданной дискретной карте найти свободный квадрат максимального размера.

5. Для задачи «Коммивояжер» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Найти последовательность посещения заданных N городов.

6. Для задачи «Маршрут» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: В заданной квадратной таблице размера N найти такой путь из левого верхнего угла в правый нижний, у которого сумма чисел минимальна.

7. Для задачи «Музей» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: В музее регистрируется время прихода и ухода посетителей. Найти максимальное число посетителей, находящихся в музее одновременно.

8. Для задачи «Перемножение матриц» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Вычислить произведение N матриц A₁A₂…A_N за наименьшее количество действий.

9. Для задачи «Монетки» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Имеется по две монетки достоинством a₁, a₂, …, a_N. Можно ли ими заплатить сумму в S рублей.

10. Для задачи «Разделение сред» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Имеется N материалов, из которых необходимо сделать перегородку с наибольшим временем разделения сред.

11. Для задачи «Подпоследовательность» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Для двух заданных последовательностей найти общую подпоследовательность наибольшей длины.

 

12. Для задачи «Рюкзак» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Имеется N предметов различных типов весом a_i и стоимостью b_i. Найти максимальную стоимость груза, помещающегося в рюкзак, выдерживающий максимальный вес W.

13. Для задачи «Сплочённая команда» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Команда будет сплочённой, если профессионализм каждого не превосходит суммы профессионализмов любых двух других игроков. Сформировать из N игроков наиболее сплочённую команду.

14. Для задачи «Счастливые билеты» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Найти количество счастливых билетов из 2N цифр.

15. Для задачи «Точки» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Найти количество точек с целочисленными координатами в круге радиуса N.

Методологии программирования

 

Модели вычислений

Понятие методологии программирования. Обзор развития языков программирования и методологий. Традиционная архитектура вычислительных машин. Первое понятие о стилях программирования. Модификации традиционной архитектуры. Нетрадиционные архитектуры. Сети данных и параллелизм. Эмуляция и машина программы.

Языки программирования

Традиционные языки и традиционная архитектура. Структура традиционной программы. Основные традиционные языки. Преобразование текста программы в исполняемый код. Синтаксис, семантика и прагматика языка программирования. Понятие НБФ грамматики. Определение порождающей и распознающей грамматики. Описание процесса трансляции.

Формальная теория. Исчисление высказываний. Исчисление предикатов. Модальные логики.

Высказывания. Логические связки. Формулы. Интерпретация. Таблица истинности. Логическое следование и логическая эквивалентность. Подстановка. Определение формальной теории. Алфавит. Формула. Аксиома. Правила вывода. Выводимость формулы. Интерпретация формальной теории. Общезначимость и непротиворечивость. Полнота, независимость и разрешимость.

Классическое определение исчисления высказываний. Частный случай формулы. Алгоритм унификации. Конструктивное определение исчисления высказываний. Производные правила вывода. Теорема дедукции. Следствия теоремы дедукции. Множество теорем исчисления высказываний. Теорема о непротиворечивости.

Определение исчисления предикатов. Связки. Кванторы. Предикаты. Функциональные символы. Формула. Связанные и свободные вхождения переменных в формулу. Замкнутая формула. Терм свободный для переменной в формуле. Правила вывода исчисления предикатов. Понятие о прикладном и чистом исчислении предикатов, исчислении предикатов первого и высших порядков. Интерпретация. Модель множества формул. Общезначимость. Теорема полноты чистого исчисления предикатов. Формальная арифметика. Теоремы Гёделя о неполноте.

Синтаксис модальной логики. Модальные операторы. Темпоральные логики. Семантика Крипке. Семантика темпоральной логики.