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

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

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

Мыло металлическое "Ликвидатор".
Мыло для рук «Ликвидатор» уничтожает стойкие и трудно выводимые запахи за счёт особой реакции металла с вызывающими их элементами.
197 руб
Раздел: Ванная
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее

Введение Теория алгоритмов и практика их построения и анализа является концептуальной основой разнообразных процессов обработки информации. В настоящее время теория алгоритмов образует теоретический фундамент вычислительных наук. Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью проясняются такие понятия как доказуемость, эффективность, разрешимость, перечислимость и другие. Фактически, алгоритм – это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса, т.е. такой набор инструкций, который можно реализовать чисто механически, вне зависимости от умственных способностей и возможностей исполнителя. Как заметил Кнут: «Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер». Эффективность алгоритма определяется анализом, который должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временной сложности процесса. Речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе (естественно, к ним относятся входные наборы, промежуточная и выходная информация), а также физических ресурсах, затраченных исполнителем. В курсовой работе представлены различные подходы и методы использования алгоритмов, приведены оценки сложностей алгоритмов, реализации математических задач с помощью алгоритмов. Проведена краткая характеристика используемых структур данных, эффективность их применения в данной задаче 1. Выбор варианта задания В основе выбора индивидуального варианта задания лежит процедура определения целочисленного остатка от деления выражения Y, образованного суммой номера студента по журнальному списку и числом Х, полученным умножением последней цифры номера группы на 100. После определения значения выражения Y находится остаток от деления для соответствующего списка алгоритмов: Y mod 4 1 – алгоритмы покрытия; Y mod 6 1 – алгоритмы на графах; Y mod 5 1 – алгоритмы сортировки. Мой номер по журнальному списку равен 5, группа АЕ-035. Поэтому имеем Y=5 5 100=505. Получаем такие варианты: А = 505 mod 4 1 = 2; B = 505 mod 6 1 = 2; C = 505 mod 5 1 = 1. Таким образом, имеем следующие алгоритмы: покрытия – по методу «построение одного кратчайшего покрытия», на графах – нахождение самого длинного пути, сортировки – простыми включениями. Постановка задачи. Необходимо ввести таблицу покрытия. Алгоритм должен найти покрытие, близкое к кратчайшему. 2. Алгоритм сортировки 2.1 Математическое описание задачи и методов её решения В общем смысле сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Её цель – облегчить последующий поиск элементов в таком отсортированном множестве. Если у нас есть элементы а1, , а , то сортировка есть перестановка этих элементов в массив ак1, , ак , где при некоторой упорядочивающей функции f выполняются отношения f(ak1)≤f(ak2)≤ ≤f(ak ).

