Программирование на языке высокого уровня

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

Описание задачи.

Задан неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число K. Выделить в графе хотя бы одно ядро мощности K. При отсутствии таких ядер в графе выдать на экран сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденного ядра.

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

Задание на курсовую работу. Вариант 32.

Прикладная программа. Гомоморфизм графов.

Описание задачи.

Заданы два неориентированных графа и , где — множества вершин графов; — множества ребер. Проверить, можно ли последовательным отождествлением несмежных вершин графа получить граф . Предусмотреть графическое представление исходных графов и цветовое выделение отождествляемых вершин.

Операция отождествления вершин и заключается в их замене одной (общей) вершиной v так, чтобы все вершины, смежные и , остались смежны вершине v.

Задание на курсовую работу. Вариант 33.

Прикладная программа. Ориентированный диаметр графа.

Описание задачи.

Задан неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число . Ориентировать ребра графа G так, чтобы полученный в результате ориентированный граф имел диаметр не более K. При отсутствии такой возможности выдать на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и результирующего ориентированного графа.

Задание на курсовую работу. Вариант 34.

Прикладная программа. Надежность сети.

Описание задачи.

Задан неориентированный граф , где V — множество вершин; E — множество ребер. Ребра графа G взвешены рациональными числами , , задающими вероятности "исправного состояния" соответствующих ребер. Кроме того, дано положительное рациональное число . Проверить что любые две вершины графа G соединены хотя бы одним маршрутом без неисправных ребер с вероятностью не менее q. Предусмотреть графическое представление исходного графа и цветовое выделение "неисправных" ребер.

Задание на курсовую работу. Вариант 35.

Прикладная программа. Задача о подъемном кране.

Описание задачи.

Задан смешанный граф , где V — множество вершин; A — множество дуг; E — множество ребер, дуги и ребра которого взвешены положительными целыми числами. Кроме того, дано положительное целое число B. Проверить существует ли в графе G цикл длины не более B, включающий каждую дугу по крайней мере один раз и проходящий дуги только в "правильном" направлении (совпадающем с их ориентацией). Предусмотреть графическое представление исходного графа и цветовое выделение найденного цикла. При отсутствии цикла вывести на экран соответствующее сообщение.

Задание на курсовую работу. Вариант 36.

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

Описание задачи.

Составить программу для лексикографической сортировки цепочек символов в произвольном алфавите. Для сортировки использовать три метода: метод вычерпывания; метод быстрой сортировки; метод слияния. Алфавит, а также набор цепочек задаются пользователем либо с клавиатуры, либо из специального настроечного файла. Результат сортировки также, по выбору пользователя, записывается либо на экран, либо в специальный файл протокола. Метод сортировки выбирается пользователем с помощью меню. Предусмотреть изменение порядка сортировки.

Задание на курсовую работу. Вариант 37.

Прикладная программа. Разбиение графа на подграфы.

Описание задачи.

Составить программу для разбиения произвольного неориентированного графа на подграфы. При разбиении число подграфов должно быть минимально возможным. Число вершин в каждом подграфе не должно превышать заданного значения n. Количество связей каждого подграфа с остальными подграфами ограничено значением z. Исходный граф, а также значения n и z вводятся пользователем с клавиатуры. Предусмотреть графическое представление результатов разбиения графа с цветовым выделением формируемых подграфов.

Задание на курсовую работу. Вариант 38.

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

Описание задачи.

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

Остовным деревом графа называется любой связный ациклический частичный граф.

Задание на курсовую работу. Вариант 39.

Прикладная программа. Кратчайший путь.

Описание задачи.

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

Задание на курсовую работу. Вариант 40.

Прикладная программа. Сочетания, перестановки и размещения.

Описание задачи.

Составить программу для формирования сочетаний, перестановок и размещений из элементов заданного множества. Множество может состоять из элементов произвольной природы и задается пользователем с клавиатуры или из специального настроечного файла. Результаты работы программы выводятся либо на экран, либо в специальный файл протокола. Вид формируемого комбинаторного соединения (сочетание, перестановка или размещение) выбирается посредством меню. Предусмотреть реализацию нескольких алгоритмов формирования комбинаторных соединений. Выбор алгоритма также осуществляется через меню.

Задание на курсовую работу. Вариант 41.

Прикладная программа.
Оптимальная последовательность смежных элементов.

Описание задачи.

