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

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

Динамическое программирование, алгоритмы на графах

Брелок LED "Лампочка" классическая.
Брелок работает в двух автоматических режимах и горит в разных цветовых гаммах. Материал: металл, акрил. Для работы нужны 3 батарейки
131 руб
Раздел: Металлические брелоки
Чашка "Неваляшка".
Ваши дети во время приёма пищи вечно проливают что-то на ковёр и пол, пачкают руки, а Вы потом тратите уйму времени на выведение пятен с
222 руб
Раздел: Тарелки
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение

Министерство образования Республики Беларусь Учреждение образования «Гомельский государственный университет им. Ф. Скорины» Математический факультет Кафедра МПМРеферат Динамическое программирование, алгоритмы на графах Исполнитель: Студентка Старовойтова А.Ю. Научный руководитель: Канд. физ-мат. наук, доцент Лебедева М.Т.Гомель 2007 СодержаниеВведение 1. Алгоритмы, использующие решение дополнительных подзадач 2. Основные определения теории графов 3. Поиск пути между парой вершин невзвешенного графа 4. Пути минимальной длины во взвешенном графе Заключение Литература Введение Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов. Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его &quo ;коэффициентом полезного действия&quo ; в практическом программировании и решении олимпиадных задач. Иногда решение основной задачи приходится формулировать в терминах несколько модифицированных подзадач. Именно такие проблемы рассматриваются в данной работе. 1. Алгоритмы, использующие решение дополнительных подзадач Задача 9. Требуется подсчитать количество различных разбиений числа на натуральные слагаемые. Два разложения считаются различными, если одно нельзя получить из другого путем перестановки слагаемых. Решение. Для того чтобы подсчитать количество различных разбиений числа на произвольные натуральные слагаемые, предварительно подсчитаем количества разбиений на следующие группы слагаемых: 1) разбиения только на единицы (очевидно, что для любого числа такое разбиение единственно); 2) разбиения на единицы и двойки такие, что хотя бы одна двойка в разбиении присутствует и т.д. Последнюю группу представляет само число . Очевидно, что каждое разбиение числа можно приписать только к одной из рассмотренных групп, в зависимости от значения j — максимального слагаемого в том или ином разбиении. Обозначим количество разбиений в каждой из групп ( , j). Тогда искомое количество разбиений равно сумме разбиений по всем возможным группам. Введение таких подзадач приводит к несложному способу подсчета числа разбиений. А именно, так как в любом из разбиений j-ой группы присутствует число j, то мы можем вычесть из число j и сложить разбиения уже числа – j на слагаемые, не превосходящие j. То есть мы пришли к следующему рекуррентному соотношению: Теперь очевидно, что если мы имеем возможность завести двумерный массив размером ґ , и будем заполнять его в порядке возрастания номеров строк, то задача будет легко решена. Однако легко заметить, что решения части подзадач никак не участвуют в формировании решения. Например, при вычислении количества разбиений числа 10 на слагаемые будут получены, но не использованы значения (9, j) для j = 2.9

и т. д. Для того чтобы не производить лишних вычислений, применим динамическое программирование “сверху вниз” (все предыдущие задачи решались “снизу вверх”). Для этого задачу будем решать все же рекурсивно, используя формулу ( ), но ответы к уже решенным подзадачам будем запоминать в таблице. Первоначально таблица пуста (вернее заполним элементы, значение которых по формуле ( ) равно 0 или 1, а остальные значения, например, числом -1). Когда в процессе вычислений подзадача встречается первый раз, ее решение заносится в таблицу. В дальнейшем решение этой подзадачи берется из таблицы. Таким образом мы получили прием улучшения рекурсивных алгоритмов, а “лишние” подзадачи теперь решаться не будут. Приведем программу для решения этой задачи. var i,j,k, :by e; sum:lo gi ; able:array of lo gi ; fu c io ( ,k:by e):lo gi ; var i,s:by e; begi if able&l ;0 he {остальные элементы не пересчитываем} begi able, ( -k,i)) e d; := able e d; begi read( ); fillchar( able,sizeof( able),0); for i:=1 o do begi able:=1 e d; {неопределенные элементы метим –1} for i:=2 o do for j:=2 o i-1 do able:=-1; sum:=0; for i:=1 o do sum:=sum ( ,i); wri el ('sum=',sum) e d. Задача 10. Плитки (Чемпионат школьников по программированию, Санкт-Петербург, 1999 г.). У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1ґ1. Он выбирает ровно плиток и выкладывает их в полоску. Например, при = 10 она может выглядеть следующим образом: К К К С З К К З К С (Буквой К обозначена красная плитка, С – синяя, З – зеленая) После этого Петя заполняет следующую таблицу, которая в данном примере выглядит так: Красный Синий Зеленый Красный Y Y Y Синий Y Y Зеленый Y Y В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает &quo ;Y&quo ;, если в его полоске найдется место, где рядом лежат плитки цветов А и Б и &quo ; &quo ; в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали – если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски. Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски. Помогите Пете узнать, сколько различных полосок имеет определенную диаграмму смежности (заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска С К З К К З С К К К не совпадает с полоской, приведенной в начале условия.) Первая строка входного файла содержит число . (). Следующие три строки входного файла, содержащие по три символа из набора {“Y”, “ ”}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична. Выведите в выходной файл количество полосок длины , имеющих приведенную во входном файле диаграмму смежности. Ниже дан пример входного и выходного файлов. I pu . x Ou pu . x 10 YYY Y Y YY 4596 Решение.

