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

Цель курсовой работы — изучение приемов формализации, составления алгоритмов и программирования при решении прикладных задач, а также глубокое овладение языком программирования C++ и приемами программирования в интегрированной среде Borland C++ Builder 5. x-6.x.

Задачи, решаемые в ходе выполнения курсовой работы:

Получение точных формулировок решаемых вопросов.

Нахождение оптимальных путей решения.

Разбиение исходной задачи на ряд более мелких подзадач.

Составление алгоритмов решения подзадач.

Написание программы на языке C++.

Отладка и тестирование программы.

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

Общие требования к курсовой работе.

Работа представляется в виде документа, называемого пояснительной запиской.

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

Пояснительная записка оформляется в соответствии с ГОСТ на условные обозначения элементов схем алгоритмов и программ (ГОСТ 19.701−90), а также методическими указаниями к составлению и оформлению отчета (№ 358 аб; № 643 ч.з.).

Пояснительная записка должна быть скреплена.

Нумерация страниц пояснительной записки осуществляется с титульного листа, номер страницы на котором не ставится.

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

Форма задания на курсовую работу

Утверждаю:

зав. кафедрой ВТ Титов В.С.

Задание на курсовую работу по дисциплине.

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

Тема работы: _________________________________________________.

_____________________________________________________________.

Студент: Ф.И.О. группа ВМ-91.

Дата выдачи задания: 18.02.2010.

Срок представления к защите: 01.06.2010.

Исходные данные для работы: язык программирования C++, среда разработки программ Borland C++ Builder, компьютер класса IBM PC AT, описание решаемой задачи.

Содержание пояснительной записки:

• 1) цель курсовой работы;
• 2) концептуальное или формализованное описание задачи;
• 3) формализованное представление концептуальной модели (при необходимости);
• 4) уточненное техническое задание (на настоящем бланке);
• 5) общая структура программы;
• 6) алгоритмы отдельных (наиболее важных) модулей;
• 7) результаты отладки и тестирования программы (описание методов отладки и примеры тестов);
• 8) результаты работы программы;
• 9) выводы;
• 10) библиографический список;
• 11) приложения (листинги программных модулей, распечатки результатов, графики, таблицы и т. д., включая инструкцию для пользователя).

Перечень графического материала:

• 1) схема иерархической подчиненности программных единиц;
• 2) граф-схемы алгоритмов отдельных подпрограмм.

Руководитель работы: Ф.И.О. руководителя Задание принял к исполнению Ф.И.О. студента.

Требования к программам

Игровые программы.

В пояснительной записке п. 3 вместо формализованного представления концептуальной модели включает два следующих подпункта:

• 3.1) описание стратегии игры на выигрыш для ЭВМ, если первый ход делает ЭВМ;
• 3.2) описание стратегии игры на выигрыш или ничью для ЭВМ, если игру начинает не ЭВМ.

В перечне графического материала добавляется п.3: сценарий диалога с пользователем.

Прочие требования.

В процессе игры недопустимый ход человека должен отклоняться.

Управление перемещением объектов должно быть удобным для игрока.

В любой момент игры игрок должен иметь возможность обратиться за справкой о допустимых ходах.

В меню должно быть краткое описание игры и ее правил.

В любой момент по инициативе игрока он может прервать игру.

После окончания игры ЭВМ должна выдавать сообщение о результате игры и предложить либо начать новую игру, либо выйти из программы.

Предусмотреть демонстрационный пример.

Прикладные программы.

Для программ обработки графов предусмотреть ввод и вывод графов в графическом режиме.

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

Моделирующие программы.

Составить структурную схему модели (схема должна быть в пояснительной записке).

В процессе моделирования предусмотреть останов и выход с распечаткой промежуточных результатов.

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

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

Выводы и предложения по усовершенствованию моделируемой системы.

Обучающие программы

В пояснительной записке п. 3 вместо формализованного представления концептуальной модели включает два следующих подпункта:

• 3.1) описание стратегии обучения;
• 3.2) описание методики оценки знаний обучаемого.

В перечне графического материала добавляется п.3: сценарий диалога с пользователем.

Прочие требования.

В процессе обучения недопустимый ход обучаемого должен отклоняться.

Управление программой должно быть удобным как для обучаемого, так и для преподавателя, контролирующего обучение.

