Вопросы к экзамену

Экзаменационные вопросы по курсу лекций «Алгоритмы и алгоритмические языки» для студентов 1 потока, 1 курса факультета ВМК МГУ. 2010/2011 уч.год, 1 семестр.  Лектор - профессор Гайсарян С.С.

I. Понятие алгоритма.

  1. Задачи обработки информации и алгоритмы. Неформальное (интуитивное) определение алгоритма.
  2. Формализация алгоритма. Машина Тьюринга.
  3. Способы представления машин Тьюринга.
  4. Понятие Универсальной машина Тьюринга.
  5. Проблема останова и алгоритмическая неразрешимость.
  6. Тезис Тьюринга – Черча.
  7. Нормальные алгоритмы Маркова. Эквивалентность алгоритмов.
  8. Композиция нормальных алгоритмов Маркова.
  9. Алгоритмическая неразрешимость проверки свойства самоприменимости.

II. Базовые понятия языка программирования Си.

  1. Способы описания языка программирования. Описание синтаксиса. – металингвистические формулы (БНФ), синтаксические диаграммы.
  2. Структура Си-программы.
  3. Типы данных. Переменные, константы. Классы памяти. Области видимости и существования переменных.
  4. Операторы языка Си: условные операторы, операторы цикла, операторы перехода, составной оператор (блок).
  5. Функции. Объявление функции. Формальные параметры. Возвращаемое значение. Побочный эффект функции. Функции типа void. Определение функции. Библиотечные функции. Вызов функции. Фактические параметры и способ их передачи (по значению).
  6. Сборка Си-программы: препроцессирование, компиляция, компоновка. Стандартные библиотеки языка Си. Директива #include и заголовочные файлы.
  7. Арифметические типы данных. Арифметические операции над целочисленными данными.
  8. Арифметические операции над данными с плавающей точкой.
  9. Символьный тип данных (char).
  10. Отношения и логические операции. Поразрядные операции.
  11. Приведение типов. Правила неявного преобразования типов («обычные арифметические преобразования»).
  12. Массивы и строки.
  13. Указатели. Адресная арифметика. Указатели и массивы. Передача массива в функцию. Массивы указателей. Квалификатор restrict.
  14. Многомерные массивы.
  15. Операция sizeof.
  16. Преобразование типа указателя.
  17. Структуры, перечисления, объединения. typedef.
  18. Рекурсивные функции.
  19. Указатель на функцию.
  20. Файлы.
  21. Динамическое распределение памяти.

III. Алгоритмы и структуры данных.

  1. Динамические структуры данных. Список (однонаправленный и двунаправленный). Очередь и ее реализация на массиве и на списке. Стек и его реализация на массиве и на списке.
  2. Пример применения стека для преобразования выражений в польскую запись.
  3. Сортировка. Основные алгоритмы сортировки. Оценка сложности алгоритмов сортировки.
  4. Быстрая сортировка Хоара.
  5. Словарные операции и их реализация с помощью хеш-функций. Методы построения хеш-функций.
  6. Хеширование с цепочками. Хеширование с открытой адресацией. Двойное хеширование.
  7. Оценка среднего времени успешного поиска в хеш-таблице с коэффициентом заполнения α.
  8. Двоичные деревья поиска. Реализация словарных операций: search (найти), insert (вставить) и delete (удалить). Реализация операций min (минимум), max (максимум), pred (предыдущий) и succ (следующий).
  9. Построение двоичного дерева поиска.
  10. Сбалансированные двоичные деревья. Деревья Фибоначчи. Число узлов в дереве Фибоначчи высоты h.
  11. АВЛ-деревья. Балансирование АВЛ-деревьев. Базовые операции над АВЛ-деревьями (удалить дерево, поиск по ключу, минимальный ключ, максимальный ключ, вставить узел, исключить узел) и их реализация.
  12. Построение АВЛ-дерева.
  13. Цифровой поиск.
  14. Поиск подстрок по образцу.
  15. Алгоритм Кнута – Морриса – Пратта.
  16. Различные способы обхода двоичного дерева.
  17. Прошитое двоичное дерево. Прошитое двоичное дерево с заголовком.
  18. Представление произвольного дерева в виде двоичного.
  19. Топологическая сортировка узлов ациклического ориентированного графа. Постановка и исследование задачи.
  20. Топологическая сортировка узлов ациклического ориентированного графа. Алгоритм Вирта.
  21. Алгоритмы перебора множеств. Рекурсивный алгоритм генерации перестановок.
  22. Алгоритмы перебора множеств. Алгоритм Нарайаны.

Leave a Reply