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

Математика Математика

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

Коврик для запекания, силиконовый "Пекарь".
Коврик "Пекарь", сделанный из силикона, поможет Вам готовить вкусную и красивую выпечку. Благодаря материалу коврика, выпечка не
202 руб
Раздел: Коврики силиконовые для выпечки
Гуашь "Классика", 12 цветов.
Гуашевые краски изготавливаются на основе натуральных компонентов и высококачестсвенных пигментов с добавлением консервантов, не
170 руб
Раздел: 7 и более цветов
Ночник-проектор "Звездное небо и планеты", фиолетовый.
Оригинальный светильник - ночник - проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фонариков) 2) Три
330 руб
Раздел: Ночники

Структуры данных и алгоритмы Курсовая работа студента  Гридасова А. Ю. Новосибирский государственный технический университет Кафедра прикладной математики Новосибирск 1998 Условие задачи Имеется некоторое конечное число городов, которые связаны транспортной сетью, состоящей из авиа, железнодорожных, автомобильных и водных рейсов произвольного направления и включающих произвольное число городов. Стоимость проезда различна по классам. Рейсы отправляются по недельному расписанию. При пересадки между рейсами должно быть не менее 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 {не приехали }      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>a;     mi :=m   e d;  fu c io max(a:mcos ):lo gi ;  {Максимальная стоимость по классам}   var i:i eger; m:lo gi ;   begi     m:=a;     for i:=2 o Mclass do if m=P^.

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

1. Организация и управление данными при проектировании сложных изделий в системе V5

2. Пример проектирования базы данных "Библиотека"

3. Проектирование Базы Данных для коммерческого предприятия

4. Основные принципы проектирования баз данных

5. Проектирование базы данных

6. Проектирование базы данных "Аптека"
7. Проектирование базы данных "Институт"
8. Проектирование базы данных "Отдел кадров"

9. Проектирование базы данных агентства по оказанию маркетинговых услуг

10. Проектирование базы данных магазина по сборке компьютеров

11. Проектирование базы данных предприятия

12. Принципы построения и этапы проектирования баз данных

13. Анализ и проектирование структуры системы управления фирмой (на примере ООО МСК "АСКО-ВАЗ")

14. Влияние структуры исходной ПАН-нити на структуру и свойства углеродного волокна

15. Структура й функції інтегрованої банківської інформаційної системи

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

Фанты "Масло в огонь".
Это настолка для влюбленных пар с различным «стажем» отношений, подойдет в качестве презента на свадьбу или годовщину
1291 руб
Раздел: Игры для взрослых (18+)
Пазл "Россия" (Русский), 100 деталей.
Пазлы - это прежде всего обучающие пазлы. С фотографической точностью прорисованы обитатели и растительный мир самых отдаленных уголков
548 руб
Раздел: Пазлы (100-199 элементов)
Каталка-мотоцикл "МХ".
Новая каталка-мотоцикл "МХ" впечатлит вашего малыша. Он сможет почувствовать себя настоящим байкером, ведь эта каталка не просто
2899 руб
Раздел: Каталки

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

18. Проектирование и разработка информационной системы на примере магазина "Computer Master"

19. Проектирование и обеспечение функционирования системы управления предпринимательской организации (на примере ООО "Олеся")

20. Структуры данных: бинарное упорядоченное несбалансированное дерево

21. Структура отитов у детей по данным ЛОР-отделения ПЦ НЦМ-РБ

22. Структуры данных
23. Структура и формирование исходных данных, необходимых для расчета параметров технологических схем
24. Динамические структуры данных: очереди

25. Иерархические структуры в реляционных базах данных

26. Иерархические структуры данных в реляционных БД

27. Динамические структуры данных: списки

28. Динамические структуры данных: списки

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

30. Алгоритмы и структуры данных. Программирование в Cи

31. Разработка обучающей программы, поддерживающей изучение темы "Структуры данных"

32. Структури даних для обробки інформації

Игра магнитная "Одевашки. Настя".
Это магнитная история про то, как одеть куклу Настю. Она простая, но при этом очень увлекательная и не вызовет сложности у ребенка старше
343 руб
Раздел: Бумажные куклы
Подушка, с лузгой гречихи, 40x60 см.
Подушка с гречневой лузгой - самая натуральная ортопедическая подушка: она высококачественная, "дышащая", экологична. Размер
520 руб
Раздел: Размер 50х70 см, 40х60 см
Контейнер "Рукоделие", 10 л.
Контейнер выполнен из прозрачного пластика. Для удобства переноски сверху имеется ручка. Внутрь вставляется цветной вкладыш с одним
324 руб
Раздел: 5-10 литров

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

34. Фізична структура даних. Бухгалтерські інформаційні системи

35. Динамические структуры данных

36. Динамические структуры данных: дек

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

38. Проектирование оптимальной структуры строительных машин при перевозке нерудных строительных материалов
39. Выбор и обоснование структуры автоматизированной системы управления – АСУ "Супермаркет"
40. Проектирование канала сбора аналоговых данных микропроцессорной системы

41. Проектирование и корректировка организационной структуры предприятия

42. Проектирование и реализация базы данных

43. Проектирование системы сбора данных

44. Решение хранения данных для локальной сети

45. Накопители для хранения и переноса данных

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

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

48. Проектирование аппаратуры передачи данных

