Перечень тем курсовых работ по предмету. «Теория алгоритмов и математические основы представления знаний»

«Теория алгоритмов и математические основы представления знаний»

На 2015-2016 уч. год

На баллы от 10 до 11

Вариант 27.

Тема: «Исследование алгоритма поиска простого пути на графе».

Задание: Реализовать алгоритм поиска простого пути на неориентированном графе. Граф представить в виде матрицы смежности. Показать трассировку рекурсивных вызовов (и пропущенные вершины) когда алгоритм поиска простого пути производит поиск пути из вершины 0 в вершину 5 на графе: 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Провести эксперименты с целью определения эмпирическим путем вероятности того, что данный алгоритм найдет путь между двумя наудачу выбранными вершинами в различных графах и вычислить среднюю длину пути, найденного для различных графов.

Вариант 28.

Тема: «Исследование алгоритма поиска Гамильтонового пути на графе».

Задание: Реализовать алгоритм поиска Гамильтонового пути на неориентированном графе. Граф представить в виде матрицы смежности. Показать трассировку рекурсивных вызовов (и пропущенные вершины) когда алгоритм находит гамильтонов цикл на графе: 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Рассмотреть графы, заданные следующими четырьмя наборами ребер:

0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8

0-1 0-2 0-3 1-3 0-3 2-5 5-6 3-6 4-7 4-8 5-8 5-9 6-7 6-9 8-8

0-1 1-2 1-3 0-3 0-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8

4-1 7-9 6-2 7-3 5-0 0-2 0-8 1-6 3-9 6-3 2-8 1-5 9-8 4-5 4-7

Какие из этих графов содержат Гамильтоновы циклы? Либо показать, что такого не существует.

Вариант 29.

Тема: «Исследование алгоритма поиска Эйлерова пути на графе».

Задание: Реализовать алгоритм поиска Эйлерового пути на неориентированном графе. Граф представить в виде матрицы смежности. Рассмотреть графы, заданные следующими четырьмя наборами ребер:

0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8

0-1 0-2 0-3 1-3 0-3 2-5 5-6 3-6 4-7 4-8 5-8 5-9 6-7 6-9 8-8

0-1 1-2 1-3 0-3 0-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8

4-1 7-9 6-2 7-3 5-0 0-2 0-8 1-6 3-9 6-3 2-8 1-5 9-8 4-5 4-7

Какие из этих графов содержат Эйлеровы циклы? Либо показать, что такого не существует. Найти число графов с V вершинами, которые содержат эйлеров цикл, для максимального числа V, для которого возможно выполнить реальные вычисления.

Вариант 30.

Тема: «Исследование алгоритма поиска в глубину на графе».

Задание: Реализовать алгоритм поиска в глубину на неориентированном графе. Граф представить в виде списка смежных вершин. Программа должна позволять возвращать размер связной компоненты. Представить трассировку вызовов рекурсивной функции поиска DFS для графа 0-2 0-5 1-2 3-4 4-5 3-5. Сделать чертеж дерева рекурсивных вызовов, соответствующего DFS.

Вариант 31.

Тема: «Исследование свойств алгоритма поиска в глубину на графе».

Задание: Реализовать алгоритм поиска в глубину на неориентированном графе. Граф представить в виде матрицы смежности. Программа должна выполнять трассировку поиска в глубину, которая будет производить классификацию каждого из двух представлений любого ребра графа на соответствие древесной связи, родительской связи, связи назад или связи вниз в дереве DFS. Представить трассировку поиска DFS для графа 0-2 0-5 1-2 3-4 4-5 3-5с классификацией связей.

Вариант 32.

Тема: «Исследование алгоритма раскраски графов».

Задание: Реализовать алгоритм для раскраски неориентированного графа в два цвета. Граф представить в виде списка смежных вершин. Программа должна определять, является ли исследуемый граф двудольным. Провести раскраску и определить является ли граф двудольным 0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8.

Вариант 33.

Тема: «Исследование алгоритма поиска мостов на графах».

Задание: Реализовать алгоритм определения реберной связности и поиска мостов на неориентированных графах. Граф представить в виде списка смежных вершин. Рассмотреть граф 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Начертить дерево стандартного DFS, которое использовать для поиска мостов и реберно-связных компонент.

Вариант 34.

Тема: «Исследование алгоритма поиска в ширину на графах».

Задание: Реализовать алгоритм поиска в ширину на неориентированных графах. Программа должна предусматривать вывод кратчайшего пути из любой вершины графа во все другие вершины. Построить матрицы всех кратчайших путей для графа: 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

Вариант 35.

