Второе домашнее задание. Алгоритмы на графах (1127077)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Домашнее задание 2.Алгоритмы на графахОбщее описание заданияЗадание направленно на проверку знаний структур данных для представленияграфов, а также приобретение навыков реализации различных алгоритмов на графах.Задание состоит из следующих этапов:1.написание ряда алгоритмов для работы с графами (см. описание ниже);2.проведение тестирования написанной программы с точки зрениякорректности работы программы;3.теоретический анализ времени работы реализованных алгоритмов и замерыпроизводительности полученных реализаций указанных алгоритмов;4.написание отчета, описывающего результаты всех указанных этапов.Для выполнения задания предполагается использовать систему контроля версий Git.Каждый студент должен создать отдельный проект на сайте http://mks1.cmc.msu.ru/ идобавить меня в проект для осуществления выполнения задания.

Проект должен иметьследующее название: «[SurnameNS] – Autumn 2014 – HW2», где [SurnameNS] – это вашафамилия и инициалы на английском языке (например, IvanovSI). Задания, выполненныебез использования системы Git и соответствующего сайта проверяться не будут. Любыевопросы (в том числе, если у Вас есть возражения, связанные с использованием Dropbox)по заданию присылать по электронной почте на следующий адрес:mikle.shupletsov@gmail.com. Тема письма имеет следующий формат: [318] [Фамилия Имя][Вопрос].Для ускорения проверки задания, Вы может в системе GitLab сделатьсоответствующий ticket на мое имя, таким образом, я буду понимать, что Вы закончиливыполнение задания и его можно проверять.Срок выполнения задания: до конца семестра.Формат входных данных.Предполагается, что на вход программы подается ориентированный разреженныйсвязанный граф с неотрицательными весами на ребрах.

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

Все элементы разделены пробелами.Пример корректного входного описания графа:430 1 0.21 2 10.342 3 5.4Реализуемые алгоритмыПредполагается, что Ваша программа реализует следующий набор алгоритмов для работыс графами:1. поиск и подсчет числа сильно связанных компонент графа;2. подсчет числа ориентированных путей между заданной парой вершин графа;3. поиск минимального остовного дерева (предполагается, что в графе существуетединственное минимальное остовное дерево).При каждом запуске программы должен выполняться только один из представленныхалгоритмов.

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

При этом в каждой строке номера вершин упорядочены повозрастанию и разделены пробелами, а сами строки упорядочены по возрастаниюминимального номера вершины. Например, для графа, который содержит следующиесильно связанные компоненты {1,3,5}{2,6,7}{4,8,9,10} программа должна выдатьследующее:31 3 52 6 74 8 9 10Подсчет числа путей между заданной парой вершинНа выходе одна строка, которая содержит три числа, разделенных пробелом.

Сначалауказывается первая вершина и вторая вершина, между которыми производится поискчисла путей, а потом указывается само число путей. Например, если между вершиной сномером 10 и вершиной с номером 35 в граве существует 150 путей, то программа должнавыдать следующее:10 35 150Поиск минимального остовного дереваПервая строка содержит целое число M – число ребер в минимальном остовном дереве,вторая строка содержит вещественное число V – суммарный вес всех ребер минимальногоостовного дерева. Остальные M строк содержат пары номеров вершин, задающие ребраминимального остовного дерева. При этом сначала указывается номер вершины, изкоторой ребро исходит, а потом номер вершины, куда приходит ребро.

Номера вершинразделены пробелом. Кроме того, список ребер упорядочен лексикографически.Например, для графа, который содержит следующее минимальное остовное дерево веса10.23 и состоящее из ребер (0,1), (1,2), (0,3), (3,4) и (4,5) программа должна выдатьследующее:510.230 10 31 23 44 5Параметры командной строки.Программа должна поддерживать следующие параметры командной строки:1. –-help, -h – при передаче этого параметра программа должна вывести краткуюсправку о работе с программой, которая включает краткое описание программы, атакже все параметры командной строки и их назначение;2. –-input_file “filename.txt”, -I “filename.txt” – если указан этотпараметр, то программа считывает вход из файла с именем “filename.txt”,если параметр не указан, то считывание происходит со стандартного потока ввода(cin);3.

–-output_file “filename.txt”, -O “filename.txt”, -O - еслиуказан этот параметр, то программа записывает результат работы в файл с именем“filename.txt”, если параметр не указан, то запись происходит в стандартныйпоток вывода (cout);4. –-algorithm (S|P|T), -a (S|P|T)– параметр определяет типисполняемого алгоритма (в скобках указан тип исполняемого алгоритма: S – поиски подсчет числа сильно связанных компонент графа, P – поиск числа путей междузаданной парой вершин, T – поиск минимального остовного дерева).5. –-input_vertex “vertex_index”, -i “vertex_index” – параметропределяет номер вершины, из которой исходят пути при реализации алгоритмаподсчета числа путей (для других алгоритмов этот параметр игнорируется);6. –-output_vertex “vertex_index”, -o “vertex_index” – параметропределяет номер вершины, из которой исходят пути при реализации алгоритмаподсчета числа путей (для других алгоритмов этот параметр игнорируется);Тестирование программы и замеры производительности.Программа должна быть протестирована на предмет корректного решенияпоставленной задачи, корректного считывания входного и генерации выходного форматовпредставления лабиринта и минимального пути в нем.Должно быть проведено тестирование программы на случайно сгенерированныхлабиринтах разного размера.

Для генерации случайных графов предполагается написатьсоответствующую программу. Установить максимальные значения параметров лабиринта,при которых программа работает за приемлемое время (меньше одной минуты) и непревышает заданных ограничений по памяти (например, память Вашего компьютера) дляразных форматов описания лабиринта. Сравнить полученные данные с теоретическойоценкой времени работы реализованного Вами алгоритма поиска пути.Полученные каждым студентом тесты, будут собраны в общую библиотеку тестов,которая будет использоваться для тестирования всех программ. Тесты, которые позволилинайти ошибки в чужих программах, будут давать студентам дополнительные баллы.Требования к отчетуОтчет по заданию должен содержать следующие основные разделы:1 Введение.2 Описание алгоритма.3 Результаты тестирования и замеры производительности.4 Список литературы.Раздел «Введение» содержит постановку задачи и краткое описание полученныхрезультатов.Раздел «Описание алгоритма» содержит описание реализованных алгоритмов дляработы с графами и теоретическую оценку времени их работы.Раздел «Результаты тестирования и замеры производительности» содержитописания того, как написанная программа тестировалась с точки зрения корректностирешения задачи, и результаты сравнения скорости работы программы на различныхвходных данных с теоретической оценкой времени работы алгоритма.

Для наглядноститребуется привести не только таблицы, но и графики. Кроме того, в этом разделе долженбыть приведен анализ полученных замеров производительности.Раздел «Список литературы» содержит ссылки на статьи и электронные ресурсы,если таковые были упомянуты в тексте отчета.Критерии оценкиРезультаты выполнения домашнего задания оцениваются по следующим основнымкритериям:1 корректность и качество реализации алгоритмов;2 правильность считывания входных форматов и генерации выходных форматов;качество оформления кода (styleguide);3 тестирование программы и анализ производительности;4 структура и содержание отчета;5 использование системы контроля версий..

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы