30. В чем идея генетических алгоритмов?

Интересной разновидностью эвристических алгоритмов являются популярные в последнее время генетические алгоритмы. Они основаны на использовании биологических аналогий, использующих такие понятия, как популяция, ген, мутация, кроссинговер, отбор.

При разработке генетического алгоритма важную роль играет удачный выбор способа кодирования допустимых планов задачи. Каждый план представляется в виде линейной цепочки («хромосомы»), состоящей из некоторых символов или чисел, играющих роль генов. Для хромосом определяются операции мутации (изменения одного или сразу нескольких генов) и кроссинговера (получения новой хромосомы как комбинации двух имеющихся). Важно суметь так определить эти операции, чтобы хромосомы, получающиеся в результате, также кодировали допустимые планы задачи. Дальнейшее понятно: случайным или иным образом выбирается «начальная популяция» хромосом, новые хромосомы образуются с помощью случайных мутаций и кроссинговера, по правилам отбора формируется новое поколение популяции и т.д., смотри учебник биологии.

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

31. Что такое оценка сложности задачи?

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

32. Какую именно сложность мы рассматриваем при изучении теории вычислительной сложности?

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

33. Что такое массовая задача и индивидуальная задача?

Массовая задача - это класс однотипных задач, различающихся значениями исходных данных (в параграфе 1.2 эти данные назывались параметром p). Например, массовыми являются: задача решения квадратного уравнения (с произвольными коэффициентами), задача раскраски графа (любого заданного). Обозначение z  Z означает, что индивидуальная задача z принадлежит классу задач Z (например, Z - задача решения квадратного уравнения, а z - задача решения уравнения 2x² + 5x - 3 = 0).

34. Что является аргументом функций, оценивающих сложность алгоритмов и задач?

Выражение «размерность задачи» слишком расплывчато. При теоретическом анализе сложности используется более четкое понятие «длина описания задачи», под которой понимается количество битов информации, необходимое, чтобы выделить из массовой задачи конкретную индивидуальную задачу. Например, для многих задач теории графов описанием задачи может быть матрица смежности конкретного графа или другая форма задания графа. Для задачи решения квадратного уравнения описание задачи – это три коэффициента уравнения, а длина описания зависит от возможного диапазона значений этих коэффициентов. Если используются двухбайтовые целые коэффициенты, то длина описания равна 6 байтам или 48 битам.

35. Почему машина Тьюринга используется как основная вычислительная модель в теории сложности вычислений?

На самом деле, чем проще, тем лучше (для теоретических доказательств), а потому будем рассматривать только алгоритмы, задаваемые машинами Тьюринга (МТ). Известно, что если н а обычном компьютере (машине фон Неймана) алгоритм можно выполнить за число тактов T, то на МТ его можно реализовать за число тактов £ T3. Таким образом, свойство полиномиальности задачи сохраняется при переходе к МТ. Чем хороша эта старая колымага? С одной стороны, она как-никак умеет выполнять любые алгоритмы. С другой стороны, ее легко можно описать, причем описать формально, и с этим описанием потом можно работать, как с данными: вычислять длину описания, преобразовывать и т.п. Это позволяет доказывать теоремы о МТ.

36. Что такое полиномиальный алгоритм?

алгоритм, имеющий оценку сложности O(n в степени k) для некоторого k

37. Что такое задача распознавания?

С точки зрения теории, удобно предварительно переформулировать исследуемые задачи в форме задач распознавания, т.е. таких, где требуется ответ «Да / Нет». Например, «Имеется ли маршрут коммивояжера короче 1000 км?» или «Есть ли выигрыш у белых в этой позиции?», или «Связен ли данный граф?». Соответствующая МТ читает свой вход (описание индивидуальной задачи распознавания) и должна придти в одно из двух заключительных состояний, соответствующих «Да» (qy) или «Нет» (qn). Все задачи поиска допустимого плана являются, в сущности, задачами распознавания с вопросом: «Существует ли такой план?» (сам план можно рассматривать как побочный результат решения задачи).

38. Что такое класс задач P?

Если для решения задачи имеется хоть один полиномиальный алгоритм, то она относится к классу P

Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть полиномиально зависящим от размера входа. Сюда относится сортировка, поиск во множестве, выяснение связности графов и многие другие.

39. Что такое полиномиальная сводимость задач?

Пусть даны две массовые задачи распознавания Z и Z'. Будем говорить, что задача Z полиномиально сводима к задаче Z' (обозначается Z * Z'), если существует алгоритм A, который переводит описание любой индивидуальной задачи z * Z в описание индивидуальной задачи z' * Z', и при этом:

1) эти индивидуальные задачи эквивалентны, т.е. либо обе имеют ответ «Да», либо обе «Нет»;

2) время работы алгоритма A ограничено некоторым полиномом P(l), где l – длина описания задачи z; очевидно, что той же величиной P(l) будет ограничена и длина описания задачи z'.

40. Как связана принадлежность задач к классу P с их полиномиальной сводимостью?

Пусть даны две массовые задачи распознавания Z и Z'. Будем говорить, что задача Z полиномиально сводима к задаче Z' (обозначается Z µ Z'), если существует алгоритм A, который переводит описание любой индивидуальной задачи z Î Z в описание индивидуальной задачи z' Î Z', и при этом:

1) эти индивидуальные задачи эквивалентны, т.е. либо обе имеют ответ «Да», либо обе «Нет»;

2) время работы алгоритма A ограничено некоторым полиномом P(l), где l – длина описания задачи z; очевидно, что той же величиной P(l) будет ограничена и длина описания задачи z'.

Если для двух массовых задач Z и Z' имеет место полиномиальная сводимость Z µ Z', то можно утверждать следующее:

1) если задача Z' полиномиальна, то и Z тоже полиномиальна (или короче: Z' Î P Þ Z Î P);

2) если Z не является полиномиальной, то и Z' тоже не является (Z Î ~P  Z' Î ~P).

Докажите сами эти несложные утверждения. Подсказка: суть дела в том, что полином от полинома – это тоже полином. Почти стихи.

Запомните твердо, где в этих утверждениях Z, а где Z'. Лучше не зазубривать, а понять.

Отметим также транзитивность отношения полиномиальной сводимости: если Z₁ µ Z₂ и Z₂ µ Z₃, то Z₁ µ Z₃.

41. Что такое недетерминированная машина Тьюринга (НМТ)?

Такая МТ, у которой возможны несколько правил перехода с одинаковой левой частью и различными правыми частями.

42. В чем принципиальность отличия НМТ от детерминированной МТ?

недетерминированной машины Тьюринга (НМТ). Она отличается от обычной (детерминированной) МТ тем, что возможны несколько правил перехода с одинаковой левой частью и различными правыми частями. А как это? Вот машина на очередном такте пришла в состояние, которому соответствуют два или, скажем, десять разных правил перехода: какое из них следует выбрать? По определению НМТ, в этом случае допустимым считается любой выбор правила.

43. Как можно представить себе работу НМТ?

Удобно представлять себе работу НМТ таким образом, как будто выбираются сразу все правила с подходящей левой частью. Машина как бы размножается в нескольких экземплярах, каждый из которых выполняет переход по одному из допустимых правил. Далее все экземпляры работают независимо и могут опять размножаться, если возникает неоднозначность выбора правила. Таким образом, если поведение детерминированной МТ можно представить линейной траекторией переходов из состояния в состояние, то поведение НМТ можно изобразить деревом. Часть ветвей дерева могут быть конечны (экземпляры НМТ приходят в заключительное состояние), другая часть – бесконечны (экземпляры циклятся). Количество ветвей может быть неограниченно большим.