Презентация Полное построение алгоритма. Часть 2. Задача коммивояжера онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Полное построение алгоритма. Часть 2. Задача коммивояжера абсолютно бесплатно. Урок-презентация на эту тему содержит всего 26 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Полное построение алгоритма. Часть 2. Задача коммивояжера
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:26 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:184.00 kB
- Просмотров:49
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Реализация алгоритма. На этом](/documents_6/5383334af805082bdedb06c85275eea5/img1.jpg)
Содержание слайда: Реализация алгоритма.
На этом этапе следует ответить на вопросы:
Каковы основные переменные?
Каких они типов?
Сколько нужно массивов, и какой размерности?
Имеет ли смысл пользоваться связными списками?
Какие нужны подпрограммы (возможно, уже записанные в памяти)
Каким языком программирования пользоваться.
Пункты 1-4 - построение структур данных.
Пункты 5-6 – непосредственное использование языка программирования.
Конкретная реализация может существенно влиять на требования к памяти и на скорость работы алгоритма.
№3 слайд
![Реализация алгоритма. Другой](/documents_6/5383334af805082bdedb06c85275eea5/img2.jpg)
Содержание слайда: Реализация алгоритма.
Другой аспект построения программной реализации - это программирование "сверху - вниз".
Необходимо разбить задачу на элементарные шаги (процедуры), т.е.
преобразовать алгоритм в такую последовательность все более конкретизированных алгоритмов, что окончательный вариант будет представлять собой программу
№5 слайд
![Реализация алгоритма. На](/documents_6/5383334af805082bdedb06c85275eea5/img4.jpg)
Содержание слайда: Реализация алгоритма.
На первом этапе пункт 1 может быть осуществлен вручную, с помощью ввода данных с клавиатуры.
Необходимо определить, что будет на входе и на выходе каждой процедуры.
Для генерации перестановок:
Вход: количество городов (К)
Выход: массив всех перестановок
(от 1 до К, матрица всех возможных путей).
№7 слайд
![Анализ алгоритма и его](/documents_6/5383334af805082bdedb06c85275eea5/img6.jpg)
Содержание слайда: Анализ алгоритма и его сложности
В начале проводится оценка ресурсов:
Как будет использовать алгоритм ресурсы машины, например, память (получение оценок или границ для объема памяти).
Полезно оценить время работы до отладки и программирования.
Необходимо иметь абсолютный (количественный) критерий для сравнения двух алгоритмов, претендующих на решение одной и той же задачи. Более сложный алгоритм должен быть улучшен или отброшен
Когда можно считать решение задачи оптимальным? Когда алгоритм настолько хорош, что его невозможно значительно улучшить.
№9 слайд
![Анализ алгоритма и его](/documents_6/5383334af805082bdedb06c85275eea5/img8.jpg)
Содержание слайда: Анализ алгоритма и его сложности
Пусть fA(n) - рабочая функция, дающая верхнюю границу для максимального числа основных операций (сложение, сравнение), которые должны быть выполнены алгоритмом А для решения задачи размерности n.
Критерий оценки качества алгоритма А основан на времени работы в худшем случае:
Алгоритм А - полиномиальный, если fA(n) растет быстрее, чем полином от n.
В противном случае алгоритм А называется экспоненциальным (ехр)
Последовательные или параллельные машины более или менее способны воспринимать полиномиальные алгоритмы для задач большой размерности, а на экспоненциальных задачах они довольно быстро "задыхаются".
№10 слайд
![Анализ алгоритма и его](/documents_6/5383334af805082bdedb06c85275eea5/img9.jpg)
Содержание слайда: Анализ алгоритма и его сложности
Введем обозначения:
Функцию f(n) обозначим как О[g(n)] и будем говорить, что она порядка g(n) для больших n, если
lim f(n)/g(n)=const0
Функцию f(n) обозначим как o[z(n)] и будем говорить, что она порядка z(n) для больших n, если
lim f(n)/z(n)=0
Если f(n)=О[g(n)], то эти две функции возрастают с одинаковой скоростью при n, то есть эти два алгоритма одного класса, они одинаково растут.
Если f(n)=o[z(n)], то z(n) растет горазда быстрее, чем f(n).
№13 слайд
![Анализ алгоритма и его](/documents_6/5383334af805082bdedb06c85275eea5/img12.jpg)
Содержание слайда: Анализ алгоритма и его сложности
"Задача коммивояжера"
Размерность задачи - n.
Оценка времени работы алгоритма O(n!), так как количество перестановок первых n-1 положительных целых чисел (n-1)!,
т.е., эта часть алгоритма потребует O(n-1!) шагов. В каждой перестановке можно найти путь и его стоимость за O(n) шагов (т. к. n сумм.)
fА(n)=O[n(n-1)!]=O(n!) - верхняя граница для общего времени работы.
№14 слайд
![Анализ алгоритма и его](/documents_6/5383334af805082bdedb06c85275eea5/img13.jpg)
Содержание слайда: Анализ алгоритма и его сложности
Пусть размерность n=20
время выполнения одной операции:
(сравнение, сложение, поиск элемента матрицы) - 10-7 сек.
Тогда 20!21018
(по формуле Стирлинга n!=210n-2)
С2101810-7=С21011 (70 веков),
где С - константа.
Замечание: Умные люди все это вычисляют на стадии разработки алгоритма, а не после того, как запрограммируют.
№15 слайд
![Проверка программы](/documents_6/5383334af805082bdedb06c85275eea5/img14.jpg)
Содержание слайда: Проверка программы
Эксплуатации программы предшествует её отладка.
Отладка программы - экспериментальное подтверждение того факта, что программа делает именно то, что должна.
Проверка вручную: рассматривается задача небольшой размерности и все просчитывается на бумаге, если есть сравнение - пример на каждую ветвь (таблица истинности).
Тестирование каждого участка программы, т.е., множество выводов всех возможных крайних случаев
если все случаи проверить практически невозможно, то проверить только те, которые встретятся с наибольшей вероятностью
№16 слайд
![Проверка программы](/documents_6/5383334af805082bdedb06c85275eea5/img15.jpg)
Содержание слайда: Проверка программы
Особенности ОС, которые могли не учесть. (Пример с фирмой МS).
Проверка качества алгоритма.
Какие были сделаны допущения.
Учесть все возможные варианты.
Работает ли алгоритм лучше в среднем, чем в худшем случае. (п.6)
Тестирование для определенных вычислительных ограничений.
Анализ среднего функционирования.
№17 слайд
![Проверка программы Многие](/documents_6/5383334af805082bdedb06c85275eea5/img16.jpg)
Содержание слайда: Проверка программы
Многие программы для некоторых входных данных работают хорошо, а для других плохо.
Характеристика работы алгоритма должна меняться плавно от хорошей к плохой при переходе от входных данных, на которых алгоритм работает хорошо, к входным данным на которых это не так.
"Задача коммивояжера"
При n6 работает хорошо.
При 6n15 плохо.
При n15 просто ужасно.
№18 слайд
![Проверка программы Из](/documents_6/5383334af805082bdedb06c85275eea5/img17.jpg)
Содержание слайда: Проверка программы
Из формулировки задачи вытекает необходимость проверки работы программы по крайней мере на двух тестах.
Пусть, например, в задаче требуется подсчитать количество окружностей, каждая из которых проходит хотя бы через три различные точки из заданного множества, в котором не меньше трех точек.
Тогда в качестве тестов заведомо необходимо взять:
множество точек, лежащих на одной прямой (с ожидаемым сообщением об отсутствии искомых окружностей),
множество, в котором не все точки лежат на одной прямой
в этом случае тест должен содержать ответ -- сколько требуемых окружностей должна обнаружить программа с учетом приближенности вычислений, о которых говорилось ранее).
№19 слайд
![Проверка програмы Далее,](/documents_6/5383334af805082bdedb06c85275eea5/img18.jpg)
Содержание слайда: Проверка програмы
Далее, всякий раз, когда в алгоритме, решающем задачу, происходит разветвление, набор тестов необходимо пополнить так, чтобы иметь возможность пройти каждую из ветвей.
Аналогично, если встречается оператор цикла с условием продолжения, то в наборе должен появиться тест, на котором тело цикла не выполняется ни разу, а также тест, на котором тело цикла выполняется хотя бы один раз
№21 слайд
![Составление документации](/documents_6/5383334af805082bdedb06c85275eea5/img20.jpg)
Содержание слайда: Составление документации:
Описание алгоритма на языке, понятном для человека, не связанного с предметной областью
Описание исходных и выходных данных
Описание программы (алгоритма)
Руководство по вводу либо корректировке данных
Особенности функционирования программы (особые случаи, ограничения)
Контрольный пример (примеры расчетов)
№22 слайд
![Описание алгоритма и данных](/documents_6/5383334af805082bdedb06c85275eea5/img21.jpg)
Содержание слайда: Описание алгоритма и данных
Самое главное - оформлять в том виде, в котором хотелось бы читать.
Следует учесть, что ваше описание должны понять люди, не владеющие предметной областью.
Описать план алгоритма «сверху – вниз».
Описать форматы данных и требования к вводу - выводу.
№23 слайд
![Описание алгоритма При](/documents_6/5383334af805082bdedb06c85275eea5/img22.jpg)
Содержание слайда: Описание алгоритма
При составление больших программ (систем) возникает необходимость разбивать задачу на подзадачи, чтобы над каждой могла работать отдельная группа людей.
Разные группы должны контактировать между собой, так как выход из одной задачи это вход в другую.
Основная ошибка - что-то неправильно описали.
№24 слайд
![Особенности функционирования](/documents_6/5383334af805082bdedb06c85275eea5/img23.jpg)
Содержание слайда: Особенности функционирования
Указать условия функционирования и ограничения. Указать также, в каких случаях программа работает, а в каких не работает или работает плохо.
Привести доказательство правильности функционирования алгоритма.
Приложить описание тестовых примеров и результаты тестирования.
Описать порядок настройки программы на конкретные условия функционирования.
№25 слайд
![Задание к практической работе](/documents_6/5383334af805082bdedb06c85275eea5/img24.jpg)
Содержание слайда: Задание к практической работе:
Решение задачи коммивояжера
Программирование исчерпывающего алгоритма для задачи коммивояжера.
Дополнить задачу коммивояжера (исчерпывающий алгоритм) процедурой генератора перестановок
Докажите, что если матрица стоимостей в задаче коммивояжера с n городами симметрична, то число разных по стоимости путей (гамильтоновых циклов) равно (n-1)!/2
Скачать все slide презентации Полное построение алгоритма. Часть 2. Задача коммивояжера одним архивом:
Похожие презентации
-
Полное построение алгоритма. Часть 1. Задача коммивояжера
-
Алгоритмы и программы. Решение олимпиадных задач
-
NP-складність і NP-повнота. Приклади наближених алгоритмів для NP-повних задач. Лекція 4
-
Построение и анализ эффективных алгоритмов
-
Алгоритмы. Задачи алгоритмизации
-
Алгоритм построения конкурсно-игровой программы
-
Построение блок-схем к задачам линейной, разветвляющей и циклической структур
-
Задачи о строках. Задачи повышенной сложности об алгоритмах на строках
-
Алгоритмы и величины. Этапы решения задач на компьютере
-
Конструирование алгоритма. Последовательное построение алгоритма. (Урок 46)