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