Очевидно, что перебор всех возможных полосок в данной задаче невозможен, так как их количество может составить 2100, поэтому следует попытаться найти динамическую схему решения. Понятно, что для того чтобы подсчитать количество полосок длины , удовлетворяющих заданной диаграмме смежности, необходимо знать количество допустимых полосок длины – 1, а также количество полосок, в диаграмме смежности которых один диагональный элемент или два симметричных недиагональных элемента равны “ ” вместо “Y” в исходной диаграмме. Далее, при рассмотрении полосок длины – 2, потребуется знать количество полосок, удовлетворяющих еще большему количеству диаграмм смежности и т. д. В результате на каком то шаге нам может понадобиться информация о количестве полосок практически со всеми возможными диаграммами. Общее количество последних составляет 26 = 64 (уникальными, то есть не повторяющимися, а, значит, определяющими количество различных диаграмм, являются только 6 элементов). Так как при увеличении длины полоски диаграмма может измениться в зависимости от сочетания цветов в последнем (новом) и предпоследнем элементах, подсчитывать полоски следует отдельно для трех различных конечных элементов. Таким образом количество хранимой информации возрастает до 64ґ3 = 192 значений. Столько же значений будет получено в результате пересчета. Но благодаря тому, что количество полосок длины i выражается только через количество полосок длины i – 1, хранить нужно лишь эти 2ґ192 = 384 значения. Несмотря на малый размер таблицы (массив o al в программе) следует отметить, что ее размер экспоненциально зависит от одного из входных параметров — количества цветов k, а именно: 2ґkґ2k(k 1)/2. Например, для 8 цветов необходимо было бы хранить 240 элементов, что нереально. Этим данная задача отличается от рассмотренных ранее. Осталось обсудить некоторые технические приемы, позволяющие написать довольно простую программу, реализующую описанный алгоритм. Если мы поставим в соответствие каждому из уникальных мест в диаграмме смежности свою степень двойки от 20 до 25 (см. массив констант magic в программе), то каждой диаграмме может быть поставлен в соответствие номер от 0 до 63, равный сумме тех степеней двоек, которые соответствуют значениям “Y” (см. процедуру fi dcode). Если мы подсчитываем количество полосок для диаграммы с номером j, то совместимость добавляемого цвета k стоявшему ранее последним цвету l согласно диаграмме j можно проверить так: magic a d j &l ;&g ; 0. Данное условие, построенное с помощью битовой операции над целыми числами a d, означает наличие в j-ой диаграмме смежности элемента “Y” на пересечении k-й строки и l-го столбца (соответствующая степень двойки массива magic содержится в двоичном представлении числа j). Выражение j - magic соответствует замене в диаграмме с номером j упомянутого элемента “Y” на “ ” (по другому это выражение можно было бы записать как j xor magic). Подробнее о битовых операциях над целыми числами можно прочитать в . Последний прием заключается в том, что мы не будем на каждом шаге переприсваивать полученные значения элементам массива, предназначенного для хранения результатов предыдущего шага.

Принципиальное отличие от игры в том, что гадание о выборе пути, употребляемое в детской игре, на основе бросания костей или вращения волчка и т.п., в реальном управлении недопустимо, поскольку это передача целесообразного управления тем силам, которые способны управлять выпадением костей, вращением волчка и т.п., т.е. тем, для кого избранный в игре «генератор случайностей» достаточно (по отношению к их целям) управляемое устройство. Если выбирать оптимальное управление на первом шаге, то необходимо предвидеть все его последствия на последующих шагах. Поэтому описание алгоритма метода динамического программирования часто начинают с описания выбора управления на последнем шаге, ведущем в одно из завершающих процесс состояний. При этом ссылаются на «педагогическую практику», которая свидетельствует, что аргументация при описании алгоритма от завершающего состояния к начальному состоянию легче воспринимается, поскольку опирается на как бы уже сложившиеся к началу рассматриваемого шага условия, в то время как возможные завершения процесса также определены. Рис. 5 -PК существу метода динамическогоPпрограммирования. Анализ переходов