В любой момент обучаемый должен иметь возможность обратиться за справкой.

В любой момент по инициативе обучаемого он может прервать обучение.

После окончания обучения ЭВМ должна выдавать сообщение о результатах обучения.

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

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

Игровая программа. Топологическая игра

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

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

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

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

Игровая программа Описание игры.

Тридцать две фишки расставляются так, как показано ниже, на все клетки, кроме центральной.

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

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

Игровая программа. Игра «Бридж-ит»

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

Полем для игры служат два «симметрично вложенных» друг в друга прямоугольника, А и В размером m (m1) каждый, заполненные соответственно кружками и крестиками:

Играют два игрока. Первому из них соответствует прямоугольник (поле) А, второму — прямоугольник В. Элементы поля, А — кружки, поля В — крестики. Очередной ход заключается в том, чтобы соединить два смежных элемента своего поля горизонтальным или вертикальным отрезком прямой, не пересекая ранее проведенных отрезков противника. Ходы делаются поочередно. Выигрывает тот, кто первым построит ломаную, соединяющую две противоположных вершины своего прямоугольника.

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

Игровая программа. Игра «Гекс» на неориентированном графе

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

В игре участвуют два игрока. Полем для игры служит произвольный неориентированный граф, где V — множество вершин; E — множество ребер. В начале игры в графе G выделяются две произвольные вершины s и t. Далее игроки поочередно выбирают по одной вершине из множества; вершины, выбранные игроком 1, «окрашиваются» при этом в синий цвет, а выбранные игроком 2 — в красный. Игра продолжается до тех пор, пока не будут окрашены все вершины из множества. Игрок 1 (игрок 2) выигрывает тогда и только тогда, когда в графе G найдется маршрут из s в t, проходящий только через синие (красные) вершины.

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

Игровая программа. " Переключательная игра Шеннона на ребрах"

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

В игре участвуют два игрока. Полем для игры служит произвольный неориентированный граф, где V — множество вершин; E — множество ребер. В начале игры в графе G выделяются две произвольные вершины s и t. Далее игроки поочередно выбирают по одному ребру из множества E; ребра, выбранные игроком 1, «окрашиваются» при этом в зеленый цвет, а выбранные игроком 2 — в красный. Игра продолжается до тех пор, пока не будут окрашены все ребра из множества E. Игрок 1 (игрок 2) выигрывает тогда и только тогда, когда в графе G найдется маршрут из s в t, содержащий только зеленые (красные) ребра.

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

Игровая программа. Игра «Гекс» на ориентированном графе

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

В игре участвуют два игрока. Полем для игры служит произвольный ориентированный граф, где V — множество вершин; A — множество дуг (ориентированных ребер). В начале игры в графе G выделяются две произвольные вершины s и t. Далее игроки поочередно выбирают по одной вершине из множества; вершины, выбранные игроком 1, «окрашиваются» при этом в черный цвет, а выбранные игроком 2 — в белый. Игра продолжается до тех пор, пока не будут окрашены все вершины из множества. Игрок 1 (игрок 2) выигрывает тогда и только тогда, когда в графе G найдется путь (ориентированный маршрут) из s в t, проходящий только через черные (белые) вершины.

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

Игровая программа. Игра «Обобщенная география»

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

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

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

Игровая программа. Игра «Кейли»

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

В игре участвуют два игрока. Полем для игры служит произвольный неориентированный граф, где V — множество вершин; E — множество ребер. Игроки поочередно выбирают по одной вершине из множества V, причем выбранная вершина и все ей смежные выбрасываются из графа. Выигрывает тот из игроков, кто удалит из графа последнюю вершину.

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

Игровая программа. Игра «Максимальное взвешенное паросочетание»

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

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

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

Игровая программа. Игра «Накрывающее множество»

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

В игре участвуют два игрока. «Полем для игры» служит семейство подмножеств C некоторого (базисного) множества B. Игроки поочередно выбирают новые элементы из множества B до тех пор, пока для каждого подмножества из C не будет выбран хотя бы один элемент. Игрок, ход которого приводит к этой ситуации, проигрывает.

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

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

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

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

Вершинным покрытием графа называется подмножество его вершин такое, что хотя бы один конец каждого ребра из множества E принадлежит .

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

Прикладная программа. Выделение доминирующего множества графа

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

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

