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

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

Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10
Забавная пачка "5000 дублей".
Юмор – настоящее богатство! Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь
60 руб
Раздел: Прочее

СодержаниеВведение 1 Выбор варианта задания 2 Алгоритм сортировки Шейкер 2.1 Математическое описание задачи 2.2 Словесное описание алгоритма и его работы 2.3 Описание схемы алгоритма 2.4 Контрольный пример 3 Алгоритм покрытия: построение одного кратчайшего покрытия 3.1 Математическое описание задачи 3.2 Словесное описание алгоритма и его работы 3.3 Описание схемы алгоритма 3.4 Контрольный пример 4 Алгоритм на графах: нахождение кратчайшего пути 4.1 Математическое описание задачи 4.2 Словесное описание алгоритма и его работы 4.3 Описание схемы алгоритма 4.4 Контрольный пример Заключение Перечень литературы Введение Алгоритм – это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса, т.е. такой набор инструкций, который можно реализовать чисто механически, вне зависимости от умственных способностей и возможностей исполнителя. Как заметил Кнут: «Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер». Теория алгоритмов и практика их построения и анализа является концептуальной основой разнообразных процессов обработки информации. В настоящее время теория алгоритмов образует теоретический фундамент вычислительных наук. Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью проясняются такие понятия как доказуемость, эффективность, разрешимость, перечислимость и другие. Эффективность алгоритма определяется анализом, который должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временной сложности процесса. Речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе (естественно, к ним относятся входные наборы, промежуточная и выходная информация), а также физических ресурсах, затраченных исполнителем. В курсовой работе представлены различные подходы и методы использования алгоритмов, приведены оценки сложностей алгоритмов, реализации математических задач с помощью алгоритмов. Проведена краткая характеристика используемых структур данных, эффективность их применения в данной задаче ВЫБОР ВАРИАНТА Номер варианта определяется нахождением остатка от целочисленного деления числа У, которое является суммой числа Х и номера по списку в журнале. Номер по списку в журнале =9. Таким образом: X= гр 100=5 100=500; Y= X=9 500=509. По формулам нахожу соответствующие виды алгоритмов. 1) (Y mod 4) 1 =(509 mod 4) 1=1 1= 2; Алгоритм покрытия: построение одного кратчайшего покрытия. 2) (Y mod 6) 1 =(509 mod 6) 1 = 5 1=6; Алгоритм на графах: поиск кратчайшего пути. 3) (Y mod 5) 1 =(509 mod 5) 1 =4 1 = 5; Алгоритм сортировки: сортировка-шейкер. 2 АЛГОРИТМ СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР 2.1 Математическое описание задачи Сортировка – это перестановка элементов некоторого множества в заданном порядке при некоторой упорядочивающей функцию. Сортировка используется для облегчения поиска элемента в таком отсортированном множестве.

