ДМ_экзамен_Т8


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

по курсу «Дискретная математика»



для группы Т8-67б, 6

Графы ориентированные и неориентированные.

Матричная форма задания графов.

Изоморфизм. Проверка изоморфизма. Понятие подграфа.

Подграфы. Определение и способ построения. Кn, Kn,m.

Операции над графами.

Маршруты в графах. Волновой алгоритм нахождения минимального расстояния в графе.

Связность графа. Алгоритмы нахождения компонентов связности графа.

Конденсация графа.

Радиус и диаметр графа. Алгоритм нахождения.

Дерево. Теорема о дереве.

Точка сочленения графа. Блок.

Вершинная и реберная связанности графа.

Остов. Алгоритмы нахождения остова графа.

Циклы и разрезы в графах. Цикломатическое число.

Эйлеров и гамильтонов циклы и алгоритмы их нахождения.

Внутренне устойчивое множество в графе. Алгоритм выделения.

Внешне устойчивое множество в графе. Алгоритм выделения.



Клика графа. Алгоритм нахождения.

Паросочетание. Алгоритм нахождения.

Раскраска графа. Приближенный алгоритм. Двойственный и самодвойственный графы.

Планарность графа. Алгоритм укладывания графа на плоскость. Род поверхности.

Автоморфизм графа.

Понятие алгоритма. Современная теория алгоритмов. Машины Тьюринга и его тезис. Модификация машин Тьюринга. Теоремы Шеннона.

Описательные числа и универсальная машина. Задача остановки и другие алгоритмически неразрешимые задачи для машины Тьюринга.

Нормальные алгоритмы и тезис Маркова.

Построение нормального алгоритма по программе машины Тьюринга.




Предыдущий:

Следующий: