Диплом Программирование

Предмет: Программирование на C++Builder

Тема или краткое описание работы: Программная реализация трансформационного метода для автоматов с непересекающимися циклами

Срoк сдачи: 4.05.2010

Вид работы: Дипломная

Tип работы: Теоретическая с практикой

Дополнительные требования: Здравствуйте. Необходимо написать программу, распадающаяся на два задания (на две подпрограммы). первый модуль нужно сдать 4 (узнал вчера об этом). Сама предзащита в конце мая Суть в следующем: есть некий метод, трансформационный, он позволяет проверять эквивалентность двух заданных графов, "прогоняя" каждый из графов на алгоритмы построения деревьев и сравнива деревья Примерно так: главное окно программы, на нем две канвы, мы там щелкаем кнопки "вершины и дуги" и рисуется граф. счелкаем проверить 1 граф – строится сначала дерево с однозначным покрытием, после чего из него выделяется деревянное покрытие 2 граф строится купол изоморфный деревянному покрытию дерева потоком. Если во время выполнения построения дерева во втором графе обнаруживается, что дерево совпадает, то идет до дерева потоков. если уже на начальной стадии нет – то программа пишет "Не эквивалентны" Желательно, чтобы он еще показывал что и как Графы желательно и нужно переводить в матрицы инцендентности (!!!) программа должна уметь очищать канву, показывать полученные деревья, вести хотябы краткий лог и показывать матрицы инцендентности Срочно нужно написать хотя бы один алгоритм в визуальной среде (до вторника) Описание трансофрмационного метода и примерные скриншоты могу предоставить Программа должна уметь выполнять алгоритмы: Построение графа с однозначным покрытием (алгоритм построения однозначного покрытия); Выделение деревянного покрытия; Построение купола изоморфного деревянному покрытию (перестановка, расклейка); Построение дерева потоков (нахождение альфа и бета сечения); Построение алгоритма с однозначным покрытием: Структуру алгоритма можно расписать так: 1. Помечаем вход автомата. 2. Выбрать помеченную вершину и все выходящие из нее дуги. 2.1. Если дуга ведет в непомеченную вершину, то помечаем дугу и вершину; 2.2. Если дуга ведет в помеченную вершину, то: 2.2.1. Если дуга не нарушает однозначность вершины, то помечаем ее. 2.2.2. Если дуга нарушает однозначность вершины, то: 2.2.2.1. направить ее в другие существующие копии вершины, если копия существует, причем с сохранением однозначности, 2.2.2.2.иначе создать копию вершины и дугу направить в нее. Выходящие дуги направить туда, куда ведут дуги из копируемой вершины. и из него выделение деревянного покрытия вот желательно 1й и второй алгоритм (однозначное покрытие и деревянное из него) в отдельной программе ко вторнику.