Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105



Скачать 20.91 Kb.
Дата04.07.2013
Размер20.91 Kb.
ТипКурсовая
Рецензия № 6

Функциональное программирование

Курсовая работа

Определение эйлерова пути на Прологе

Халипский Сергей Николаевич Специальность:230105

Зеленогорск ze072hsn 84 Форма:З

2000

Проверил Зюзьков Валентин Михайлович
Оценка: не зачтена

Комментарий

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

Понятие эйлерова пути возникло в восемнадцатом столетии, когда известный математик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рисунке 1. Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра – с мостами, которыми связаны эти части.









gffffff



Рисунок 1 Модель задачи о мостах Кенигсберг
Может ли пешеход обойти все мосты, пройдя по каждому из них только один раз? Эта задача увлекла великого математика и в 1736 году Эйлер доказал ее неразрешимость.
Как видите в данном случае надо рассматривать и параллельные ребра – две вершины графа соединяются несколькими ребрами (граф, в котором некоторые пары вершин соединены более чем одним ребром, называется мультиграфом).

Вы рассматриваете графы без параллельных ребер. Это достаточно обременительное ограничение – в исходной задаче Эйлера о кенисбергских мостах параллельные ребра как раз были.

Как представлять такие графы? Конечно не так, как в вашей программе.

Например, для данного мультиграфа:
описание вершин:

(A B С D)

описание ребер:

((A C 3) (A C 4) (A B 1) (A B 2) (A D 5) (C D 7) (B D 6))
Так как в Лиспе большие и маленькие буквы не различаются, то мы вынуждены метки ребер заменить числами:

с  3, d  4, a  1, b  2, e  5, g  7, f  6.
Каждое ребро описывается списком из двух вершин и меткой ребра.

И путь, который ищет программа, должен быть представлен в виде списка меток ребер.


Например, для данного графа путь (1 2 3 4) означает путь

из вершины A в вершину B по ребру 1, потом

из вершины B в вершину A по ребру 2, потом

из вершины A в вершину C по ребру 3, потом

из вершины C в вершину A по ребру 4.
Сделайте изменения в программе и протестируйте программу на графах с параллельными ребрами.

Похожие:

Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconКурсовая работа по дисциплине информатика студента Чиж А. В шифр 9403030028 группа 230105

Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconРабочая программа по дисциплине "Дискретная математика" для специальности 230105 (220400)
Гос во по направлению 654600 Информатика и вычислительная техника (специальность 230105 (220400) – “Программное обеспечение вычислительной...
Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconДипломный проект выпускная квалификационная работа дипломированного специалиста Специальность 230105
Охватывают работы, выполняемые специалистами на следующих стадиях разработки проектных материалов
Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconПособие по геологии кафедры географии игпу сергей Николаевич Коваленко
...
Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconДепутат на округе
Сергей Николаевич Моисеев частый гость в шести школах своего округа и детском доме, к воспитанникам которого у депутата особое отношение....
Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconНазвание кафедры Курсовая (Контрольная) работа по предмету тема: выполнил(а): студент(ка) курса группы Специальность: 060109. 65 «Сестринское дело»

Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconСергей Николаевич Голубов Багратион Голубов Сергей Николаевич Багратион
Евгения, тихо струились воды широкого Немана. Река текла в уровень с берегами по гладкому раскату золотых полей, коричневых пашен...
Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconКурсовая работа Научный М. н с., к х. н. Головин А. В. Москва 2003 г
Определение области контакта рибосомального белка S7 с 16S ррнк в структуре Tth30S
Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconИнтернет-экзамен в сфере профессионального образования
Специальность: 230105. 65 – Программное обеспечение вычислительной техники и автоматизированных систем
Курсовая работа Определение эйлерова пути на Прологе Халипский Сергей Николаевич Специальность: 230105 iconКурсовая работа «Проектирование вычислительной системы»
Данная контрольно-курсовая работа выполняется с целью закрепления знаний по курсу «Организация ЭВМ и систем» и получения практических...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org