1. Линейное и динамическое программирование

2. Динамическое программирование

3. Динамическое программирование

4. Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ

5. Динамическое программирование и вариационное исчисление

6. Динамическое и линейное программирование
7. Алгоритм определения динамических характеристик гидроупругих систем для управления гидросооружениями
8. Алгоритмы и структуры данных. Программирование в Cи

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

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

11. Проектування керуючих автоматів Мура та Мілі за заданою граф-схемою алгоритму

12. Разработка статических и динамических библиотек на языке программирования С/C++ в операционных системах UNIX

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

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

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

16. Граф А. А. Аракчеев. Современный взгляд на личность на основе анализа и сравнительной характеристики исторических источников и литературы

Таблетки для посудомоечной машины "Clean&Fresh", 5 in1 (mega).
Таблетки для посудомоечной машины «Clean&Fresh» – чистота и свежесть Вашей посуды в каждой таблетке! Великолепно очищает посуду и содержит
708 руб
Раздел: Для посудомоечных машин
Ящик почтовый с замком, коричневый.
Ящик почтовый с замком. Материал: пластик. Длина: 385 мм. Ширина: 310 мм. Высота: 80 мм.
490 руб
Раздел: Прочее
Настольная игра "Запретный Остров. Приключения для смелых!".
Запретный остров – это семейная кооперативная игра, в которой игроки действуют совместно против игры. Вашей команде дерзких искателей
1215 руб
Раздел: Карточные игры

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

18. Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры

19. Динамическое распределение памяти

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

21. Периферийное устройство ПЭВМ, Характеристика этапов подготовки и решения задач на ПЭВМ в любой системе программирования. Электронная почта, особенности применения

22. Прикладное программирование, 1 семестр
23. Алгоритм Кнута-Морриса-Пратта
24. Программирование ориентированное на объекты

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

26. Объективное программирование

27. Постановка лабораторной работы по теории графов

28. Динамическое распределение памяти

29. Динамическое представление данных

30. Системное программирование

31. Аналитический обзор книги "Программирование на языке ассемблера..."

32. Математическое программирование

