Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование     Программное обеспечение Программное обеспечение

Структуры данных и алгоритмы

Гуашь "Классика", 12 цветов.
Гуашевые краски изготавливаются на основе натуральных компонентов и высококачестсвенных пигментов с добавлением консервантов, не
170 руб
Раздел: 7 и более цветов
Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее
Совок №5.
Длина совка: 22 см. Цвет в ассортименте, без возможности выбора.
18 руб
Раздел: Совки

Новосибирский государственный технический университет Кафедра прикладной математики Курсовая работа Структуры данных и алгоритмы Факультет: ПМИ Группа: ПМ-71 Студент: Гридасов А.Ю. Новосибирск 2008 Оглавление Оглавление 1. Условие задачи 2. Анализ задачи 3. Выбор и обоснование форм представления данных 4. Алгоритм 5. Текст программы на языке Pascal 6. Выбор и обоснование набора тестов 7. Анализ результатов Приложение Условие задачи Имеется некоторое конечное число городов, которые связаны транспортной сетью, состоящей из авиа, железнодорожных, автомобильных и водных рейсов произвольного направления и включающих произвольное число городов. Стоимость проезда различна по классам. Рейсы отправляются по недельному расписанию. При пересадке между рейсами должно быть не менее 2-х часов. По заданным начальному и конечному городам, дате желаемого отправления, максимальному времени пути и максимальной стоимости и максимальному числу пересадок выдать все возможные маршруты, так, чтобы маршруты с меньшей датой и временем прибытия отображались раньше, чем с большим. Анализ задачи Транспортная схема представляет собой направленный взвешенный мультиграф. Каждая дуга характеризуется принадлежностью к рейсу, временем пути, ценой каждого из классов, временем отправления. Входными данными является: Транспортная система. (города и все рейсы) Начальный, конечный город, ориентировочная дата и время отправления, максимальное время пути максимальная цена, максимальное количество пересадок. Причем данные первой группы изменяются крайне редко и задаются разработчиком транспортной системы, а данные второй группы изменяются от задачи к задачи и задаются каждым пользователем. Результатом работы программы является конечное множество маршрутов. Два маршрута мы будем считать различными, если они отличаются хотя бы одним городом следования или хотя бы одним рейсом. После того, как найдены все маршруты они сортируются по времени прибытия. Метод решения – метод последовательных испытаний. Поиск решений будет осуществляться рекурсивно, причем максимальная глубина рекурсии будет равна максимальному количеству пересадок. Так как мы имеем ограничения по некоторым параметрам то мы можем отсечь заведомо ошибочную ветвь поиска решений, сделав проверку на превышение параметров. Это позволит выиграть дополнительное время. (о реализации более подробно п.4) Выбор и обоснование форм представления данных Так как транспортная система включает в себя достаточно большой объем информации, в целях доступа к большему объему памяти, также в целях более рационального использования памяти и по причине недопустимости использования статических объектов в некоторых случаях, в программе для внутреннего представления широко используются динамические объекты. Для объединения большого количества данных в одном объекте, а также для реализации динамических объектов используется комбинированный тип (запись). Для внутреннего хранения информации о рейсах используется цепь (однонаправленный список) PFligh с 7-ю информационными полями различных типов: Для хранения названия компании-перевозчика используется тип s ri g так по понятным причинам.