Доминирующим множеством графа называется подмножество его вершин такое, что каждое ребро из множества E имеет один конец в подмножестве, а другой — в подмножестве .

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

Прикладная программа. Выделение семейства доминирующих подмножеств в графе

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

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

Доминирующим подмножеством графа называется подмножество его вершин такое, что каждое ребро из множества E имеет один конец в подмножестве, а другой — в подмножестве .

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

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

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

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

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

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

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

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

Полный (под)граф — граф, в котором все вершины попарно смежны.

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

Прикладная программа. Множество вершин, разрезающих контуры

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

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

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

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

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

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

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

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

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

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

Полным называется (под)граф, в котором каждая пара вершин соединена ребром.

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

Прикладная программа. Выделение клики

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

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

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

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

Прикладная программа. Выделение независимого множества графа

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

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

Под независимым множеством неориентированного графа понимается всякое максимальное подмножество его множества вершин, в котором ни одна пара вершин не соединяется ребром.

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

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

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

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

Планарный граф — граф, который можно изобразить на плоскости без пересечения ребер.

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

Прикладная программа. Кубический подграф

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

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

Кубическим называется (под)граф, степени всех вершин которого равны либо 3 либо 0.

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

Прикладная программа. Гамильтонов цикл

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

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

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

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

Прикладная программа. Гамильтонов путь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прикладная программа. Самый длинный цикл

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

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

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

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

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

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

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

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

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

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

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

Прикладная программа. Покрытие битового образа прямоугольниками

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

Заданы (0−1)-матрица M порядка и положительное целое число K. Проверить, возможно ли покрытие всех единичных элементов матрицы M не более чем K прямоугольниками. Исходную матрицу и вариант покрытия представить графически.

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

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

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

Задан неориентированный граф, где 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.

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

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

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

В игре участвуют два игрока. Они по очереди убирают (стирают) с рисунка по одному ребру. При стирании ребра, соединяющего какую-то часть графа с базовой линией, эта часть исчезает, т. е. также стирается («падает на землю»). Например, если убрать на рисунке ребро А, то исчезнут и паук и окно (они оба упадут на землю). Если удалить ребро С, то исчезнет только паук. Убирая ребро В, можно срубить всю яблоню. Если убрать одно из ребер в основании фонаря (D или E), то фонарь все же останется стоять, но если при следующем ходе убрать и второе ребро основания, то фонарь опрокинется и исчезнет. Побеждает в игре тот, кто убирает на картинке последнее ребро.

Замечания:

Исходная картинка вводится игроком.

Картинка может содержать графы с петлями; между двумя вершинами могут быть несколько ребер.

Максимальный размер поля картинки 2035 точек.

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

Игровая программа. Игра «ним Норткотта»

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

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

Пример:

Черная шашка 1 не имеет хода, белая шашка 1 может ходить назад на любое поле в данном столбце в пределах доски. Для шашек 3 хода вперед нет. Черная шашка 3 может отступить на одну клетку в столбце 3, а белая шашка 3 имеет 5 возможных ходов назад в столбце 3.

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

Игровая программа. Игра «Французская Хальма»

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

Для игры используется обычная шахматная доска. Играют двое партнеров. Каждый игрок в начале игры размещает свои фишки на определенных клетках, которые называются «домом». При этом у игроков имеется по 10 одинаковых фишек, цвет которых у каждого из соперников разный. Один из домов размещается в левом нижнем углу доски, а другой — в правом верхнем углу. Выигрывает тот, кто первым переместит все свои фишки в дом соперника.

Играющие ходят по очереди, перемещая на доске при каждом ходе только одну фишку. В процессе игры разрешается делать ходы двух типов: 1) «шаг» — ход на любую из восьми соседних клеток; 2) «прыжок» — скачок через фишку в любом направлении. Фишка, через которую совершается прыжок, остается на месте. Несколько прыжков подряд рассматриваются как один ход. При этом разрешается перепрыгивать любое число своих и чужих фишек. Совершать прыжок необязательно, даже если он возможен. Каждый из соперников может остановиться после любого прыжка. Один и тот же ход не может включать и шаги и прыжки.

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

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

Прикладная программа. Нахождение кратчайшего пути алгоритмом Левита

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