Тема: «Исследование алгоритма рандомизированного поиска на графе».

Задание: Реализовать алгоритм рандомизированного поиска на неориентированных графах, который выбирает из накопителя то или иное ребро с равной вероятностью. Предложить три различных порядка обхода при рандомизированном поиске на графе 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Может ли рандомизированный поиск наносить визиты вершинам данного графа в порядке следования их индексов? Доказать правильность ответа.

Вариант 36.

Тема: «Исследование свойств алгоритма поиска в глубину на орграфе».

Задание: Реализовать алгоритм поиска в глубину на ориентированном графе. Граф представить в виде списка смежных вершин. Программа должна выполнять классификацию каждого ребра графа на соответствие древесной связи, родительской связи, связи назад или связи вниз в дереве DFS. Начертить лес DFS, который получается при применении поиска в глубину к орграфу 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

Вариант 37.

Тема: «Исследование алгоритма Уоршалла для построения транзитивного замыкания».

Задание: Реализовать алгоритм Уоршалла для построения транзитивного замыкания. Сколько ребер будет содержать транзитивное замыкание орграфа, который состоит только из простого ориентированного пути с V вершинами? Построить транзитивное замыкание для орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Провести эмпирические исследования с целью определить число ребер в транзитивном замыкании различных типов графов.

Вариант 38.

Тема: «Исследование алгоритма топологической сортировки орграфа».

Задание: Реализовать алгоритм топологической сортировки орграфа. Сколько и каких различных топологических сортировок возможно на графе DAG орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3?

Вариант 39.

Тема: «Исследование алгоритма обратной топологической сортировки орграфа».

Задание: Реализовать алгоритм обратной топологической сортировки орграфа. Сколько и каких различных обратных топологических сортировок возможно на графе DAG орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3?

Вариант 40.

Тема: «Исследование алгоритма топологической сортировки орграфа, основанной на очереди истоков».

Задание: Реализовать алгоритм топологической сортировки орграфа, основанный на очереди истоков. Покажите процесс топологической сортировки графа DAG 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3 с помощью алгоритма, использующего очередь истоков.

Вариант 41.

Тема: «Исследование алгоритма Косарайю для определения сильных компонент».

Задание: Реализовать алгоритм Косарайю для определения сильных компонент на орграфе. Описать, что произойдет и привести пример, когда данный алгоритм будет применен для: а) нахождения сильных компонент графа DAG; б) для нахождения сильных компонент орграфа, который состоит из одного цикла. Показать леса DFS и содержимое вспомогательных векторов, индексированных именами вершин, которые получаются для вычисления сильных компонент орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

Вариант 42.

Тема: «Исследование алгоритма Тарьяна для определения сильных компонент».

Задание: Реализовать алгоритм Тарьяна для определения сильных компонент на орграфе. Описать, что произойдет и привести пример, когда данный алгоритм будет применен для: а) нахождения сильных компонент графа DAG; б) для нахождения сильных компонент орграфа, который состоит из одного цикла. Показать леса DFS и содержимое стека во время выполнения алгоритма и окончательное содержимое векторов, индексированных именами вершин, которые получаются для вычисления сильных компонент орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

Вариант 43.

Тема: «Исследование алгоритма Габова для определения сильных компонент».

Задание: Реализовать алгоритм Габова для определения сильных компонент на орграфе. Описать, что произойдет и привести пример, когда данный алгоритм будет применен для: а) нахождения сильных компонент графа DAG; б) для нахождения сильных компонент орграфа, который состоит из одного цикла. Показать леса DFS и содержимое стека во время выполнения алгоритма и окончательное содержимое векторов, индексированных именами вершин, которые получаются для вычисления сильных компонент орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

Вариант 44.

Тема: «Исследование алгоритма Прима для построения дерева MST».

Задание: Реализовать алгоритм Прима для построения дерева MST. Представить результаты построения дерева MST с помощью данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).

Вариант 45.

Тема: «Исследование алгоритма Крускала для построения дерева MST».

Задание: Реализовать алгоритм Крускала для построения дерева MST. Представить результаты построения дерева MST с помощью данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).

Вариант 46.

Тема: «Исследование алгоритма Борувки для построения дерева MST».

Задание: Реализовать алгоритм Борувки для построения дерева MST. Представить результаты построения дерева MST с помощью данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).

Вариант 47.

Тема: «Исследование алгоритма Дейкстры для поиска кратчайших путей».

Задание: Реализовать алгоритм Дейкстры для поиска кратчайших рутей на сети. Представить результаты поиска кратчайших путей для данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).