Экзаменационные вопросы по курсу лекций «Алгоритмы и алгоритмические языки» для студентов 1 потока, 1 курса факультета ВМК МГУ. 2011/2012 уч.год, 1 семестр.
I. Формальные системы описания алгоритмов.
- Задачи обработки информации и алгоритмы. Неформальное (интуитивное) определение алгоритма.
- Формализация алгоритма. Машина Тьюринга.
- Способы представления машин Тьюринга. Нормальные вычисления.
- Диаграммы Тьюринга. Построение диаграмм Тьюринга. Построение таблиц по диаграммам.
- Понятие универсальной машины Тьюринга. Построение универсальной машины Тьюринга.
- Проблема останова и алгоритмическая неразрешимость.
- Алгоритмическая неразрешимость проблемы самоприменимости.
- Тезис Тьюринга – Черча.
- Нормальные алгоритмы Маркова. Эквивалентность формальных систем описания алгоритмов.
II. Язык программирования Си.
- Язык программирования Си. Описание Си-машины.
- Структура Си-программы.
- Типы данных. Переменные, константы. Классы памяти. Области видимости и существования переменных.
- Арифметические типы данных. Арифметические операции над целочисленными данными.
- Приведение типов. Правила неявного преобразования типов («обычные арифметические преобразования»).
- Старшинство операций.
- Операторы языка Си: условные операторы, операторы цикла, операторы перехода, составной оператор (блок).
- Символьный тип данных (char).
- Массивы и строки.
- Указатели. Адресная арифметика. Преобразование типа указателя.
- Указатели и массивы. Массивы указателей. Многомерные массивы.
- Функции. Объявление функции. Формальные параметры. Возвращаемое значение. Побочный эффект функции. Функции типа void.
- Определение функции. Библиотечные функции. Вызов функции. Фактические параметры и способ их передачи (по значению). Указатели и параметры функции. Передача массива в функцию.Квалификатор restrict.
- Рекурсивные функции. Квалификатор inline.
- Операция sizeof.
- Арифметические операции над данными с плавающей точкой.
- Отношения и логические операции. Поразрядные операции. Реализация абстрактного типа данных «множество».
- Структуры, перечисления, объединения. Указатели на структуры. Битовые поля. Ключевое слово typedef.
- Динамическое распределение памяти.
- Указатель на функцию.
- Сборка Си-программы: препроцессирование, компиляция, компоновка. Директивы препроцессора. Директива #include и заголовочные файлы. Условная компиляция.
- Стандартные библиотеки языка Си.
III. Алгоритмы и структуры данных.
- Динамические структуры данных. Список (однонаправленный и двунаправленный). Стек и его реализация на массиве и на списке. Очередь.
- Применение стека для преобразования выражений в польскую запись.
- Топологическая сортировка узлов ациклического ориентированного графа: постановка задачи, алгоритм Вирта.
- Сортировка. Основные алгоритмы сортировки. Оценка сложности алгоритмов сортировки.
- Быстрая сортировка Хоара.
- Двоичное дерево. Представление двоичного дерева в памяти компьютера.
- Способы обхода двоичного дерева и их рекурсивная и нерекурсивная реализации.
- Прошитое двоичное дерево. Прошитое двоичное дерево с заголовком.
- Двоичные деревья поиска. Реализация словарных операций: search (найти), insert (вставить) и delete (удалить). Реализация операций min (минимум), max (максимум), pred (предыдущий) и succ (следующий).
- Построение двоичного дерева поиска.
- Структура данных «пирамида». Пирамидальная сортировка.
- Сбалансированные двоичные деревья. Деревья Фибоначчи. Число узлов в дереве Фибоначчи высоты h.
- АВЛ-деревья. Базовые операции над АВЛ-деревьями (удалить дерево, поиск по ключу, минимальный ключ, максимальный ключ) и их реализация.
- Балансирование АВЛ-деревьев. Реализация операции вставки узла в АВЛ-дерево. Построение АВЛ-дерева.
- Красно-черные деревья. Вставка узла в красно-черное дерево.
- Словарные операции и их реализация с помощью хеш-функций. Методы построения хеш-функций.
- Хеширование с цепочками. Хеширование с открытой адресацией. Двойное хеширование.
- Оценка среднего времени успешного поиска в хеш-таблице с коэффициентом заполнения α.
- Цифровой поиск.
- Поиск подстрок по образцу. Алгоритм Кнута – Морриса – Пратта.
- Алгоритмы перебора множеств. Рекурсивный алгоритм генерации перестановок. Алгоритм Нарайаны.