Редактирование: Методы оптимизации, 01 лекция (от 08 февраля)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

== Методы оптимизации ==

МО в хороших университетах для студентов по специальности прикл. математика --- 6 семестров, но у нас полугодовой курс, но это будет предлагать самостоятельную работу, будут давать задачи, их решение висит на сайте, но рекоммендуется рисовать их самостоятельно. В Америке по статистике 70 процентов функционально неграмотны. Это не есть обязательая мера. Для всех, кто хочет сдавать досрочно это обязтельная мера, а также для тех, кто обучается 4 года.

Курс для этого потока непохож на те, которые читаются для 1/2 потоков, там годовой курс, и попросили сделать упор на дискру.

== Теория сложности ==
Лекции 4 будет занимать, основной набор задач по этой теме, эта же тема будет продолжаться в курсе ИО.

=== Литература ===
* М&nbsp;Гэри, Д.&nbsp;Джонсон. «Вычислительные машины и трудно решаемые задачи», М., Мир, 1982 год
* Х.&nbsp;Пападимитриу, К. &nbsp;Сталиц, «Комбинаторная оптимизация», М. Мир, 1985 год

=== Что такое теория сложности ===
В чём цель прикладная? Если мы псомотрим, как двигалась научная мысль, то увидим, что сначала люди решали дискретные задачи. Если надо почитать площать, длину, то разбивали на кусочки. Но так считать тяжело. Потом Ньютон придумал флюксии, появился анализ… При этом забыли, что дискретные задачи решать сложно.

В конце 60-х годов народ понял, что переборные алгоритмы для существующих задач это сложно. И выяснилось, что да, есть задачи, для которых можно построить алгоритмы, есть задачи, для которых нельзя построить алгоритмы, и возникло направление, которое пыталось доказать по задаче, можно ли найти непереборный алгоритм или нет. На жтом и возникла теория сложности, которая хоть эту задачу не решает, но позволяет классифицировать задачи. В книжке Гэри-Жжонсона приводиться более 550 труднорешаемых задач, они все перечисляются по одной, поскольку основной резултат теории сложности такой: если удасться найти для однофй из этих задач найти непереборный алгоритм или доказать, что такого алгоритма построить нельзя, то это верно и для всех остальных. Задачи разного плана: теория графов, сети, головоломки, оптимизация БД…

=== Термины ===
<div class="definition">'''Решить задачу оптимизации''' — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Униыерситета», это значит написать программу решения определённого класса задач.</div>

Основное понятие — массовая задача (П)

<div class="definition">'''Массовая задача''' — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.</div>

# Задача характеризуется списком параметров (имеются в виду свободные параметры задачи) (конкретные параметры &rarr; I)
# Требования к решению. Задача поставлена &hArr; поставлены требования к решению.

Классической задачей, модельной задачей, массовой задачей, основной задачей является задача ''коммивояжёра''.

Формулировка: имеется набор городов C = {c1, …, cn}, имеются расстояния между городами, полагаем, что они больше нудя: {dij = d(ci, cj)} > 0 | ci, cj &isin; C}. Коммивояжр должен выйти из города, обойти все, затратив наименьшее расстояние. Другое название — поиск гамильтонова цикла.

Задача имеет воплощение в реальной жизни: вы поступаете не работу, вы или ваши сотрудники ездят по точкам, и вас, как выпускника, просят написать задачу, которая по списку точек выстраивает оптимальный маршрут.