Составить программу для нахождения в заданном взвешенном неориентированном графе кратчайшего пути между двумя заданными вершинами алгоритмом Левита [5, c.166−167]. Предусмотреть графическое представление исходного графа и цветовое выделение найденного кратчайшего пути.

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

Прикладная программа. Нахождение кратчайшего дерева путей

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

Составить программу для нахождения в заданном взвешенном неориентированном графе кратчайшего дерева путей от заданной вершины [5, c.170−173]. Предусмотреть графическое представление исходного графа и цветовое выделение найденного кратчайшего дерева путей.

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

Обучающая программа. Основы теории графов

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

Составить программу для обучения студентов основам теории графов [6−9]. Программа должна включать информирующую функцию (выдача кратких сведений по темам обучения), оценочную функцию (тестирование знаний обучаемого с выдачей оценки), поисковую функцию (поиск данных по требуемой теме). Предусмотреть вывод текстового и иллюстративного графического материала. Состав тем, структура курса обучения, а также методика оценки знаний обучаемого согласовываются с преподавателем.

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

Обучающая программа. Комбинаторика

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

Составить программу для обучения студентов основам комбинаторной теории [5,10,13]. Программа должна включать информирующую функцию (выдача кратких сведений по темам обучения), оценочную функцию (тестирование знаний обучаемого с выдачей оценки), поисковую функцию (поиск данных по требуемой теме). Предусмотреть вывод текстового и иллюстративного графического материала. Состав тем, структура курса обучения, а также методика оценки знаний обучаемого согласовываются с преподавателем.

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

Обучающая программа. Теория автоматов

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

Составить программу для обучения студентов основам теории автоматов [4,11,12]. Программа должна включать информирующую функцию (выдача кратких сведений по темам обучения), оценочную функцию (тестирование знаний обучаемого с выдачей оценки), поисковую функцию (поиск данных по требуемой теме). Предусмотреть вывод текстового и иллюстративного графического материала. Состав тем, структура курса обучения, а также методика оценки знаний обучаемого согласовываются с преподавателем.

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

Обучающая программа. Элементы теории вероятностей

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

Составить программу для обучения студентов основам теории вероятностей [5,14,15]. Программа должна включать информирующую функцию (выдача кратких сведений по темам обучения), оценочную функцию (тестирование знаний обучаемого с выдачей оценки), поисковую функцию (поиск данных по требуемой теме). Предусмотреть вывод текстового и иллюстративного графического материала. Состав тем, структура курса обучения, а также методика оценки знаний обучаемого согласовываются с преподавателем.

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

Обучающая программа. Язык программирования C++

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

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

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

Моделирующая программа. Система массового обслуживания. Модель дозаправки самолетов в воздухе

После выполнения задания самолеты производят дозаправку в воздухе. В районе дозаправки постоянно дежурят 4 самолета-дозаправщика. Среднее время дозаправки одного самолета равно 10 минут. Плотность потока самолетов, нуждающихся в дозаправке, составляет 0.4. Если самолет, нуждающийся в дозаправке, застает все дозаправщики занятыми, он может некоторое время ожидать их освобождения в районе дозаправки. Среднее время ожидания дозаправки 20 минут. Самолет, не дождавшийся дозаправки, производит посадку на запасной аэродром. Если самолет дозаправлен, он производит посадку на основной аэродром. Смоделировать процесс дозаправки самолетов в течение N часов. В ходе моделирования выяснить среднее число дозаправленных самолетов, вероятность того, что самолет будет дозаправлен, среднее число самолетов, ожидающих дозаправки в воздухе, среднее время ожидания самолета в очереди на дозаправку.

Литература

: [15,16].

Задание на лабораторную работу. Вариант 62.

Моделирующая программа. Система массового обслуживания. Модель дисплейного центра

В вычислительном центре (ВЦ) соединено 100 дисплеев, работающих в online-режиме круглосуточно. Каждый дисплей включается в работу с ВЦ в среднем 20 раз в сутки независимо от работы других дисплеев. Каждое включение дисплея в работу в ВЦ длится случайное время, распределенное по показательному закону с параметром M=288 (1/сутки), независимо от того, сколько дисплеев работает. Поток включений каждого дисплея простейший. Промоделировать работу ВЦ в течение K суток. В процессе моделирования определить вероятность того, что число общающихся с ВЦ дисплеев не превысит 10. Проанализировать зависимость числа включенных дисплеев от времени при условии, что в начальный момент ни один дисплей не работал.