Метод сортировки называется устойчивым, если в её процессе относительное расположение элементов с равными ключами не изменяется. Существуют такие алгоритмы сортировок массива: сортировка с помощью прямого включения, прямого выбора, прямого обмена, включений с уменьшающимися расстояниями, дерева, разделения и другие. 2.2 Словесное описание алгоритма и его работы В силу простоты алгоритм сортировки простыми включениями не требует разделения на подпрограммы. Элементы мысленно делятся на уже «готовую» последовательность а1 а2 и исходную последовательность а1 а . При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется в нужное место. Словесное описание алгоритма сортировки простыми включениями: 0. В готовую подпоследовательность записывается а1, во входную – а2, .а . 1. i = 2. 2 Переносим элемент х = а из входной подпоследовательности в готовую так, чтобы готовая подпоследовательность осталась под сортированной. Для этого: а) расширяем готовую подпоследовательность слева: а0 = х – барьер; б) просматривая элементы готовой подпоследовательности слева направо, находим такой номер j что и ai &l ;=x &l ; ai 1; в) если j=j-1, то переходим к пункту г), иначе расширяем готовуюподпоследовательность справа, сдвигая ее элементы, начиная с ai вправо; г) ai 1 = x д) i = i 1. Если i &l ;= , то переходим к п. 2, иначе сортировка заканчивается. Процесс может закончиться при двух различных условиях: 1) найден элемент с ключом, меньшим, чем ключ x; 2) достигнут конец готовой последовательности. Получается цикл с двумя условиями. Поэтому для некоторого улучшения быстродействия применяется барьер – a присваивается значение ключа x. Проанализируем этот алгоритм. Число сравнений (Сi) при i-м просеивании самое большее равно i-1, самое меньшее – 1; если предположить, что все перестановки из ключей равновероятны, то среднее число сравнения – i/2. Число же пересылок (присваиваний элементов) Mi равно Сi 2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы: Сmi = -1,Mmi =3 ( -1) Cave=( 2 -2)/4,Mave=( 2 -10)/4, Cmax=( 2 -4)/4,Mmax=( 2 3 -4)/2. Минимальные оценки в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки – когда они первоначально расположены в обратном порядке. Очевидно, что приведенный алгоритм описывает метод устойчивой сортировки (см. ). Этот алгоритм можно легко улучшить, поскольку готовая последовательность сама уже упорядочена. Поэтому при поиске подходящей позиции для i-го ключа целесообразно использовать двоичный поиск. При этом такой модифицированный алгоритм носит название метода с двоичным включением. Словесное описание алгоритма сортировки с двоичным включением: 0. В готовую подпоследовательность записывается а1, во входную а2, .а . 1. i = 2 2 Переносим элемент х=аi из входной подпоследовательности в готовую так, чтобы последняя осталась под сортированной. Для этого: а) организуем бинарный поиск места включения х в готовую подпоследовательность: находим срединный элемент готовой подпоследовательности – am, где m =] i/2 (, и сравниваем его с х.

Если am &g ; х то ведем далее поиск в левой половине готовой подпоследовательности, т.е. опять находим срединный элемент и сравниваем его с х и т.д., пока не найдем номер j такой, что ai &l ;=x &l ; ai 1, иначе аналогично ведем поиск в правой половине готовой подпоследовательности; б) если j=j-1, то переходим к пункту в), иначе расширяем готовую подпоследовательность справа, сдвигая ее элементы, начиная с ai вправо; в) ai 1 = х 3. i=i 1. Если i &l ;= , то переходим к п. 2, иначе сортировка заканчивается. Деление пополам производится i log2i. Число сравнений практически не зависит от начального порядка элементов. В нижней части последовательности место включения отыскивается несколько быстрее, чем в верхней, поэтому предпочтительна ситуация, когда элементы немного упорядочены. Фактически, если элементы в обратном порядке, потребуется минимальное число сравнений, если уже упорядочены – максимальное: C≈ log2(log2-log2e±0,5). Однако число пересылок так и остается порядка 2. И на самом деле сортировка уже упорядоченного массива потребует больше времени, чем метод с прямыми включениями (см. ). 2.3 Выбор структур данных Алгоритмы сортировки очень сильно зависят от структуры данных, так что выделяют два класса: сортировку массивов и сортировку последовательностей (файлов). В данной работе рассматривается сортировка массивов. Тип данных «массив» удобен тем, что хранится во внутренней памяти и имеет случайный доступ к элементам, то есть более быстрый, чем у последовательности. Поэтому массивы целесообразно использовать для хранения небольших, часто используемых множеств. Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента (поле) каждого элемента. Её значение называется ключом элемента. Поэтому для представления элемента хорошо подходит тип «запись», что на языке «Pascal» выглядит следующим образом: YPE i em = RECORD key: I EGER; {здесь описаны другие компоненты} E D; Поскольку в алгоритме сортировки используется только ключ элемента, то остальную информацию об элементе можно опустить – считаем, что тип элемента определен как I EGER. Можно выбрать и другой тип, на котором определено общее отношение порядка. Из выше сказанного следует, что в процессе работы потребуются следующие переменные: – количество элементов массива; A – сортируемый массив; i – переменная цикла (по исходной последовательности); j – переменная внутреннего цикла (по готовой последовательности); x – i-й ключ (переносимый элемент). Все переменные целого типа. 2.4 Описание схемы алгоритма Блок-схема данного алгоритма изображена на рис. 2 в Приложении. Алгоритм работает следующим образом. Сначала вводятся исходные данные: длина массива и его элементы (блоки 1, 2), затем организуется цикл по всей длине массива, во время которого ставится «барьер» (блок 3) и проводится сравнение i-го ключа с элементами готовой последовательности (стоящими раньше него). При этом все элементы, большие этого ключа (это условие проверяется в блоке 4), сдвигаются вправо (блок 5). Это происходит до тех пор, пока не встретится элемент меньший либо равный данному ключу (по крайней мере барьеру).

Если хотя бы одно решение отличается от других, переходим к операции 1, где задается новое значение а. Если все три решения равны, считаем результат – полученный а-оптимальный гамильтонов цикл – удовлетворительным решением ЗОК. Последовательность выполнения операций алгоритма показана на графе (рис.9.1). Работа алгоритма «а-оптимум» анализировалась для различных п. При решении задач метод «обогащения» исходного множества ветвей и алгоритм «а-оптимум» использовались совместно. Во всех приведенных случаях такой совместный счет эффективнее алгоритма «а-оптимум» на необогащенном множестве ветвей графа. С соответствующими изменениями предложенные методы «обогащения» и «а-оптимизации» могут использоваться и для задач поиска а-оптимальных простых путей и циклов (или их совокупностей), покрывающих т ? п вершин графа. Рис.9.1. Схема алгоритма «а-оптимум» Глава 10. Экология 10.1. Введение Экология – это вид современной человеческой деятельности, включающий в себя науку, проектирование, образование, анализ, экспертизу, контроль и другие компоненты деятельности, общее содержание которых описано в главе 4