Задача сортировки решается с помощью таких алгоритмов: сортировка с помощью прямого включения, прямого выбора, прямого обмена, включений с уменьшающимися расстояниями, дерева, разделения и другие. 2.2 Словесное описание алгоритма и его работы Сортировка Шейкер является усовершенствованной сортировкой методом пузырька. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.(см. Таб. 1) Таблица 1 i=1 2 3 4 5 6 7 8 44 06 06 06 06 06 06 06 55 44 12 12 12 12 12 12 12 55 44 18 18 18 18 18 42 12 55 44 42 42 42 42 94 42 18 55 44 44 44 44 18 94 42 42 55 55 55 55 06 18 94 94 67 67 67 67 67 67 67 67 94 94 94 94 После нулевого прохода по массиву &quo ;вверху&quo ; оказывается самый &quo ;легкий&quo ; элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию. Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию. Среднее число сравнений и обменов имеют квадратичный порядок роста: отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся. Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит ? Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала !). Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу. Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i. Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов. Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм называют &quo ;шейкер-сортировкой&quo ;. Далее проведена программа на языке С , реализующая сортировку Шейкер. empla e&l ;class &g ; void shakerSor ( a[], lo g size) { lo g j, k = size-1; lo g lb=1, ub = size-1; // границы неотсортированной части массива x;do { // проход снизу вверх for( j=ub; j&g ;0; j-- ) { if ( a=x; k=j; } }lb = k 1;// проход сверху вниз for (j=1; j&l ;=ub; j ) { if ( a=x; k=j; } } ub = k-1; } while ( lb &l ; ub ); } Насколько описанные изменения повлияли на эффективность метода ? Среднее количество сравнений, хоть и уменьшилось, но остается O( 2), в то время как число обменов не поменялось вообще никак.

Среднее(оно же худшее) количество операций остается квадратичным, количество излишних двойных проверок сократилось. Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество. На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется. 2.3 Описание схемы алгоритма Алгоритмы сортировки очень сильно зависят от структуры данных. В данной работе рассматривается сортировка массивов. Тип данных «массив» удобен тем, что хранится во внутренней памяти и имеет случайный доступ к элементам, то есть более быстрый, чем у последовательности. Поэтому массивы целесообразно использовать для хранения небольших, часто используемых множеств Из выше сказанного следует, что в процессе работы потребуются следующие переменные: – количество элементов массива; A – сортируемый массив; j – переменная; x – i-й ключ (переносимый элемент); r – номер последнего обмена при просмотре входной последовательности слева-направо. l - номер последнего обмена при просмотре входной последовательности справа - налево. Все переменные целого типа. Описание схемы алгоритма. Блок-схема данного алгоритма изображена на рис. 1 в Приложении. Алгоритм работает следующим образом. Сначала вводятся исходные данные: длина массива и его элементы (блок 1, 2) , затем организуется цикл по всей длине массива, во время которого (блоки 3 -7) и проводится сравнение элементов а и их обмен при проходе справа-налево . Номер последнего обмена l запоминается. Далее организуется цикл, в котором проводится проверка условия а при проходе массива слева-направо (блоки 8 - 12). 2.4 Контрольный пример Рассмотрим пример работы алгоритма сортировки Шейкер. Задан массив A, состоящий из 8 элементов: 44, 55, 12, 42, 94, 18, 6, 67. Шаг 1. l = 2, r = 8 Таблица 2 l 2 3 3 4 4 r 8 8 7 7 4 Направление ↑ ↓ ↑ ↓ ↑ j=1 44 6 6 6 6 j = 2 55 44 44 12 12 j= 3 12 55 12 44 18 j = 4 42 12 42 18 42 j = 5 94 42 55 42 44 j = 6 18 94 18 55 55 j = 7 6 18 67 67 67 j = 8 67 67 94 94 94 j = r =8 A, x=18, A =6, A&g ;A =6, A = 44 l=3. Шаг 2. A; j=6 2) A, A =12, j=6 5) A = 18 , j=8 7) r =7. Шаг 3. A, x=18, A =6, A =42; j=4 A, A =6, A, x=18, A = 94, j= 4 3) A, A&g ;A = 44 , j=8 , 7) r =7. → конец алгоритма. Таким образом, мы получили исходный массив, отсортированный методом Шейкер: 6, 12, 18, 42, 44, 55, 67, 94. 3 АЛГОРИТМ ПОКРЫТИЯ: ПОСТРОЕНИЕ ОДНОГО КРАТЧАЙШЕГО ПОКРЫТИЯ 3.1 Математическое описание задачи и методов её решения Пусть -опорное множество. Имеется множество подмножеств множества B ( ). Каждому подмножеству сопоставлено число , называемой ценой. Множество называется решением задачи о покрытии, или просто покрытием, если выполняется условие , при этом цена . Термин «покрытие» означает, что совокупность множеств содержит все элементы множества В, т.е. «покрывает» множество B Безизбыточным называется покрытие, если при удалении из него хотя бы одного элемента оно перестает быть покрытием.

К рассвету золото было доставлено на аэродром. После короткого отдыха летчики заняли свои места в самолете. Погода благоприятствовала полету. На небе - ни облачка. "Де хевиленд" с полностью заправленными баками пробежал по взлетной дорожке аэродрома и медленно начал набирать высоту. Вначале Кудрин и Мельников летели вдоль железной дороги, проходившей по долине реки Ворчала, но затем, попав в полосу сплошной облачности, закрывшую Караклисский перевал, полетели вдоль Зелинсанского ущелья. Здесь облачность была меньше, с просветами. Семеновский перевал перелетели на высоте 4000 метров. Вскоре заметили вершину горы Арарат... Пользуясь этим ориентиром, летчики кратчайшим путем вывели самолет в долину реки Араке, на железную дорогу Эривань - Нахичевань, и начали снижаться. Через несколько минут показалась Нахичевань. Здесь самолет уже ждали. Три белых квадрата и стрела показали путь к аэродрому. Аэродром оказался очень маленьким. К тому же телеграфные провода в полосе подхода к нему очень затрудняли посадку. Летчики решили "высмотреть" с воздуха более подходящую площадку, но их поиски оказались безуспешными

1. Алгоритм создания базы данных складского учета

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

3. Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal

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

5. Алгоритмы поиска кратчайших покрытий булевых матриц

6. Отчет по учебной практике ОАиП база данных студентов (создание, поиск, удаление, сортировка, все, что надо написанная на С++)
7. Алгоритмы поиска в тексте
8. Алгоритмы поиска подстроки в строке

9. Оптимизация алгоритмов поиска

10. Алгоритмы сортировки

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