В данном случае C, {dij} — параметры задачи, требования к решению — найти такое &pi: {1, …, m} &rarr; {&pi1, …, &pim} &harr; <math>\min_{T_{1}} \sum_{j=1}^{m-1} d(c_{\pi(i)}, c_{\pi(i+1)}) + d(c_{\pi(m)}, c_{\pi(1))</math>.

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

Можно сказать, что зачем нам кольцевая задача (альтернатива — бездомный коммивояжёр), но это столь же сложная задача.

Похожая задача — поиск минимальной связывающей сети, но эта задача уже решаемая.

Если спросить у человека, что проще — построить минимальную связывающую сеть или закольцевать, то немногие ответят, что связать просто, а закольцевать сложно.

Если же теперь на вход подаём какие-то численные значения, то получаем индивидуальную задачу. Можно сказать, чего проще, у нас конечные множества, можно перебрать все варианты. Чтобы рассеить все иллюзии, достаточно сказать, что число вариантов для m городов равно m!. Табличка:
{|
 !m
 !m!
 |-
 |5
 |120
 |- 
 |8
 |40320
 |-
 |10
 |3,6 &times; 106
 |-
 |13
 |6,2 &times; 109
 |-
 |15
 |1,3 &times; 1012
 |-
 |30
 |2,7 &times; 1032
 |}

У телефонной сети была задача обхода автоматов и вытаскивания из них жетонов, совершенно нерешаемая задача. В книге Гэри-Джонса есть замечательная картинка, в которой босс даёт сотруднику задачу, он пытается её решить, придумывает алгоритмы, но они все переборные.

Кроме первичных понятий будем использовать понятие алгоритма (A), понимать под этим формально следующее:

Алгоритм (А) — программа для машины Тьюринга.

Алгоритм А решает массовую задачу П, если для любои индивидуальнй задачи алгоритм применим, т. е. останавливается за конечное число шагов, и даёт решение: A решает П, если &forallI &isin; П А применим и даёт решение I.

Мы будем заниматься массовыми задачами распознавания свойств.

П — задача распознавания свойств, если в качестве требования к решению является ответ «да» или «нет».

Большинство задач без особых качественных изменений записываются в виде задач распознавания свойств, например, для задачи коммивояжёра: мы должны задать число B, которое является критической длиной маршрута, и вопрос выглядит таким образом: «существует ли маршрут длины &le; B?».

Задачи в этих постановках по сложности эквивалентны, то есть, если будет найде алгоритм для задачи распознавания свойств, то \, не сильно увеличив сложность алгоритма, можно указать алгоритм для исходной задачи.

Также будут применяться следующие обозначения:

* D — множество значений параметров задачи
* Y — множество значений параметров, для которых соответствующая индивидуальная задача имеет ответ «да»

Этот набор (D, Y) полностью характеризует задачу распознавания свойств. Например, для задачи коммивояжёра:

* D = {C = {c1, …, cn}, {dij = d(ci, cj)} > 0 | ci, cj &isin; C}, B}, dij, B &isin; '''Z+'''

Если есть алгоритм, который останавливается за конечное число шагов, то для того, чтобы найти сложность алгоритма, нужно связать количество шагов с длиной входного слова. Для того, чтобы формализовать размер задачи, с каждой проблемой П нужно свзяать некую схему кодирования (кодировку) для задания параметров.

Схема кодирования (кодировка): необходимо ввести алфавит &Sigma; — множество, состоящее из конечного числа символов <math>{|\sigma_i}|_{i=1}^k, k < \infin</math>, &Sigma;* — множество слов для алфавита, слово — конечный набор букв, слово будем обозначать &sigma = {&sigma;i, &sigma;j, &sigma;k, …}. Кодировка — e: П &rarr; &Sigma;*, &forall;I &rArr; e(I) = &sigma; &isin; &Sigma;* — отображение массовой задачи в множество слов, индивидуальная задача отображается в слово.

