Реферат: Список вопросов к зачету

ЛКШ – 2005. Группа C3.


Список вопросов к зачету


Стек, очередь, дек: основные операции, реализация, возможные ошибки функционирования.

Куча: основные операции, их реализация, оценка сложности.

HeapSort.

QSort.

Бинарный поиск.

Графы: основные определения. Способы представления графов в компьютере. Теорема о четности числа вершин нечетной степени. Деревья. Теорема о соотношении числа ребер и вершин в дереве.

Планарные графы. Формула Эейлера. Доказательство непланарности графов K5 и K3,3.

Алгоритмы обхода графа в ширину и в глубину.

Алгоритмы поиска кратчайших путей: алгоритм Дейкстры (реализация, оценка сложности, область применения).

Алгоритмы поиска кратчайших путей: алгоритм Флойда (реализация, обоснование, оценка сложности, область применения).

Алгоритмы поиска кратчайших путей: алгоритм Форда-Белмана (реализация, обоснование, оценка сложности, область применения).

Алгоритмы построения минимального каркаса: алгоритм Прима.

Алгоритмы построения минимального каркаса: алгоритм Краскала.

Топологическая сортировка.

Построение эйлерового цикла.

Генерация перестановок в лексикографическом порядке.

Генерация перестановки по номеру и номера по перестановке.

Число сочетаний (Cnk). Треугольник Паскаля. Основные свойства и тождества.

Метод динамического программирования (на примере нескольки задач).

Перебор. Основные этапы: отсечения, получение предварительной оценки, эвристики, отсечение по времени.

Формулы Бэкуса-Науэра для арифметических выражений. Метод рекурсивного спуска.

Конечные автоматы. Основные определения. Детерминированные и недетерминированные автоматы. Примеры регулярного и нерегулярного языков. Доказательство теоремы о том, что множества языков, распознаваемых детерминированными и недетерминированными автоматами, совпадают.

Проверка принимаемости слова недетерминированным автоматом. Проверка эквивалентности двух детерминированных автоматов.

Поиск подстроки в строке. Алгоритм Кнута–Морриса–Пратта.