12. Web-серверы, базы данных в Интернет, Поиск информации в Интернет, Основные системы и средства

13. Реализация алгоритма обработки данных

14. Данные о происхождении человека и поиски его прародины

15. Алгоритмы сжатия данных

16. Поиск кратчайшего пути в лабиринте

Наклейка зеркальная "Бабочки", 30x40 см.
Стильные оригинальные зеркальные наклейки прекрасно дополнят интерьер вашего дома, наполнив его светом и радостью. Декорирование интерьера
351 руб
Раздел: Интерьерные наклейки
Глобус детский зоогеографический, 210 мм.
Глобус детский зоогеографический, на пластиковой подставке. Диаметр: 210 мм.
374 руб
Раздел: Глобусы
Пепельница S.Quire круглая, сталь, 110 мм.
Металлическая круглая пепельница S.QUIRE станет хорошим подарком курящим людям. Глубокий контейнер для пепла снабжен съемной крышкой,
361 руб
Раздел: Пепельницы

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

18. Шифрование и дешифрование данных при помощи симметричных криптографических алгоритмов

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

20. В поисках системы мира

21. Поиск внеземных форм жизни

22. Разработка алгоритмов контроля и диагностики системы управления ориентацией космического аппарата
23. Поиск внеземных форм жизни
24. Гидрохимический, атмохический и биогеохимический методы поисков

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

26. Образное воплощение творческого поиска Н.Гумилева

27. Поиск романтического идеала в русской литературе XX века

28. Рекурсивные алгоритмы

29. Межкультурная коммуникация в электронной среде и поиск информации в сети Интернет

30. Распределенные алгоритмы

31. Принцип программного управления. Микропроцессор. Алгоритм работы процессора

32. Написание игровой программы Tetris и описание алгоритма

Именная кружка с надписью "Любимая бабушка".
Предлагаем вашему вниманию готовое решения для подарка по любому поводу – именная кружка. Кружка изготовлена из керамики, в нежной
434 руб
Раздел: Кружки
Ящик с крышкой Darel Box на колесах, 61x40x31 см.
Универсальные и герметичные боксы идеально подходят для хранения меха, одежды и домашнего текстиля. Герметичность конструкции обеспечивает
652 руб
Раздел: Более 10 литров
Обложки для переплета, тиснение под кожу, А4, картон 230г/м2, черные, 100 шт..
Обложки для переплета из плотного картона. Актуальны для создания деловых брошюр. Имеют поверхность с текстурой, имитирующей натуральную
402 руб
Раздел: Прочее

33. Поиск информации в www

34. Разработка системы задач (алгоритмы-программы) по дискретной математике

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

36. Алгоритм компактного хранения и решения СЛАУ высокого порядка

37. Поиск клик в графах

38. Практика перевода числа из одной системы счисления в другую + блок-схема алгоритма определения наименьшего числа
39. Методы поиска и исследований в преподавании физики
40. Патентный поиск на тему: "Современная оснастка станка" по курсу "Основы научной деятельности"

41. Усилитель мощности системы поиска нелинейностей

42. Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры

43. Методы поиска и исследований в преподавании физики

44. Человек в поисках смысла жизни

45. Оптимальный поиск переносного компьютера (ноутбука) на рынке

46. Иван Грозный: поиск альтернативных путей социально-политического развития Руси

47. В поисках "исторического Валентина"

48. Сравнительный анализ нейросетевых реализаций алгоритмов распознавания образов

Набор для проведения раскопок "Jewerly Excavation. Горный хрусталь".
Набор для проведения раскопок "Горный хрусталь" из серии Jewerly Excavation станет идеальным подарком для юных любителей
373 руб
Раздел: Археологические опыты
Развивающая игра "Таблица умножения".
Благодаря этой красочной и яркой игрушке ребёнок очень быстро выучит таблицу умножения! Набор состоит из игрового поля и 100 разноцветных
442 руб
Раздел: Кассы букв и цифр (без магнита)
Шкатулка для рукоделия, 28x21x15 см, арт. 80887.
Такие шкатулки послужат оригинальным, а главное, практичным подарком, в котором замечательно сочетаются внешний вид и функциональность.
1618 руб
Раздел: Шкатулки для рукоделия

49. В поисках жанра (Новые книги об авторской песне)

50. Андерграунд вечен – как вечны новации и поиск

51. Духовный поиск Андрея Платонова

52. Культура и экономика: поиски взаимосвязей

53. Поиски альтернативы преступному состоянию мира в романе Ф. М. Достоевского «Преступление и наказание»

54. Нравственный и художественный поиск современной литературы
55. Духовный поиск героев В. М. Шукшина
56. Поиски смысла жизни молодыми людьми начала XIX века