Литература

: [15,16].

Задание на лабораторную работу. Вариант 63.

Моделирующая программа. Система массового обслуживания. Модель информационно-логической машины

На информационно-логическую машину поступает простейший поток групповых сообщений. Число сообщений в группе может меняться от одного до четырех. Закон распределения числа сообщений в группе равномерный. Плотность поступления групп сообщений равна одной группе в единицу времени. Машина может одновременно обрабатывать два сообщения, а остальные, застав оба канала обработки информации машины занятыми, становятся в очередь. В очереди может находиться не более двух сообщений. Один канал машины способен обрабатывать в среднем два сообщения в единицу времени. Информация со временем теряет ценность. Время, в течение которого она считается еще годной для обработки, случайно и имеет показательный закон распределения с параметром V=1. Промоделировать работу машины в течение H часов. Определить вероятность того, что информация будет обработана, вероятность того, что информация не будет своевременно обработана до конца, а также вероятность того, что сообщения, ожидающие в очереди, потеряют ценность до того, как начнется их обработка в машине.

Литература

: [15,16].

Задание на лабораторную работу. Вариант 64.

Моделирующая программа. Система массового обслуживания. Модель заставы

На заставе, где взимается подорожный сбор, находятся семь касс. Каждая из них может обслужить автомобиль в среднем за 15 секунд. Застава работает круглосуточно. С 19.00 до 15.00 открыты 4 кассы и ни один автомобиль не стоит в очереди. Однако средняя дневная пропускная норма автомобилей через заставу возрастает после полудня и падает вечером согласно следующей таблице:

Можно считать, что в пределах каждого периода времени поток машин является пуассоновским. При увеличении потока автомобилей для уменьшения простоев в 16.30 открывают пятую кассу, а в 17.00 открывают оставшиеся две кассы. Промоделировать работу заставы в течение нескольких суток. Определить загрузку касс и среднее число автомобилей, ожидающих в очереди на заставе на каждом из интервалов времени, показанных в таблице.

Задание на лабораторную работу. Вариант 65.

Моделирующая программа. Система массового обслуживания. Модель производственного цеха

В производственном цехе работают три одинаковых станка. Во всех станках используется деталь, которая время от времени выходит из строя. Как только деталь отказывает, соответствующий станок необходимо выключить. Отказавшую деталь вынимают и на ее место ставят исправную запасную деталь сразу же или как только это станет возможным, и станок вновь включают. Неисправные детали ремонтируют и после ремонта используют снова. Время работы детали распределено по нормальному закону со средним 350 часов и стандартным отклонением 70 часов. Съем отказавшей детали со станка занимает 4 часа. Время установки новой детали составляет 6 часов. Время ремонта неисправной детали распределено по нормальному закону со средним и стандартным отклонением соответственно 8 часов и 0.5 часов. Ремонтом отказавших деталей занимается механик. В его обязанности входит также ремонт некоторых других деталей, поступающих из другого цеха. Эти другие детали поступают по закону Пуассона со средним интервалом между поступлениями 9 часов. Время их ремонта составляет 84 часа. Они имеют более высокий приоритет при ремонте, чем неисправные детали, используемые в рассматриваемых станках. Все три станка не зависят друг от друга за исключением процесса распределения деталей. Имеются только две запасные детали. Смоделировать работу цеха в течение N лет, рассматривая 40-часовую рабочую неделю. Определить степень загрузки станков и механика. Найти среднюю часовую стоимость системы как сумму стоимости простоя станков и стоимости ожидания ремонта другими деталями. Считать, что стоимость простоя станка составляет 25 долларов в час, а стоимость ожидания ремонта другими деталями равна 5 долларам в час для каждой детали.

Литература

: [15,16].

Задание на лабораторную работу. Вариант 66.

Моделирующая программа. Система массового обслуживания. Модель химчистки

В пункте химчистки работают две приемщицы. В среднем за 40-часовую рабочую неделю в приемный пункт обращается 480 клиентов, дожидающихся обслуживания. Среднее время обслуживания клиента — 5 минут. Поток клиентов простейший, а время их обслуживания распределено по показательному закону. Промоделировать работу химчистки в течение рабочей недели. Найти вероятность полного простоя пункта и вероятность наличия очереди. Проанализировать, как будет изменяться вероятность наличия очереди при постепенном уменьшении среднего времени обслуживания клиента до 4 минут с шагом в 10 секунд (построить график).