Для хранения номера рейса используется тип s ri g т.к. в номерах рейса часто используются различные не цифровые шифры, индексы, коды. Общее количество городов – интервальный тип. Автоматическая проверка границ этого типа повышает надежность программы. Таблица отправления представляется своим динамическим типом. Этот динамический тип представляет совой цепь с одним информационным полем, содержащим время отправления в минутах от начала недели (например Вт 17:42 будет записан числом 1 24 60 17 60 42). Такая форма хранения времени сочетает с себе компактность и легкость пересчета (пересчет требуется только при вводе и выводе, а в программе в большинстве случаев пересчет не нужен. Динамический тип использован по причине большого разброса в частоте отправления рейсов (могут быть рейсы, отправляющиеся каждый день через час, а могут быть рейсы отправляющиеся раз в неделю). Маршрут рейса также представляется своим динамическим типом – однонаправленным динамическим списком. Причина использования списка аналогична полю отправления -разброс. Так, например самолеты обычно не имеют более 4 посадок, а поезда наоборот делают много остановок. Информационное поле содержит информацию не об одной а о 4-х станциях, т.е. представляет собой массив из 4 элементов. Это сделано для экономии памяти на избыточных указателях. При этом усложнение кода программы незначительно. Тип транспорта кодируется числом 1.4. По понятным причинам. Перечислимый тип не был использован для упрощения ввода данных из внешнего файла. Классы, которые предоставляет рейс, представляется в виде массива индексом является класс, а типом элемента – булевский. Внутренне каждый город обозначается своим номером (элемент интервального типа), что уменьшает расходы памяти и упрощает вычисление. А для хранения названий городов и их координат для отображения на экране используется свой тип – массив, элементами которого являются записи с полями для названия города и координат. Статический массив используется для простого и быстрого доступа к этим данным. Для хранения времени пути используется тип I eger. Отрицательные числа нужны для контроля за превышением времени пути. Для хранения цены используется тип Lo gI . Причины выбора этого типа очевидны. Тип Pa er для хранения исходных параметров поиска представляет собой запись с полями: время отправления относительно понедельника в минутах, начальный и конечный город, допустимые типы транспорта, допустимые классы, максимальное количество пересадок, максимальное время пути, максимальная цена, допустимые классы. Выбор типов для всех полей кроме «допустимые типы транспорта» обсуждался выше. Для поля «допустимые типы транспорта» выбран массив где тип индекс – это тип транспорта, а тип элемента – булевский. Это сделано по причине того что маршрут может включать. Поездки на разных видах транспорта (тех где в значение rue). Запись использована чтоб передавать все данные единым объектом в процедуру поиска маршрута. Тип Li k предназначен для хранения информации о части маршрута между двумя городами, соединенными одним рейсом. Кроме ссылки на предыдущую такую часть он содержит ссылку на рейс, коды начального и конечного города, общую цену участка, время отправления, относительно заданного пользователем время отправления, общее время пути по участку.

Типы полей и обоснования их выбора обсуждались выше. В совокупности цепочка таких элементов задает один маршрут. Тип A swerLis предназначен для ответа - множества всех допустимых маршрутов. Представляет из себя однонаправленный список, в каждом элементе которого кроме ссылки на следующий имеется поле типа маршрут (Li k), общее время пути, общая максимальная и минимальная цена, количество пересадок. Типы полей и обоснование обсуждались выше. Внешнее представление: Транспортная система хранится во внешнем текстовом файле. Файл может быть создан любым текстовым редактором. В файле указывается следующее: Количество городов. Со следующей строки начинается информация о городах: название города, на следующей строчке координаты. После всех городов начинается информация о рейсах: компания, номер, тип, классы, количество станций; номер города, время пути, время стоянки цена по классам, для каждого города; время отправления от начальной станции. Так как эта информация редактируется крайне редко, причем разработчиком сети, то такой способ является наиболее приемлемым. Название городов вводятся как строки, дата – в любом формате (дд-мм-гг, дд-мм-гггг, дд-мес-гг и т.п.) время чч:мм. По умолчанию полагается дата – текущий день, время 0:00. Максимальное время пути, максимальное число пересадок, максимальная цена – вводятся как числа. Алгоритм Begi {Загрузка транспортной схемы}; {Ввод исходных данных и заполнение шаблона}; {Вызов процедуры поиска с введенным шаблоном, построенная часть маршрута - пустая}; {Вывод полученного множества маршрутов} E d {Процедура поиска маршрута с данным шаблоном и уже построенной частью маршрута} Begi While {просмотрены не все рейсы} do begi If {соответствует тип транспорта} a d {Текущий рейс не равен предыдущему} he Begi If {город отправления присутствует в рейсе, причем раньше конечной станции} he begi {Рассчитать время отправления ближайшего следующего рейса} Repea {Перейти к следующему городу}; {Рассчитать время дороги с учетом нового участка} If {текущий город еще не проезжали} a d {время пути не превышает максимального} a d {количество пересадок не превышает максимального} a d {не приехали1} he {Добавить к маршруту проеханный участок. Вызвать процедуру поиска маршрута от текущего города до конечного с новыми значениями времени} U il {текущий город проезжали} or {время исчерпано} or {приехали} or {конец рейса}; If {приехали} a d {время не превышено} a d {минимальная цена рейса не выше допустимой} he {Добавить построенный маршрут в мно-во ответов на нужное место} e d; e d; {Перейти к следующему рейсу} e d; e d Текст программы на языке Pascal uses Cr , Da e, Graph; Co s MaxCi y=100; MClass=6; ype Ci yCode=1.maxci y; {Внутрений код города} Week=0.10079; {Тип время в минутак с 0:00 понедельника} Day able=^IDay able; {Таблица отправлений от начальной станции} IDay able=record ime:Week; ex :Day able; e d; WayKi d=1.4; {Тип пути (аэро, море, ж.д, авто)} WayClass=1.MClass; {Класс или тип перевозки} Ci ies=array of {Названия и координаты городов} record ame:s ri g of lo gi ; {Таблица стоимости по классам} Way=record Ci y:Ci ycode; Delay,Reboard:Word; Cos :mcos ; e d; WayP=^way; PWay=^Way1; {Информация о городах следования рейса} Way1=record Way:array of way; ex :PWay; e d; wclass=array of boolea ; PFligh =^Fligh ; Fligh =record {Информация о рейсе} compa y:s ri g; o als a io :Ci yCode; able:Day able; pa h:PWay; ki d:WayKi d; class:WClass; ex :PFligh ; e d; Bla k=record {Шаблон для поиска пути} delay:Week; BCi y,ECi y:Ci yCode; Ki d:array of boolea ; ReBoadi g:Ci yCode; Way ime:I eger; Cos :Lo gi ; Class:WClass; e d; Li k=^Ci yLis ; {Цепочка рейсов для проезда от начала до конца} Ci yLis =record {Информация о проезде между двумя пунктами одним рейсом} DDelay:Word; way ime:word; cos :mcos ; Bci y, arge :Ci yCode; Fligh :PFligh ; Las :Li k; e d; A swerLis =^IA swer; {Список всех возможных маршрутов следования} IA swer=record pa h:li k; reboard:ci ycode; mi cos ,maxcos :lo gi ; way ime:word; ex :A swerLis ; e d; var La swer:A swerLis ; {глобальная переменная - начало списка маршрутов } {Добавления нового найденного маршрута} Procedure A swer(A:Li k;cos :lo gi ); var P,Q:Li k; d,s1,s2:word; W,PA swer:a swerlis ; r:ci ycode; fu c io mi (a:mcos ):lo gi ; {Минимальная стоимость по классам} var i:i eger; m:lo gi ; begi m:=1000000000; for i:=1 o Mclass do if (m&g ;a; mi :=m e d; fu c io max(a:mcos ):lo gi ; {Максимальная стоимость по классам} var i:i eger; m:lo gi ; begi m:=a; max:=m e d; begi ew(PA swer); Pa swer^.p

Затем, используя обычный алгоритм планирования, ядро выбирает порожденный процесс для исполнения и тот «доигрывает» свою роль в алгоритме fork. Контекст порожденного процесса был задан родительским процессом; с точки зрения ядра кажется, что порожденный процесс возобновляется после приостанова в ожидании ресурса. Порожденный процесс при выполнении функции fork реализует ту часть программы, на которую указывает счетчик команд, восстанавливаемый ядром из сохраненного на уровне 2 регистрового контекста, и по выходе из функции возвращает нулевое значение. На Рисунке 7.3 представлена логическая схема взаимодействия родительского и порожденного процессов с другими структурами данных ядра сразу после завершения системной функции fork. Итак, оба процесса совместно пользуются файлами, которые были открыты родительским процессом к моменту исполнения функции fork, при этом значение счетчика ссылок на каждый из этих файлов в таблице файлов на единицу больше, чем до вызова функции. Порожденный процесс имеет те же, что и родительский процесс, текущий и корневой каталоги, значение же счетчика ссылок на индекс каждого из этих каталогов так же становится на единицу больше, чем до вызова функции

1. Структура программного обеспечения региональной экоинформационной системы

2. Некоторые особенности реализации алгоритма защиты программного обеспечения от нелегального использования

3. Программное обеспечение для модемов Lexand TS2400

4. Технология разработки программного обеспечения

5. Разработка системного программного обеспечения

6. Разработка программного обеспечения для оптимизации показателей надежности радиоэлектронных систем
7. Объектно-ориентированный подход к проектированию программного обеспечения на примере работы налоговой инспекции
8. Программное обеспечение персональных компьютеров

9. Программное обеспечение удалённого доступа к технической документации

10. Вирусы и антивирусное программное обеспечение

11. Программное обеспечение компьютеров. Архиваторы

12. Обзор современного программного обеспечения управления проектами

13. Продуктовая политика организации (на примере продвижения услуг программного обеспечения)

14. Программное обеспечение сетей ЭВМ

15. Разработка программного обеспечения

16. Охрана программного обеспечения

Ручка гелевая "BLGP-G1-5", синяя, 0,3 мм, 3 штуки.
Гелевая ручка Pilot имеет пластиковый корпус с резиновой манжеткой, которая снижает напряжение руки. Стержень с чернилами синего цвета в
345 руб
Раздел: Синие
Каталка детская "Mercedes-Benz SLS AMG С197" (белая).
Каталка "Mercedes-Benz SLS AMG С197" - это легкая пластиковая каталка для детей от года. Она может использоваться как дома, так
2590 руб
Раздел: Каталки
Универсальный стиральный порошок "Meine Liebe", концентрат, 1000 г.
Предназначен для стирки цветного и белого белья во всех типах стиральных машин при температурах от 30 С до 90 С, а так же для ручной
438 руб
Раздел: Стиральные порошки

17. Программное обеспечение преемственности подготовки специалистов по физической культуре и спорту в системе "колледж-вуз"

18. Виды программного обеспечения, операционной система

19. Программное обеспечение

20. Вредоносное программное обеспечение

21. Программное обеспечение модемов

22. Разработка программного обеспечения
23. Программное обеспечение
24. История развития прикладного программного обеспечения

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

26. Разновидности общесистемного программного обеспечения персональных ЭВМ

27. Технологии тестирования программного обеспечения

28. Системное программное обеспечение

29. Технологии тестирования программного обеспечения

30. Свободное программное обеспечение: к чему приведет "свобода"?

31. Структуры данных и алгоритмы

32. Бухгалтерский и налоговый учет покупаемого программного обеспечения

Набор линеров "Kores", 0,4 мм, 10 цветов.
Линеры имеют эргономичную зону обхвата. Толщина линии письма - 0,4 мм. Набор содержит 10 цветов. Входящие в набор цвета:
424 руб
Раздел: Капиллярные
Этажерка для обуви разборная, 2 полки, 435x660x300 мм, 4 положения.
Этажерка Ника ЭТ3 - ваш правильный выбор в экономии свободного пространства. Модель предназначена для хранения обуви в прихожей. Она
720 руб
Раздел: Полки напольные, стеллажи
Ручка шариковая "Excellence", золото.
Новая подарочная шариковая ручка имеет необычный дизайн, который притягивает взгляд. Металлический миниатюрный корпус полностью усыпан
444 руб
Раздел: Металлические ручки

33. АИС управления серверным программным обеспечением на базе программного комплекса Webmin/Alterator

34. Аппаратура, программное обеспечение и микропрограммы

35. Виды программного обеспечения. Общие требования к программным системам

36. Методика работы с модулем "Реализация и склад" программного обеспечения "ПАРУС"

37. Общая характеристика и классификация программного обеспечение и базовых технологий управления информационными ресурсами

38. Операционная система, программное обеспечение ПК
39. Организация процесса конструирования программного обеспечения
40. Оценка риска проектов программного обеспечения

41. Прикладное программное обеспечение

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

43. Программное обеспечение

44. Программное обеспечение Lotus-Notes

45. Программное обеспечение Линукс

46. Программное обеспечение системы принятия решений адаптивного робота

47. Программное обеспечение ЭВМ и языки программирования

48. Программное обеспечение. Операционная система

Бумага чертежная, А2, 594x420 мм, 100 листов.
Плотность: 200 г/м2, ГОСТ 597-73.
1687 руб
Раздел: Папки для акварелей, рисования
Микроскоп для смартфона "Kakadu".
Микроскоп для смартфона прекрасное дополнения для Вашего гаджета. Увеличение в 30 раз! Подходит практически ко всем смартфонам (толщина
383 руб
Раздел: Прочее
Деревянная игрушка "Набор для обучения".
Отличная игрушка для малыша. Способствует развитию мелкой моторики, логического мышления, координации движений.
749 руб
Раздел: Счетные наборы, веера

49. Проектирование процесса тестирования программного обеспечения

50. Разработка базы данных и прикладного программного обеспечения для автобусного парка

51. Разработка интернет – магазина по продаже программного обеспечения

52. Разработка прикладного программного обеспечения деятельности предприятия в системе клиент-сервер

53. Разработка программного обеспечения для нахождения корней биквадратного уравнения

54. Разработка программного обеспечения для оценки уровня знаний студентов с применением технологии "Клиент-сервер"
55. Разработка программного обеспечения для фильтрации растровых изображений
56. Разработка программного обеспечения по автоматизации учебного процесса в колледже

57. Разработка программно–алгоритмических средств для определения надёжности программного обеспечения на основании моделирования работы системы типа "клиент–сервер"

58. Реинжиниринг программного обеспечения

59. Анализ прикладного программного обеспечения

60. Разработка алгоритмического и программного обеспечения стандарта IEEE 1500 для тестирования гибкой автоматизированной системы в пакете кристаллов

61. Системное программное обеспечение

62. Организационно-экономические мероприятия по совершенствованию качества выпускаемого программного обеспечения

63. Использование современного программного обеспечения для проектировании цепной передачи в металлорежущем станке

64. Исследование программного обеспечения физкультурного образования дошкольников

Стул детский Ника "СТУ3" складной, мягкий (цвет: синий).
Особенности: - стул складной; - предназначен для детей от 3 до 7 лет; - металлический каркас; - на ножках стула установлены пластмассовые
518 руб
Раздел: Стульчики
Рюкзак для средней школы "Неон", 46x34x18 см.
Рюкзак для средней школы. 2 основных отделения, 4 дополнительных кармана. Формоустойчивая спинка. Ремни регулировки объема. Материал:
978 руб
Раздел: Без наполнения
Доска пробковая "Premium", 60x90, алюминиевая рамка.
Доска пробковая с качественным покрытием, в элегантной рамке из алюминиевого профиля. Изготовлены c использованием наполнителя Softboard,
1054 руб
Раздел: Прочее

65. Структура и алгоритмы работы спутниковых радионавигационных систем

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

67. Способы обеспечения качества программных продуктов

68. Разработка алгоритмов и программных средств подсистемы документооборота системы управления содержанием информационного сервера

69. Авторское право как институт правовой защиты прикладного программно-математического обеспечения ЭВМ

70. Алгоритм и его структура
71. Обеспечение всемирной трансляции спортивных шахматных соревнований с применением разработанного в ходе проекта законченного программного продукта
72. Создание средств наглядности с использованием программной среды Delphi и Microsoft Movie Maker

73. Структуры и алгоритмы обработки данных

74. Структура системы пенсионного обеспечения регионов

75. Типы и элементы планировочной структуры города

76. Эволюция, образование и структура Вселенной

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

78. Генетические алгоритмы

79. Структура и состояние водоснабжения и водосброса, подземных вод и артезианских скважин города Киева

80. Проблемы обеспечения продовольствием и перенаселение Земли

Набор детской посуды "Домашние животные" (3 предмета).
Набор детской посуды "Домашние животные" в подарочной упаковке. В наборе 3 предмета: - кружка 240 мл; - тарелка 19 см; - миска
310 руб
Раздел: Наборы для кормления
Тележка багажная ручная ТБР-02.
Грузоподъемность: 30 кг. Предназначена для перевозки грузов. Удобна для любого путешествия. Легко собирается в транспортное положение,
538 руб
Раздел: Хозяйственные тележки
Полотенце махровое "Нордтекс. Aquarelle", серия "Палитра", цвет: аметистовый, 70х130.
Полотенца махровые гладкокрашеные изготовлены из 100% хлопка, плотность 300 г/кв.м. Размер: 70х130 см.
361 руб
Раздел: Большие, ширина свыше 40 см

81. Планирование обеспечения горючим воинской части в мирное время

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

83. Территориальные особенности обеспеченности хозяйства Украины природными ресурсами (Контрольная)

84. Структура транспорта в Европе

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

86. Проблемы пенсионного обеспечения в РФ
87. Государственный аппарат и его структура
88. Деятельность органов внутренних дел по обеспечению режима чрезвычайного положения

89. Залог - как способ обеспечения исполнения обязательств

90. Алгоритмы экономической (кадастровой) оценки городских земель и территориально-экономического зонирования

91. "Военный коммунизм" - вынужденная политика или программный идеал большевизма

92. Структура государственных органов США по Конституции 1787 года

93. Система пенсионного обеспечения населения и пути его реформирования

94. Двухпалатная структура Федерального Собрания

95. Роль главы государства в обеспечении конституционных прав личности в РФ

96. Организационно-правовое обеспечение деятельности комитета по международным делам ГД ФС РФ

Набор ковриков "Kamalak Tekstil" для ванной, 50х50 см и 50x80 см (бежевый).
овры-паласы выполнены из полипропилена. Ковры обладают хорошими показателями теплостойкости и шумоизоляции. Являются гипоаллергенными. За
607 руб
Раздел: Коврики
Набор подарочный для новорождённого "Мой малыш".
Запечатлите мимолетные мгновения жизни Вашего ребенка с помощью необычного набора для новорождённого «Мой малыш». Рамка для
850 руб
Раздел: Прочие
Ранец "Generic. Wild Horse".
Размер: 37х27х21 см. Раскладной школьный ранец обязательно привлечет внимание вашего ребенка. Ранец выполнен из современного легкого и
2567 руб
Раздел: Без наполнения

97. Роль ООН в вопросах обеспечения международной безопасности

98. Структура закона Саратовской области "О местном самоуправлении в Саратовской области". Полномочия органов местного самоуправления в области жилищного хозяйства, коммунально-бытового и торгового обслуживания населения

99. Структура, содержание и значение общей части Налогового кодекса России


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.