Алгоритм
<<  Алгоритм, событие, или… Формализация понятия «Алгоритм»  >>
Приближенные алгоритмы
Приближенные алгоритмы
Картинки из презентации «Приближенные алгоритмы» к уроку информатики на тему «Алгоритм»

Автор: Kononov. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока информатики, скачайте бесплатно презентацию «Приближенные алгоритмы.ppt» со всеми картинками в zip-архиве размером 67 КБ.

Приближенные алгоритмы

содержание презентации «Приближенные алгоритмы.ppt»
Сл Текст Сл Текст
1Приближенные алгоритмы. НГУ, ауд. 313 16Полиномиальная приближенная схема
четверг 16:00. Лектор: Кононов Александр (PTAS). Семейство приближенных алгоритмов
Вениаминович. 1. для задачи ?, {A?}? называется
2Объект исследования. Np-трудные задачи полиномиальной приближенной схемой, если
оптимизации. 2. алгоритм A? ? (1+?)-приближенный алгоритм
3Что нужно знать! Задача Индивидуальная и время его работы ограничено полиномом от
задача Оптимизационная задача Размер входа размера входа при фиксированном ?. 16.
индивидуальной задачи Алгоритм Временная 17Вполне полиномиальная приближенная
сложность алгоритма Полиномиальный схема (FPTAS). Семейство приближенных
алгоритм Задача линейного программирования алгоритмов для задачи ?, {A?}? называется
NP-трудная задача. 3. вполне полиномиальной приближенной схемой,
4Литература по комбинаторной если алгоритм A? ? (1+?)-приближенный
оптимизации. М.Гэри, Д.Джонсон, алгоритм и время его работы ограничено
Вычислительные машины и труднорешаемые полиномом от размера входа и 1/?. 17.
задачи, Мир, 1982. Х. Пападимитриу, К. 18Алгоритм. Как построить приближенный
Стайглиц, Комбинаторная оптимизация: алгоритм? Изучение комбинаторной структуры
Алгоритмы и сложность, Мир, 1984. Т. задачи. Изучение свойств оптимального
Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн решения. Поиск алгоритмической техники,
Алгоритмы: построение и анализ, Вильямс, которая использует эти свойства. Обобщение
2009. Korte B., Vygen J., Combinatorial и расширение техники и опыта, накопленного
Optimization: theory and algorithms, при построении полиномиальных алгоритмов.
(Algorithms and Combinatorics 21), 18.
Springer, Berlin, 2010. 4. 19Задача линейного программирования. 19.
5Задача. Задача ? определяется 20Полиномиально разрешимые задачи.
следующей информацией: общим списком всех Задача об остовном дереве минимального
ее параметров формулировкой тех свойств, веса Задача о максимальном потоке Задача о
которым должен удовлетворять ответ или, максимальном паросочетании Задача о
другими словами, решение задачи. k-факторе минимального веса ??? 20.
Индивидуальная задача I получается из 21Вопрос о качестве алгоритма. Как
задачи ?, если всем параметрам задачи ? оценить качество алгоритма? Сравнить
присвоить конкретные значения. 5. стоимость получаемых решений со стоимостью
6Размер входа. Размер входа оптимального решения. Найти стоимость
индивидуальной задачи с рациональными оптимального решения также сложно, как и
данными равен числу бит, требуемых для ее само оптимальное решение. 21.
двоичного представления в некоторой 22Как оценить качество алгоритма? Найти
«наилучшей» бинарной кодировке. 6. «хорошую» полиномиально вычислимую нижнюю
7Оптимизационная задача. оценку на стоимость оптимального решения.
Оптимизационная задача ? есть либо задача 22.
минимизации, либо задача максимизации и 23Задача о вершинном покрытии наименьшей
состоит из множества ?? индивидуальных мощности. Дано: Связный граф G = (V, E).
задач; для каждой I ? ?? конечного Найти вершинное покрытие наименьшей
множества Sol? допустимых решений мощности. 23.
индивидуальной задачи I ; функции h? , 24Максимальное паросочетание. Дан граф G
сопоставляющей каждой индивидуальной = (V, E), подмножество ребер M ? E
задаче I ? ?? и каждому допустимому называется паросочетанием, если никакие
решению ? ? Sol? некоторое рациональное два ребра из M не смежны, то есть не имеют
число y(I, ?), называемое величиной общей граничной точки. Паросочетание
решения ?. 7. максимальное по включению. Паросочетание
8Оптимальное решение. Если ? ? задача максимальное по мощности. Размер
минимизации, то оптимальным решением паросочетания максимального по включению
индивидуальной задачи I ? ?? является является нижней границей на стоимость
такое допустимое решение ?* ? Sol? , что оптимального решения задачи «Вершинное
для всех ? ? Sol? выполнено неравенство покрытие наименьшей мощности». 24.
y(I, ?*) ? y(I, ?). Для обозначения 25Алгоритм «Простой». Найти в графе G
величины y(I, ?*) оптимального решения произвольное паросочетание M максимальное
индивидуальной задачи I будет по включению. Выдать множество вершин,
использоваться символ OPT(I). 8. попавших в паросочетание M. 25.
9Задача о вершинном покрытии. Дано: 26Теорема 1.1 Алгоритм «Простой»
Связный граф G = (V, E), веса вершин c: V является 2-приближенным алгоритмом для
? Q+. Найти вершинное покрытие наименьшего задачи «Вершинное покрытие наименьшей
веса. Вершинное покрытие это множество мощности». Оценка качества алгоритма
вершин V? ? V такое, что каждое ребро «Простой». 26.
имеет граничную точку в V? . 9. 27Теорема 1.1 Алгоритм «Простой»
10Алгоритм. Множество исходных данных является 2-приближенным алгоритмом для
(Вход) Последовательность инструкций, задачи «Вершинное покрытие наименьшей
каждая из которых может быть представлена мощности». Оценка качества алгоритма
цепочкой элементарных шагов. Для каждого «Простой».
допустимого входа алгоритм в процессе 28Качество анализа, нижней оценки, …
вычисления выполняет единственно Можно ли за полиномиальное время получать
определенную серию элементарных шагов и решение с гарантированной оценкой лучше
выдает некоторый ответ. 10. чем 2? Можно ли улучшить анализ качества
11Временная сложность алгоритма. Время алгоритма «Простой»? Можно ли построить
работы алгоритма удобно выражать в виде алгоритм, который всегда находит решение с
функции от одной переменной, оценкой лучше чем 2 от предложенной нижней
характеризующей «размер» индивидуальной границы? Существует ли другой алгоритм с
задачи, то есть от ее размера входа. гарантированной оценкой лучше чем 2?
Временная сложность алгоритма ? это 29Точность оценки.
функция, которая каждому входу размера x 30Качество анализа, нижней оценки, …
ставит в соответствие максимальное по всем Можно ли за полиномиальное время получать
индивидуальным задачам время (число решение с гарантированной оценкой лучше
элементарных шагов), затрачиваемое чем 2? Можно ли улучшить анализ качества
алгоритмом на решение индивидуальных задач алгоритма «Простой»? Ответ нет. Можно ли
данного размера. 11. построить алгоритм, который всегда находит
12Полиномиальный алгоритм. Алгоритм с решение с оценкой лучше чем 2 от
рациональным входом называется предложенной нижней границы? Существует ли
полиномиальным, если существует целое k другой алгоритм с гарантированной оценкой
такое что алгоритм работает время O(xk), лучше чем 2?
где x есть размер входа и все числа, 31Сравнение нижней оценки и оптимального
используемые алгоритмом в процессе решения.
вычислений ограничены величиной O(xk) бит. 32Качество анализа, нижней оценки, …
Алгоритм с произвольным входом называется Можно ли за полиномиальное время получать
сильно полиномиальным, если существует решение с гарантированной оценкой лучше
целое k такое что алгоритм работает время чем 2? Можно ли улучшить анализ качества
O(nk) на любом входе состоящим из n чисел алгоритма «Простой»? Ответ нет. Можно ли
и он полиномиальный на рациональном входе. построить алгоритм, который всегда находит
Если k =1 алгоритм называется линейным. решение с оценкой лучше чем 2 от
12. предложенной нижней границы? Ответ нет.
13Np-трудная задача. Задача ? является Существует ли другой алгоритм с
NP-трудной, если к ней сводится некоторая гарантированной оценкой лучше чем 2?
NP-полная задача. Существование точного 33Литература. Approximation Algorithms
полиномиального алгоритма для NP-трудной for NP-hard problems, edited by
задачи влечет P = NP. Почти все интересные D.Hochbaum, PWS Publishing Company, 1997.
дискретные оптимизационные задачи ? V. Vazirani Approximation Algorithms,
NP-трудны. 13. Springer-Verlag, Berlin, 2001. P.
14Что делать с NP-трудными задачами? Schuurman, G. Woeginger Approximation
Решать точно «переборными» алгоритмами Schemes – A Tutorial, chapter of the book
Решать приближенно с апостериорной оценкой “Lecture on Scheduling”, to appear in
точности с априорной оценкой точности Мы 2008. 33.
будем строить приближенные полиномиальные 34Практика. Принадлежит ли задача
алгоритмы с априорной оценкой точности. распознавания существования в сети потока
14. заданной величины к классу NP и почему?
15Приближенный алгоритм. Полиномиальный Записать задачу о вершинном покрытии
алгоритм A называется ?-приближенным наименьшей мощности как задачу ЦЛП.
алгоритмом для задачи минимизации ?, если Записать двойственную задачу к ее линейной
для каждой индивидуальной задачи I ? ?? , релаксации. 34.
A(I) ? ?OPT(I). 15.
Приближенные алгоритмы.ppt
http://900igr.net/kartinka/informatika/priblizhennye-algoritmy-124245.html
cсылка на страницу

