Реферат: Понятие алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Черча. Машины Тьюринга. Тезис Тьюринга

Список вопросов к экзамену

Понятие алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Черча. Машины Тьюринга. Тезис Тьюринга. Рекурсивные и рекурсивно перечислимые множества. Неразрешимые проблемы.

Временная сложность алгоритма. Θ, Ω, Ο – символика. Правила подсчета временной сложности.

Полиномиальная и экспоненциальные сложности. Классы P и NP. NP-полные задачи. Примеры.

Метод ветвей и границ. Применение метода ветвей и границ для решения задачи о рюкзаке.

Динамическое программирование. Пример применения динамического программирования для решения задачи об оптимальной последовательности перемножения матриц. Свойства задач, для которых применимо динамическое программирование.

Динамическое программирование. Пример применения динамического программирования для решения задачи о линейном раскрое. Свойства задач, для которых применимо динамическое программирование.

Жадные алгоритмы. Свойство жадного выбора. Задача о выборе заявок. Свойства задач, для которых применим жадный алгоритм.

Приближенные методы решения задач: ослабление задачи, локальный поиск, эвристика жадного выбора и локального поиска. Примеры.

Абстрактные типы данных. АТД словарь. Реализация при помощи нагруженного дерева. Способы реализации нагруженного дерева в ЭВМ.

Очереди с приоритетом. Способы реализации. Частично-упорядоченное дерево (пирамида или двоичная куча). Реализация пирамиды.

Корневые деревья. Реализация корневого дерева. Представление «левый сын – правый брат».

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

Определение компонент связности неориентированного графа.

Определение компонент сильной связности ориентированного графа.

Поиск мостов. Поиск точек сочленения.

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

Поиск кратчайших путей в бесконтурном графе.

Алгоритм Форда-Беллмана.

Алгоритм Дейкстры.

Алгоритм Флойда.

Минимальные покрывающие деревья. Алгоритм Прима. Алгоритм Крускала.


Критерии оценок:

«Отлично» – умение обосновать правильность работы алгоритма, оценить его сложность.


«Хорошо» – знание формулировок задач, определений, умение объяснить, как устроены алгоритмы и используемые структуры данных.


«Удовлетворительно» – твердые знания определений, методов, алгоритмов.


«Неудовлетворительно» – незнание предмета, либо знания бессистемные, обрывочные.