Задание на лабораторную работу. Вариант 67.

Моделирующая программа. Система массового обслуживания. Модель продовольственного магазина

Продовольственный магазин состоит из трех прилавков и основной кассы при выходе. Кроме того, на выходе из магазина имеется экспресс-касса. Покупатели приходят в магазин в соответствии с распределением Пуассона. Среднее значение интервала прихода составляет 75 с. Войдя в магазин, каждый покупатель берет корзинку и может обойти один или несколько прилавков, отбирая продукты. Время, требуемое для обхода прилавка, и число покупок, выбранных у прилавка, распределены равномерно в соответствии с таблицей:

После того как товар отобран, покупатель становится в конец очереди к основной кассе. Стоя в очереди, покупатель может захотеть сделать еще 21 покупки. Покупатели с тремя и меньшим числом покупок (не считая возможной дополнительной покупки) пользуются экспресс-кассой. Все другие покупатели проходят через обычную кассу. Если у контролера экспресс-кассы нет работы, то покупателю из начала очереди у основной кассы разрешается перейти к экспресс-кассе. Время обслуживания покупателя в любой кассе пропорционально числу сделанных покупок, на одну покупку уходит 3 с проверки. После оплаты продуктов покупатель оставляет корзинку и уходит. Построить модель, описывающую процесс покупок в продовольственном магазине. Провести моделирование N 8-часовых рабочих дней. Определить нагрузку кассиров и максимальные длины очередей перед кассой. Найти необходимое количество корзинок для бесперебойной работы магазина. Как изменятся указанные характеристики, если среднее значение интервала прихода покупателей составит T (T₀30) с? Литература: [15,16].

Задание на лабораторную работу. Вариант 68.

Моделирующая программа. Система массового обслуживания. Модель ремонтного ателье

Ателье по ремонту различной радиоаппаратуры имеет 5 мастеров. В среднем в течение рабочего дня (он составляет 7 часов) от населения поступает в ремонт 10 радиоаппаратов. Поток заявок на ремонт аппаратуры является пуассоновским. Статистика показала, что в среднем в течение рабочего дня каждый из мастеров в ателье успевает отремонтировать 2.5 радиоаппарата. Смоделировать работу ателье в течение N рабочих дней. Найти вероятность того, что все мастера свободны от ремонта, среднее время обслуживания каждого прибора в ателье, среднюю длину очереди заявок на ремонт, среднее время ожидания каждого неисправного аппарата в начале ремонта.

Литература

: [15,16].

Задание на лабораторную работу. Вариант 69.

Моделирующая программа. Система массового обслуживания. Модель работы станка

В станке используют две детали, А и В, которые периодически выходят из строя. Как только деталь, А или В отказывает, станок отключают. Затем отказавшую деталь вынимают, вместо нее ставят исправную запасную (если она имеется или как только она появится) и станок вновь включают. И деталь А, и деталь В можно отремонтировать и использовать снова. Время работы деталей, А и В распределено по нормальному закону со средним и стандартным отклонением соответственно: А — 350 час и 70 час; В — 450 час и 90 час. Съем любой отказавшей детали со станка занимает 4 час, а установка заменяющей ее детали этого же типа требует 6 час. Время ремонта неисправной детали, А распределено по нормальному закону со средним 8 час и стандартным отклонением 0.5 час, а время ремонта детали В в соответствии с таблицей:

Ремонт деталей, А и В в порядке их поступления выполняет механик. Кроме того, он ремонтирует другие детали, имеющие при ремонте высший приоритет. Эти другие детали поступают по закону Пуассона со средним интервалом 9 час. Время, требуемое на их ремонт, составляет 84 час. Имеется две запасные детали типа, А и одна запасная деталь типа В. Смоделировать работу станка в течение N лет, считая, что рабочая неделя состоит из 40 час. Определить загрузку станка, загрузку механика, среднюю длину очереди деталей к механику.

Литература

: [15,16].

Задание на лабораторную работу. Вариант 70.

Моделирующая программа. Система массового обслуживания. Модель парикмахерской

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