1. Поиск оптимального пути в графе

2. Социализм в поисках "третьего пути"

3. Рациональные методики поиска оптимальных путей сетевых графиков и их автоматизация на ЭВМ

4. Алгоритмы численного решения задач

5. Поиск кратчайшего пути в многоугольнике

6. Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала
7. Графы. решение практических задач с использованием графов (С++)
8. Обучение решению математических задач с помощью графов

9. Стимулирование математической деятельности младших школьников в процессе поиска решения задач с дробями

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

11. Алгоритм возникновения и развития международных конфликтов и возможные пути их решения

12. Максимальное ускорение алгоритма поиска

13. Алгоритмы поиска в тексте

14. Алгоритмы на графах. Независимые и доминирующие множества

15. Алгоритмы поиска подстроки в строке

16. Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)

Игра настольная "Не урони пингвина", 47 деталей.
Комплектация (47 деталей): пингвин, игровое поле, молоток (2 штуки), игровой циферблат с указателем, выбиваемые блоки (2 комплекта по 19
351 руб
Раздел: Игры на ловкость
Кружка "Акула".
Пусть утро станет добрым! Кружка с забавной фигуркой на дне - это шанс вызвать улыбку близкого человека. По мере выпивания напитка фигурка
434 руб
Раздел: Оригинальная посуда
Рюкзак для школы и офиса "SpeedWay 2", 46x32x19 см, серо-оранжевый.
Рюкзак для школы и офиса с отделением для ноутбука с диагональю до 15,6”. 3 больших отделения. 1 передний карман для мелких предметов. 2
1092 руб
Раздел: Без наполнения

17. Способы описания алгоритма. Виды операторов

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

19. Алгоритм раскраски графа (точный)

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

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

22. Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры
23. Информационные потоки в ЭВМ. Алгоритм работы процессора
24. Алгоритмы сортировки

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

26. VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

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

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

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

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

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

32. Использование алгоритмов при изучении орфографии в начальных классах

Пакеты фасовочные "Paclan", 26x35 см, 1000 штук.
Производятся из пищевого полиэтилена и безвредны для человека. Сохраняют свежесть продуктов. Пакеты выпускаются разного размера, что
305 руб
Раздел: Пакеты для продуктов
Декоративная наклейка-ростомер "Ракета", арт. EZG-1001.
Размер: 40x75 см.
366 руб
Раздел: Ростомеры
Набор для составления букета из мягких игрушек "LOVE", 3 зайки.
Яркий и нестандартный подарок - букет из мягких игрушек вызовет восторг у всех, независимо от возраста и положения. К тому же, этот букет
496 руб
Раздел: Дизайнерские игрушки

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

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

35. Генетический алгоритм

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

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

38. Нечетко-логические модели и алгоритмы
39. Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости
40. Интуитивное понятие алгоритма и его свойств

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

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

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

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

45. Алгоритмы выполнения манипуляций

46. Алгоритм развития для науки

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

48. Способ устойчивого решения неустойчивых задач и его алгоритм

Кружка керамическая "FIFA 2018", 1000 мл.
Объем: 1000 мл. Материал: керамика.
1231 руб
Раздел: Кружки, посуда
Корзина "Плетенка" с крышкой, (350x290x175) (бежевый).
Материал: пластик. Ширина: 29 см. Длина: 35 см. Высота: 17,5 см. Цвет: бежевый.
303 руб
Раздел: Корзины для стеллажей
Сковорода-гриль чугунная, со съемной деревянной ручкой, 25x25х4 см (квадратная).
Размеры: 25х25х4 см. Размер рабочей поверхности: 23х23х2 см. Чугунная литая сковорода-гриль со съемной ненагревающейся деревянной ручкой,
620 руб
Раздел: Сковороды гриль

49. Алгоритм определения перечня специальных квалификационных характеристик (компетентностей)

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

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

52. Алгоритм решения обратной задачи вихретокового контроля (ВТК)

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

54. Генетичні алгоритми в СППР
55. Если возникнет чрезвычайная ситуация: алгоритмы поведения учащихся и студентов
56. Алгоритм и программа

57. Генетический алгоритм глобальной трассировки

58. Исполнитель алгоритмов – человек

59. Планирование поставок торговой фирме с использованием имитации и генетического алгоритма

60. Алгоритмы и протоколы маршрутизации

61. Алгоритмы нейрокибернетики

62. Быстрые алгоритмы сортировки

63. Конфигурирования программного обеспечения алгоритма OSPF на маршрутизаторе

64. Понятие алгоритма

Настольная игра "Маленький балансир".
Классическая настольная игра – балансир. Смешные, зеленые лягушата прыгают в пруду, нужно помочь им забраться на кувшинки. Настольная игра
1699 руб
Раздел: Игры на ловкость
Сейф-книга Alparaisa СС0072/1 "Вокруг света", 17х11х5 см.
Размеры: 17х11х5 см. Бокс-сейф в виде книги для хранения мелких ценных вещей. Встроенный замок, запирающийся на ключ. Аксессуары: ключ - 2 штуки.
572 руб
Раздел: Копилки
Магнитный конструктор 3D из 20 деталей.
Магнитный конструктор из 20 квадратов и треугольников различных ярких цветов порадует Вашего ребенка. Изготовлен из высококачественного
997 руб
Раздел: Магнитные и металлические конструкторы

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

66. Алгоритм сжатия "Unbuffered RLE"

67. Алгоритм сжатия видео: рецепторы как кодировщики

68. Методика и алгоритмы контроля работоспособности и диагностики сейсмометрических каналов

69. Анализ алгоритма вируса

70. Реализация алгоритма на ЭВМ
71. Перспективы развития и использования асимметричных алгоритмов в криптографии
72. Реализация алгоритма обработки данных

73. Особенности реализации машинно-ориентированных алгоритмов расчета частотных характеристик канала воздействия

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

75. Граф Л.Н. Толстой: путь к «Войне и миру»

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

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

78. Математическая логика и теория алгоритмов

79. Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

80. Алгоритм внедрения управленческого абсолюта

Набор фломастеров Bic Kid "Couleur", 12 цветов.
Цветные фломастеры со средним пишущим узлом и чернилами на водной основе. Вентилируемый колпачок обеспечивает безопасность при
323 руб
Раздел: 7-12 цветов
Дождевик для коляски "Карапуз".
Дождевик выполнен из плотной непромокаемой ПВХ ткани. Универсален - подходит для любой коляски-люльки. Сезон: всесезонный. Расцветка
755 руб
Раздел: Дождевики, чехлы для колясок
Доска магнитно-маркерная, 45x60 см.
Размер: 45х60 см. Поверхность доски позволяет писать маркерами и прикреплять листы при помощи магнитов. Улучшенный алюминиевый профиль. В
829 руб
Раздел: Доски магнитно-маркерные

81. Алгоритм действий по управлению конфликтом

82. Алгоритм разработки и реализации федеральных целевых программ по развитию проблемных регионов России

83. Алгоритм нейтрализации замечаний и возражений

84. Алгоритм и сравнительная характеристика использования векселей и складских средств при коммерческом кредитовании

85. Горные породы, алгоритмы их определения

86. Алгоритм и его свойства
87. Алгоритм криптографического преобразования в режиме простой замены
88. Алгоритм работы программы "Консультант Плюс"

89. Алгоритми сортування

90. Алгоритмічні мови програмування

91. Алгоритмы вокруг нас

92. Алгоритмы и организация данных

93. Алгоритмы параллельных процессов при исследовании устойчивости подкрепленных пологих оболочек

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

95. Використання генетичних алгоритмів для складання розкладу

96. Интеллектуальные информационные технологии и системы: генетические алгоритмы

Ящик с крышкой Darel Box, 41x30x21 см.
Универсальные и герметичные боксы идеально подходят для хранения меха, одежды и домашнего текстиля. Герметичность конструкции обеспечивает
319 руб
Раздел: Более 10 литров
Планшет для акварели и пастели "Соленый ветер. Венеции", 20 листов, А3.
Планшет для пастели и акварели состоит из 2 цветов рисовальной бумаги (10 листов серого цвета и 10 листов оливкового цвета), что позволяет
345 руб
Раздел: Папки для акварелей, рисования
Цветные карандаши, 12 цветов, в пластиковом пенале.
Первый гибкий пенал для карандашей. Изящное решение: с растягивающимся тубусом. Пенал легко превращается в стаканчик для карандашей.
378 руб
Раздел: 7-12 цветов

97. Компрессия информации и упорядочение дерева по алгоритму Виттера

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

99. Особенности арифметико-логических устройств (АЛУ) с двоично-десятичными кодами (ДДК) при вычислении операций умножения и деления и поиск путей их ускорения


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