57. Проблемы поиска смысла жизни в романе Пушкина "Евгений Онегин"

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

59. Поиски идеального героя (по рассказу «Чудик»)

60. Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.

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

62. Методы и алгоритмы построения элементов систем статистического моделирования

63. Поиск клик в графах

64. К поискам эфира

Антипригарный коврик, многоразовый, 33x40 см.
Антипригарный коврик используется для выпечки кондитерских и хлебобулочных изделий, приготовления пиццы, запекания мяса и рыбы без
311 руб
Раздел: Коврики силиконовые для выпечки
Штора для ванной "Рыжий кот", арт. SC-РЕ09.
Штора для ванной Рыжий кот SC-РЕ09 изготовлена из 100% полиэстера с тефлоновой пропиткой. Материал ценится за свою устойчивость ко
364 руб
Раздел: Занавески
Лоток (сортер), 4 отделения, вертикальный, сборный.
- предназначен для сортировки и временного хранения документов различных размеров, писем, счетов и другой документации - устойчивый на
317 руб
Раздел: Подставки, лотки для бумаг, футляры

65. Интуитивное понятие алгоритма и его свойств

66. Градиентный алгоритм для систем независимости с отрицательными весами

67. Место цифровой рентгенографии в современном алгоритме лучевой диагностики

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

69. Алгоритм иммуногематологического исследования женщин во время беременности

70. Алгоритмы выполнения манипуляций
71. Единый алгоритм успешных продаж
72. Адроны, очарованные мезоны и поиски кварк-глюонной плазмы

73. В поисках пятой силы

74. Алгоритм выживания для науки

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

76. Алгоритмы инопланетной геометрии

77. Поиск, накопление и обработка научной информации

78. Экзистенциально-гуманистический подход Джеймса Бюджентала: человек в поисках самого себя

79. Системный подход и алгоритм управления подготовкой студентов к духовно-просветительской деятельности

80. Алгоритмы трассировки

Сковорода-сотейник алюминиевая с антипригарным покрытием "Alpenkok" AK-1007/28N "Brown Marble", 28.
Диаметр: 28 см. Высота: 7,5 см. Толщина дна: 4 мм. Сковорода-сотейник из литого алюминия. Высококачественное внутреннее антипригарное
856 руб
Раздел: Сковороды с антипригарным покрытием
Машинка "Кабриолет. Шейх".
Игрушечный кабриолет «Шейх» представляет собой уменьшенную модель настоящего роскошного автомобиля. Машинка изготовлена из гладкого
567 руб
Раздел: Пластиковые машинки
Замок для коляски "Flipper".
Замок для колясок Flipper оснащен надежным механизмом, защищенным также специальной крышечкой от влаги, грязи и пыли. Замок Flipper
388 руб
Раздел: Прочие

81. Усилитель мощности системы поиска нелинейностей

82. Контекстная реклама или лучший способ попасть на первую страницу поиска

83. Вот где задача зарыта! Алгоритм постановки задач рекламной кампании

84. В поисках легендарной Трои

85. Пространство и время: в поисках "естественной онтологии" знания

86. Алгоритм решения обратной задачи вихретокового контроля (ВТК)
87. В поисках "глобального синтеза"
88. Милетская школа. Поиски первоначала

89. Поиски движущих сил общественного развития

90. Поиск новых философских парадигм в России и на Западе на рубеже XIX - XX и XX - XXI веков

91. Поиски альтернативных хладагентов

92. Алгоритм работы процессора

93. В поисках "хорошего лесопользования"

94. Историческая экология: между повседневностью и вечностью, или поиск решений на перекрестке проблем

95. Рискология. Методы верификации информации: сопоставительный анализ, метод поиска противоречий

96. Генетичні алгоритми в СППР

Рюкзак для старших классов "Фантазия", 41x32x14 см.
Рюкзак "Фантазия" предназначен для учениц старших классов и студенток. Поклонницам нежной гаммы цветов придется по вкусу броский
621 руб
Раздел: Без наполнения
Мобиль на детскую кроватку "Music Bed Bell" (свет, звук).
Погремушка станет отличным помощником, она позволит привлечь внимание ребенка. Мобиль на детскую кроватку Music Bed Bell - это отличное
1475 руб
Раздел: Мобили
Швабра отжимная "Хозяюшка Мила", KF-08.
Отжимные швабры с PVA насадками подходят для влажной уборки и мытья полов из любых материалов: ламинат, паркет, линолеум, керамическая
371 руб
Раздел: Швабры и наборы

97. СППР фінансового аналізу на базі алгоритмів нечіткої логіки

98. В поисках механизмов понимания текстов

99. Если возникнет чрезвычайная ситуация: алгоритмы поведения учащихся и студентов

100. Поиски идеала


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