Пазл "Киты", 66 деталей.
Пазл собирается на основании в рамке — детали не растеряются и ограниченное пространство подскажет ребёнку правильный размер картины. На
548 руб
Раздел: Пазлы (54-99 элементов)
Дождевик Bambola, ПВХ.
Прозрачный, прочный дождевик для прогулочной коляски, подходит и для колясок с ручкой сзади (крепление задней стороны - на
408 руб
Раздел: Дождевики, чехлы для колясок
Карандаши цветные "Jumbo", двухсторонние, 24 цвета.
Карандаши для рисования, треугольной формы. В наборе: 12 разноцветных, двусторонних карандашей (24 цвета). Мягкие, но при этом очень
608 руб
Раздел: 13-24 цвета

33. Системы программирования

34. Языки программирования

35. Понятие, назначение и составные элементы систем программирования

36. Лекции по высокоуровневым методам информатики и программированию

37. Курсовая работа по основам программирования. Игра "Паровоз"

38. Двунаправленный динамический список
39. Помощь в обучении программированию
40. Программирование на С++

41. Сравнительный анализ языков программирования JavaScript и VBScript

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

43. Общая терминология программирования

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

45. Программирование логической игры на visual basic

46. Тест на языке программирования Visual Basic

47. Учебник по программированию на Java для мобильных устройств

48. Структура и программирование ПЛИС фирмы Altera в САПР Quartus II, её применение в лабораторном стенде

Полотенце вафельное "Райский уголок", банное, пляжное, 100х150 см.
Вафельное полотенце "Райский уголок". Легкое и практичное полотенце удобно использовать на пляже, в бане и в бассейне.
304 руб
Раздел: Большие, ширина свыше 40 см
Глобус Земли, физико-политический, с подсветкой, 320 мм.
Глобус Земли физико-политический, с подсветкой, работает от сети. Диаметр: 320 мм. На пластиковой подставке. Рельефный. Цвет подставки
1159 руб
Раздел: Глобусы
Коробка подарочная "Штамп".
Коробка подарочная. Материал: мелованный, ламинированный, негофрированный картон плотностью 1100 г/м2. Отделка: полноцветный декоративный
302 руб
Раздел: Коробки

49. Билеты по дисциплине "Основы алгоритмизации и программированию"

50. Практика оператора (WINDOWS 95, MICROSOFT WORD 97, MATHCAD, ЯЗЫКИ ПРОГРАММИРОВАНИЯ, ЭЛЕКТРОННЫЕ КНИГИ, VISIO, Norton Utilites 3.0 for Windows 95)

51. Компьютерный файлово-загрузочный полиморфный стелс-вирус ONEHALF 3544, особенности алгоритма и методы борьбы с ним

52. Отчет по практическим занятиям по курсу прикладные задачи программирования на тему Windows, Microsoft Word и Microsoft Excel

53. Руководство по программированию на HTML

54. Понятие об алгоритмах
55. Лабораторная работа №4 по "Основам теории систем" (Послеоптимизационный анализ задач линейного программирования)
56. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

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

58. Теория графов и её применение

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

60. Решение оптимизационной задачи линейного программирования

61. Решение задач линейного программирования

62. Постановка задачи линейного программирования и двойственная задача линейного программирования.

63. Задача остовных деревьев в k–связном графе

64. Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика»

Зеркальце карманное "Бабочка", 8x7 см.
Симпатичное карманное зеркало станет Вашим незаменимым помощником и с легкостью разместится даже в небольшой женской сумочке или кармане.
354 руб
Раздел: Зеркала, расчески, заколки
Кулинарная форма, круглая, регулируемая, 16-30 см, высота 8,5 см.
Кольцо-трансформер решает проблему выбора размера формы раз и навсегда.Используется для выпечки коржей диаметров от 15 до 30 см.Форма
482 руб
Раздел: Формы и формочки для выпечки
Сковорода литая с антипригарным покрытием, 26 см.
Сковорода со съемной ручкой и стеклянной крышкой, утолщенное дно. Диаметр: 260 мм. Высота: 60 мм.
1738 руб
Раздел: Сковороды с антипригарным покрытием

65. Программированное обучение и контроль по физиологии

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

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

68. Расчет линейных цепей методом топологических графов

69. Разработка блока динамического ОЗУ с мультиплексором кода адреса

70. Устройство цифровой динамической индикации на 7 сигментных индикаторах
71. Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры
72. Нейролингвистическое программирование /краткий обзор/

73. Вопросы для программированного контроля по курсу "Механика"

74. Динамические законы и механический детерминизм

75. Алмаз-графит

76. Программирование и планирование в ситуациях коллективного взаимодействия

77. Поліграфічна промисловість України. II роль та перспективи розвитку

78. Риск в задачах линейного программирования

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

80. Невольник чести (о графе Михаиле Воронцове)

Рамка деревянная со стеклом, формат 40х40 см, арт. 2N66.
Размер: 40х40 см. Цвет: клён. Материал: дерево.
404 руб
Раздел: Багетные рамы, для икон
Беговел "Funny Wheels Rider Sport" (цвет: зелёный).
Беговел - это современный аналог детского велосипеда без педалей для самых маленьких любителей спорта. Удобный и простой в
2900 руб
Раздел: Беговелы
Сиденье в ванну, белое.
Материал: экологически чистый пластик. Цвет: белый. Внутреннея ширина от 45 см до 75 см, Размер пластмассового сиденья 37 см длина и 30 см
782 руб
Раздел: Решетки, сиденья для ванны

81. Алгоритм Кнута-Морриса-Прата

82. Пушкин: Граф Нулин

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

84. Графы

85. Ссылочный тип данных. Динамические объекты.

86. Структуры данных и алгоритмы
87. Модель управления конфликтными потоками в классе алгоритмов
88. Задача линейного программирования

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

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

91. Теория графов

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

93. Линейные симметрии многогранника паросочетанийи автоморфизмы графа

94. Об использовании квазираспределения Глаубера-Сударшана для описания динамического хаоса

95. Некоторые алгоритмы реализации UPSCALING

96. Обучение решению математических задач с помощью графов

Увлекательная настольная игра "Делиссимо", новая версия.
В этой милой игре вам предстоит немало потрудиться, так как вы работаете на известную и уважаемую итальянскую пиццерию «Делиссимо». Её
632 руб
Раздел: Карточные игры
Крышка силиконовая универсальная, 31 см.
Универсальная силиконовая крышка изготовлена из высококачественного пищевого силикона — экологичного и долговечного материала. Не теряет
318 руб
Раздел: Крышки
Форма разъемная для кулича Regent "Easy" круглая, 16x12,5 см.
Форма для выпечки разъемная из алюминия с антипригарным покрытием. Удобная застежка. Поверхность устойчива к царапинам. Размер: 16x12,5 см.
581 руб
Раздел: Формы и формочки для выпечки

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

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

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


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