Задана квадратная матрица , содержащая положительные целые числа. Построить по матрице M последовательность, начинающуюся в элементе и оканчивающуюся в элементе , такую, что сумма модулей разностей смежных элементов этой последовательности минимальна. Предусмотреть графический вывод исходной матрицы на экран.

Элементы и считаются смежными, если или .

Задание на курсовую работу. Вариант 42.

Моделирующая программа.
Одноленточная детерминированная машина Тьюринга.

Описание задачи.

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

Задание на курсовую работу. Вариант 43.

Моделирующая программа.
Одноленточная недетерминированная машина Тьюринга.

Описание задачи.

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

Задание на курсовую работу. Вариант 44.

Моделирующая программа.
Многоленточная детерминированная машина Тьюринга.

Описание задачи.

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

Задание на курсовую работу. Вариант 45.

Моделирующая программа.
Многоленточная недетерминированная машина Тьюринга.

Описание задачи.

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

Задание на курсовую работу. Вариант 46.

Моделирующая программа.
Двухсторонний детерминированный магазинный автомат.

Описание задачи.

Разработать программу для моделирования работы двухстороннего детерминированного магазинного автомата (ДДМА) по произвольной программе. Программа ДДМА задается пользователем либо непосредственно с клавиатуры, либо из специального файла инициализации (форма представления программы произвольна). Предусмотреть текстовый и графический режимы отображения процесса функционирования ДДМА.

Задание на курсовую работу. Вариант 47.

Моделирующая программа.
Детерминированный конечный автомат.

Описание задачи.

Разработать программу для моделирования работы детерминированного конечного автомата (ДКА) с произвольной таблицей переходов. Таблица переходов ДКА задается пользователем либо непосредственно с клавиатуры, либо из специального файла инициализации (форма задания таблицы произвольна). Предусмотреть текстовый и графический режимы отображения процесса функционирования автомата. Рассматривать как полностью определенные, так и не полностью определенные ДКА.

Задание на курсовую работу. Вариант 48.

Моделирующая программа.
Недетерминированный конечный автомат.

Описание задачи.

Разработать программу для моделирования работы недетерминированного конечного автомата (НДКА) с произвольной таблицей переходов. Таблица переходов НДКА задается пользователем либо непосредственно с клавиатуры, либо из специального файла инициализации (форма задания таблицы произвольна). Предусмотреть текстовый и графический режимы отображения процесса функционирования автомата. Рассматривать как полностью определенные, так и не полностью определенные НДКА.

Задание на курсовую работу. Вариант 49.

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

Описание задачи.

Разработать программу для моделирования работы и проверки динамической корректности последовательных вычислительных алгоритмов. Корректность алгоритма определяется свойствами безызбыточности (отсутствие недостижимых операторов), реентерабельности (возможность перезапуска алгоритма после его прерывания в любой точке), отсутствия тупиков. Моделируемый алгоритм задается пользователем либо непосредственно с клавиатуры, либо из специального файла инициализации (форма представления алгоритма произвольна). Предусмотреть текстовый и графический режимы отображения процесса моделирования алгоритма. Если алгоритм некорректен, выдать на экран соответствующее сообщение с указанием источника некорректности.

Задание на курсовую работу. Вариант 50.

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

Описание задачи.

Разработать программу для моделирования работы и проверки динамической корректности параллельных вычислительных алгоритмов. Корректность параллельного алгоритма определяется свойствами безызбыточности (отсутствие недостижимых операторов), реентерабельности (возможность перезапуска алгоритма после его прерывания в любой точке), отсутствия тупиков, самосогласованности (невозможность запуска уже выполняемого оператора) и непротиворечивости (отсутствие условий, выполнение которых нарушает возможность выполнения других условий). Моделируемый алгоритм задается пользователем либо непосредственно с клавиатуры, либо из специального файла инициализации (форма представления алгоритма произвольна). Предусмотреть текстовый и графический режимы отображения процесса моделирования алгоритма. Если алгоритм некорректен, выдать на экран соответствующее сообщение с указанием источника некорректности.

Задание на курсовую работу. Вариант 51.

Игровая программа. Игра "Хакенбуш".

Описание игры.

При игре используется картинка, представляющая собой набор из нескольких отдельных графов, каждый из которых отображает определенный объект. Каждый граф стоит на некоторой базовой линии, называемой "землей", причем эта линия не является частью графа. Вершины, расположенные на земле, называются базовыми. Пример исходной картинки дан ниже.