Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 14
Текст из файла (страница 14)
В рассматриваемом примере из состояния А всостояние в можно перейти, только считав на входе строку s1.Между любыми двумя лексемами во входном файле может бытьпроизвольное число разделителей (пробелов и табуляций). Процедурапреобразования графа из внешнего формата во внутреннее представлениедолжна быть устойчива по отношению к ошибкам во входном файле, иуметь диагностировать ошибки ввода.Несмотря на ограничения, накладываемые на свойства графа в каждойконкретной задаче, библиотека считывания должна уметь обрабатыватьполный формат описания графа. Внутреннее представление графа такжестроится для полного формата. Если для решения конкретной задачисущественно более простое представление, оно может быть полученопутем преобразования из общего (библиотечного) представлениясредствами прикладной программы.Помимо функций считывания графа из файла и записи в файл, интерфейсбиблиотеки работы с графом должен предоставлять методы доступа квнутреннему представлению и его модификации.
Например:•••••76получить все вершины;получить свойства вершины по ее имени;получить все ребра, выходящие из данной вершины,получить свойства ребра по его имени;изменить цвет вершины;и т.д.Решение конкретной задачи должно включать визуализацию графа суказанием имен вершин и обозначенным решением. Например, еслинеобходимо найти путь на графе, то вершины и ребра, входящие в этотпуть, должны быть выделены цветом.Реализация библиотеки обработки графов включает спецификациювнутреннего представления и методов доступа к элементам графа, кодбиблиотеки и набор тестов на считывание графа для демонстрацииработоспособности библиотеки.
Решение задачи включает описаниеалгоритма, наличие нескольких, последовательно уточняемых прототипови визуализацию результатов решения.Список задач1. Минимальный путь в графе.Дана схема городского движения: дороги и перекрестки. Как добраться отодного заданного перекрестка до другого, проезжая минимальноеколичество перекрестков (найти самый короткий путь между заданнымивершинами графа)?1-ый прототип, найти все пути между заданными вершинами графа.Выдать все найденные пути в порядке возрастания длины.2-ой прототип: найти минимальный путь между заданнымивершинами графа.Ограничения на тип входного графа: не ориентированный, нераскрашенный, без весов, без условий.2. Оптимальный обход графа.Дана схема городского движения: дороги и перекрестки.
На перекрестках светофоры. Ремонтная бригада каждый день объезжает все светофоры спроверкой. Выработать оптимальный маршрут для бригады, предполагая,что после работы она возвращается в исходное место (у одного изсветофоров).1-ый прототип: найти произвольный обход графа, начиная состартовой вершины, выдавать путь и его длину.2-ой прототип, найти кратчайший обход в графе.Ограничения на тип входного графа, не ориентированный, нераскрашенный, без весов, без условий.3.
Самый «дешевый» путь между двумя вершинами на графе с весами.Дана схема транспортного сообщения между N городами: заданы ценыпроездов из i-го города в j-й город, 1<=i, j <= N, если города связаны77.напрямую. Как наиболее дешево добраться из одного заданного города вдругой?1-ый прототип: найти все пути между заданными вершинами графа ивыдать все найденные пути в порядке возрастания весов.2-ой прототип: найти самый «дешевый» путь между заданнымивершинами графа.Ограничения на тип входного графа: не ориентированный, нераскрашенный, без условий.4. Самый «дешевый» обход графа с весами.Начальник поручил рядовому коммивояжеру объехать N городов дляреализации товара и вернуться обратно с выручкой.
Города некоторымобразом связаны транспортным сообщением (известны цены билетов из iго города в j-й, 1 <= i, j <= N, если города связаны напрямую). Какобъехать все города, истратив минимум денег на дорогу?1-ый прототип: найти произвольный обход графа, начиная состартовой вершины, выдать путь и его стоимость.2-ой прототип: найти самый «дешевый» обход в графе, начав состартовой вершины графа и вернувшись в нее.Ограничения на тип входного графа: не ориентированный, нераскрашенный, без условий.5.
Раскраска двудольного графа.Раскрасить вершины двудольного графа в черный и белый цвета. (Графназывается двудольным, если все его вершины можно раскрасить в двацвета так, что каждое ребро графа соединяло бы вершины разного цвета.)1-ый прототип: раскрасить граф в черный и белый цвет ираспечатать список вершин с их цветами.2-ой прототип: выяснить, является ли граф двудольным и еслиявляется, то раскрасить его вершины в черный и белый цвет.Ограничения на тип входного графа: не ориентированный, без весов, безусловий.6.
Минимальная тестовая последовательность для конечногоавтомата.Регулярная грамматика представляется конечным автоматом, который всвою очередь представляется в виде ориентированного графа с условиями.Для простоты ограничимся лево-регулярной грамматикой. Граф сусловиями (диаграмма состояний) содержит условие перехода на каждомиз своих ребер, вершины являются состояниями конечного автомата. Этотграф удобно использовать для проверки принадлежности цепочки к языку,задаваемому грамматикой: выходя из стартовой вершины (стартовогосостояния), считывая по одному символу из цепочки и выполняясоответствующий переход в другое состояние, нужно, исчерпав цепочку,оказаться в специальном стоп-состояний.
Задача заключается в78нахождении цепочки минимальной длины, разбор которой покрывает всеребра графа.1-ый прототип: найти какую-нибудь входную последовательность,применение которой к конечному автомату позволило бы пройти повсем ребрам графа, и распечатать ее.2-ой прототип: найти минимальную входную последовательность ираспечатать ее. Ограничения на тип входного графа: нераскрашенный, без весов.7. Удаление циклов в ориентированном графе.Программа на Си состоит из набора модулей, которые связаны по импортупеременных. Возможны нежелательные кольцевые зависимости, когда,например, модуль А использует какую-нибудь переменную VI из модуля8, который в свою очередь использует переменную V2 из модуля А.Отношение межмодульной зависимости транзитивно.
Предложить вариантминимальной модификации программы (в терминах модулей: модуль Аотказывается от использования переменной VI из модуля В), чтобыисключить кольцевые зависимости.1-ый прототип: найти и напечатать все циклы.2-ой прототип: определить минимальное количество ребер, которыеразрывают все циклы.Ограничения на тип входного графа: не раскрашенный, без весов, безусловий.8. Недостижимые вершины в ориентированном графе.Дана схема дорог и перекрестков, причем все дороги - с одностороннимдвижением. Стартуя из заданного перекрестка, найти все перекрестки, ккоторым нельзя подъехать.1-ый прототип: найти и напечатать хотя бы одну вершину, недостижимую из стартовой вершины.2-ой прототип: найти и напечатать все вершины и ребра, недостижимые из стартовой вершины.Ограничения на тип входного графа: не раскрашенный, без весов, безусловий.9. Принадлежность цепочки языку.Регулярная грамматика представляется конечным автоматом, который всвою очередь представляется в виде ориентированного графа с условиями.Для простоты ограничимся лево-регулярной грамматикой.
Граф сусловиями (диаграмма состояний) содержит условие перехода на каждомиз своих ребер, вершины являются состояниями конечного автомата. Этотграф удобно использовать для проверки принадлежности цепочки к языку,задаваемому грамматикой: выходя из стартовой вершины (стартовогосостояния), считывая по одному символу из цепочки и выполняясоответствующий переход в другое состояние, нужно, исчерпав цепочку,79оказаться в специальном стоп-состоянии.
Используя представлениеграмматики в виде графа с условиями, осуществить проверку заданнойцепочки. Восстановить по графу текст грамматики.1-ый прототип: проверить цепочку на принадлежность к языку.описываемому графом и распечатать трассу обхода.2-ой прототип: по графу с условиями сгенерировать и распечататьтекст грамматики. Ограничения на тип входного графа: нераскрашенный, без весов.80Литература1. Haasan Gomaa. The Impact of prototyping on software system engineeringin lEEEComputer Society press tutorial 1990, 543-552.2. Barry W Boehm. A Spiral Model of Software Development andEnhancement in Software Engineering Project Management, 1987, 120-142.3. Alan M.
Davis, Edward H. Bersoff, Edward R.Comer A Strategy forComparising Alternative Software Development Life Cycle Models in IEEETransactions on Software Eng. Vol. SE-14, №10, Oct.1988,1453-1461.4. Harold Abelson, Gerald J. Sussman, Julie Sussman. Structure andInterpretation of Computer Programs. MIT Press. 1996.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