Приближенные алгоритмы

другие презентации на тему «Приближенные алгоритмы»

«Свойства и виды алгоритмов» - Последовательность выполнения действий. Выполняемое действие. Полная форма разветвленного алгоритма. Линейный алгоритм. Свойства алгоритмов: Графический способ описания алгоритма (блок-схема). Циклическая алгоритмическая конструкция, в которой условие поставлено в конце цикла. Начало, конец алгоритма.

«Решение алгоритмов» - Алгоритмы внутренних точек с приближенным решением вспомогательной задачи. 1939 – линейное программирование (Канторович). Алгоритмы центрального пути (имеют полиномиальные оценки). Решение вспомогательной задачи. Алгоритмы центрального пути. Метод сопряженных направлений. Метод сопряженных направлений.

«Алгоритм уроки» - Проверку условия. Алгоритмы бывают очень сложными и большими по объему. Бывает, что над алгоритмом трудятся сразу несколько человек. Способы описания алгоритма. Примеры алгоритмов. Как такому ротозею Доверяют пароход? Понятие алгоритма – одно из фундаментальных в информатике. Тема урока «АЛГОРИТМЫ».

«Схема алгоритма» - Разветвляющийся алгоритм (полная форма). Дома я поем, сделаю уроки и сяду играть на компьютере. Иначе придется идти на уроки. Циклический алгоритм. Самостоятельно: После уроков я пойду домой. Пример: Делаю уроки. Конец. Обозначим время буквой t. Самостоятельно: Если на улице пойдет дождь, то необходимо открыть зонт.

«Алгоритм основные понятия» - Блок-схема алгоритма Евклида. Конец алгоритма. Блок-схема алгоритма «пузырьковой» сортировки. Алгоритм сложения двух целых многозначных чисел. Продолжение выполнения. Различают циклы с предусловием и постусловием: Интуитивное понятие алгоритма. В машине БЭСМ была принята трехадресная система команд.

«Приближенное значение числа» - Округление чисел. Обозначив длину отрезка буквой У, получим 6 У 7. Рассмотрим пример №1. Из рисунка видно, что масса тыквы больше чем 3 кг., но меньше чем 4 кг. Значит, 6 – приближённое значение длины отрезка АВ (в сантиметрах) с недостатком, а 7 – с избытком. Рассмотрим пример №2. Говорят, что число 6 получилось при округлении длины отрезка до целых.

Алгоритм

31 презентация об алгоритме
Урок

Информатика

130 тем
Картинки
900igr.net > Презентации по информатике > Алгоритм > Приближенные алгоритмы