Полотенце вафельное "Сластена полосатка", банное, пляжное, 100х150 см.
Вафельное полотенце "Сластена полосатка". Легкое и практичное полотенце удобно использовать на пляже, в бане и в бассейне.
304 руб
Раздел: Большие, ширина свыше 40 см
Средство для мытья посуды Finish "All in 1 Max", в посудомоечных машинах таблетки, 65 штук.
Таблетки идеальны для использования на коротких циклах - таблетки быстро растворяются. Таблетки не нужно разворачивать! Специальные
880 руб
Раздел: Для посудомоечных машин
Шкатулка для ювелирных украшений, 13x13x6 см, арт. 84412.
Шкатулка сохранит ваши ювелирные изделия в первозданном виде. С ней вы сможете внести в интерьер частичку элегантности. Регулярно удалять
832 руб
Раздел: Шкатулки для украшений

49. Проектирование информационных баз данных: отчет по отгруженным товарам

50. Проектирование реляционных баз данных

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

52. Разработка форматов хранения данных программы. Структурирование

53. Блочно-симметричные модели и методы проектирования систем обработки данных

54. Схема процесса автоматизированного проектирования РЭС. Структура и классификация проектных задач
55. Проектирование организационных структур государственного управления
56. Отраслевая структура экономики России и методы отраслевого экономического обоснования размещения производства

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

58. Структура организации материи

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

60. Структура и функции клеточного ядра

61. Синапсы (строение, структура, функции)

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

63. Дания

64. Особенности годового хода приземной температуры воздуха в разных частях Земли по данным ОА Гидрометцентра РФ

Детские футбольные ворота 2 в 1.
Игровой набор включает в себя всё необходимое для тренировок маленьких футболистов - пластиковые сборно-разборные ворота с сеткой,
1306 руб
Раздел: Футбол
Мешок для обуви "Мерцающие звезды", 33х40 см.
Мешок для обуви. Размер: 33х40 см.
315 руб
Раздел: Сумки для обуви
Доска магнитно-маркерная, 120х90 см.
Доска имеет магнитную поверхность. Алюминиевая рамка соединяется пластиковыми уголками, имеет регулируемые элементы крепления,
3010 руб
Раздел: Доски магнитно-маркерные

65. План статистического наблюдения и данные переписи населения

66. Безработица в России /данные на 1992г/

67. Государственный аппарат и его структура

68. Нормы права. Структура норм права

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

70. Налоговая система Дании
71. Международная организация труда- создание, структура, задачи и организация её работы
72. Структура закона Саратовской области "О местном самоуправлении в Саратовской области". Полномочия органов местного самоуправления в области жилищного хозяйства, коммунально-бытового и торгового обслуживания населения

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

74. Структура налоговых органов РФ права, обязанности и функции

75. Структура налоговых органов Российской Федерации

76. Цели, задачи и структура Федерального закона № 122-ФЗ

77. Структура нормы права

78. Структура правоотношения. Классификация правоотношений: критерии и виды

79. Структуры экономического дискурса во французском языке. Роль коннекторов в построении аргументации

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

Телескопическая ложка.
Прикольный подарок, который рассмешит участников любого застолья. При помощи этой ложки Вы можете с невозмутимым видом «подцепить»
397 руб
Раздел: Прочее
Этикетка самоклеящаяся, А4, 1 этикетка, 210х297 мм, белая, 100 листов.
Размер этикетки: 210х297 мм. 1 этикетка на листе А4. Плотность бумаги: 70 г/м2. Верхнее и нижнее поле (отступ от края листа до этикетки):
660 руб
Раздел: Бейджи, держатели, этикетки
Игровой набор "My Little Pony. Мерцание". Пинки Пай.
Игровой набор "Мерцание" из серии "Май Литл Пони" от популярного бренда Hasbro представляет собой всеми любимую
2018 руб
Раздел: Игрушки

81. Структура культуры. Классификация ее видов

82. Даниил Иванович Хармс

83. Загальна структура мовної системи

84. Трансформация жанровой структуры литературы Древнего Египта

85. Структура ораторской речи

86. Данило Нечай - сподвижник Богдана Хмельницкого
87. Классовый и сословный характер общества по данным древневосточных судебников
88. Методы компьютерной обработки статистических данных. Проверка однородности двух выборок

89. Базы данных в Internet

90. Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных

91. Системы, управляемые потоком данных. Язык "Dataflow Graph Language"

92. Электронная почта и факсимильная связь. Структура и прицип работы

93. Глобальные гипертекстовые структуры: WWW

94. Микропроцессор Z80 его структура и система команд

95. Выбор логической структуры процессора

96. Информация, информатика, базы данных. Периферийные устройства

Ручки капиллярные "Johanna Basford. Triplus 334", 36 цветов.
Количество цветов: 36 ярких цветов. Эргономичная форма для удобного и легкого письма. Пишущий узел завальцован в металл. Защита от
2085 руб
Раздел: Капиллярные
Портфель "Megapolis", синий.
Легкая папка-портфолио изготовлена из жесткого пластика, рассчитана на длительный срок службы. Папка служит для перевозки документов и
512 руб
Раздел: Папки-портфели, папки с наполнением
Ночник с датчиком движения "Ночной снайпер".
Маленький ночник с датчиком движения "Ночной снайпер" надежно крепится на крышку унитаза и срабатывает только при вашем
648 руб
Раздел: Ночники

97. Данные и информация

98. Форматы баз данных в автоматизированных библиографических системах

99. Пример базы данных на Delphi 2.0

100. Структура и реализация макроязыков


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