Можно сказать, что отображение параметров задачи. Отображение должно удовлетворять следующим свойствам:
* Возможность декодирования однозначного: &forall;I1 &ne; I2, e(I1) &ne; e(I2)
* Само кодирование и процесс декодирования должны быть полиминальной сложностиЮ e, e-1 — полиномиальные вычисления
* Неизбыточность кодировки: для любой другой кодировки, удовлетворяющей свойствам 1 и 2 найдётся такой полином от n, что для любого натурального n найдётся такая задача I, что длина входа задачи I: <math>\exist p'(\dot) \forall n \exist I: |e(I)| = n \le p'(|e'(I)|)</math> — не существует кодировки, которая на порядок лучше

Обычно встречаемся с кодировкой чисел. Какие бывают кодировки: двоичная. Например, есть число N, в двоичной кодировке получаем число N2 = (1, 0, …, 1), |N2| = log2 N, можно взять другую систему: |N10| = log10 N, и в данном случае порядок соответствует.

Другая кодировка: кодирование палочками, длина слова |N1| = N = 2log2 N, и эта кодировка избыточная, так как в этом случае получаем не полином а экспоненту.

'''Задача 1'''. Предложить (неизбыточную) кодировку для задачи коммивояжёра и оценить длину входа.

В книге Гэри-Джонсона есть оценка, которая выглядит следующим образом: <math>m + \lceil log2 B\rceil + max_i, j \lceil log_2 dij\rceil</math>

Просьба: задачи решать-сдавать, не списывать (лектор готова брать листочки, где указаны максимум 5 человек).

Всем этим задачам (выявления свойств) соответствует &Sigma;*, части их соответствует ответ «да», будем назыать эти слова правильными. Множество правильных слов — язык.

Язык — множество слов, соответствующих правильным решениям: L(&Pi;, e) = у(Н) = {&sigma; &isin; &Sigma;* | &Sigma; — алфавит e, &sigma; = e(I), I &isin; Y}

С любым алгоритмом А, который решают задачу распознавания свойств, связывается язык: A &rArr; L(A) = {&sigma; &isin; &Sigma;* | &Sigma; — алфавит A и A(&sigmal) = qY}

После того, как мы написали алгоритм и написали задачу, мы можем оценить время работы алгоритма.

Время работы алгоритма А, если есму подали на вход слово &sigma; — tA(&sigma;).

<div class="definition">'''Определение 1.''' A решает задачу П с кодировкой e, если язык алгоритма совпадает с задачей П в кодировке E: L(A) = L(&Pi;, e), и для любого слова из их множества алгоритм останавливается: &forall; &sigma; &isin; &Sigma;* A(&sigma;) останавливается</div>

tA(&sigma;) — число шагов до остановки.

<div class="definition">'''Определение 2.''' Временна'я сложность алгоритма A решения задчи П — функция TA(.): TA = <math>max_{\sigma \isin \Sigma^*: |\sigma| \le n} t_A(\sigma), n \isin Z</math></div>

'''Задача 2'''. Дать алгоритм распознавания простоты числа, оценить временную сложность алгоритма. Что такое задача распознавания простоты числа — есть N, на выходе должны получить «да» — N простое, «нет» — N составное.

=== Классы сложности задач ===

'''Определение 3.''' Класс полиномиально разрешимых задач <math>\mathbb{P}</math> = {L(&Pi;, e) | &exist; A решающий &Pi; с кодировкой e, &exist;p(.) — полином: <math>T_{A(n)} \le p(n) \forall n \isin \mathbb{Z}_+</math>

Будем говорить просто: задача принадлежит классу полиномиальных задач: П &isin; P — ежели для неё существует алгоритм с полиномиальной сложностью.

Труднорешаемые задачи — задачи, для которых нет полиномиального алгоритма.

Слово о полиномиальных и экспоненциальных алгоритмах: если есть алгоритм, который имеет полиномиальную сложность, но степено например порядка 7. Это ничем не лучше экспоненты. Но опыт показывает, что через некоторое время появляется алгоритм, который решает задачу с приемлемыми степенями полинома.

Ежели задача не принадлежит классу полиномиальных (П &notin; P), то есть три возможности:
* П неразрешима алгоритмически, то есть, нет алгоритма, который не решает любую индивидауальную задачу. Пример: 10-я проблема Гильберта по многочлену с целыми коэфициентами g необходимо найти, имеет ли уравнение g = 0 целочисленные решения. Было доказано (Матюясевич Ю. М.), что эта проблема алгоритмически неразрешима.
* Запись решения имеет экспоненциальную сложность
* Нет полиномиального алгоритма. Для любой подобной задачи доказано, что не существует полиномиальное решение задачи на МТ, допускающей бесконечный алфавит

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.name/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_01_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_08_%D1%84%D0%B5%D0%B2%D1%80%D0%B0%D0%BB%D1%8F%29

Редактирование: Методы оптимизации, 01 лекция (от 08 февраля)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 13: / Строка 13: @@
 === Что такое теория сложности ===
-В чём цель прикладная? Если мы посмотрим, как двигалась научная мысль, то увидим, что сначала люди решали дискретные задачи. Если надо посчитать площадь, длину, то разбивали на кусочки. Но так считать тяжело. Потом Ньютон придумал флюксии, появился анализ… При этом забыли, что дискретные задачи решать сложно.
+В чём цель прикладная? Если мы псомотрим, как двигалась научная мысль, то увидим, что сначала люди решали дискретные задачи. Если надо почитать площать, длину, то разбивали на кусочки. Но так считать тяжело. Потом Ньютон придумал флюксии, появился анализ… При этом забыли, что дискретные задачи решать сложно.
-В конце 60-х годов народ понял, что переборные алгоритмы для существующих задач это сложно. И выяснилось, что да, есть задачи, для которых можно построить алгоритмы, есть задачи, для которых нельзя построить алгоритмы, и возникло направление, которое пыталось доказать по задаче, можно ли найти непереборный алгоритм или нет. На этом и возникла теория сложности, которая хоть эту задачу не решает, но позволяет классифицировать задачи. В книжке Гэри-Жжонсона приводиться более 550 труднорешаемых задач, они все перечисляются по одной, поскольку основной результат теории сложности такой: если удасться найти для одной из этих задач найти непереборный алгоритм или доказать, что такого алгоритма построить нельзя, то это верно и для всех остальных. Задачи разного плана: теория графов, сети, головоломки, оптимизация БД…
+В конце 60-х годов народ понял, что переборные алгоритмы для существующих задач это сложно. И выяснилось, что да, есть задачи, для которых можно построить алгоритмы, есть задачи, для которых нельзя построить алгоритмы, и возникло направление, которое пыталось доказать по задаче, можно ли найти непереборный алгоритм или нет. На жтом и возникла теория сложности, которая хоть эту задачу не решает, но позволяет классифицировать задачи. В книжке Гэри-Жжонсона приводиться более 550 труднорешаемых задач, они все перечисляются по одной, поскольку основной резултат теории сложности такой: если удасться найти для однофй из этих задач найти непереборный алгоритм или доказать, что такого алгоритма построить нельзя, то это верно и для всех остальных. Задачи разного плана: теория графов, сети, головоломки, оптимизация БД…
 === Термины ===