Отправляет email-рассылки с помощью сервиса Sendsay

Дистанционное обучение

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 406 RSS
←   Октябрь 2008   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://дистанционный-репетитор.рф
Открыта: 04-12-2005

Автор
Андрей Темнов

Статистика

406 подписчиков
0 за неделю
←   Все выпуски   →

Уроки и методика преподавания информатики для учителей новые горизонты www.thl.narod.ru


Новые горизонты
NP-полные задачи.
Теория сложности классифицирует не только сложность конкретных алгоритмов решения задачи, но и сложность самих задач. Теория сложности рассматривает минимальное время и объем памяти, необходимые для решения самого сложного варианта задачи на теоретическом компьютере, известном как машина Тьюринга. Задачи, которые можно решить с помощью алгоритмов, сложность которых определяется многочленом (полиномиальное время), называют разрешимыми, поскольку обычно при разумных входных данных могут быть решены за приемлемое
время. (Точнее, определение "приемлемости" зависит от конкретных обстоятельств). Задачи, которые невозможно решить за полиномиальное время, называют труднорешаемыми, или просто трудными, поскольку вычисление их решений быстро становится невозможным.
Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними:
P<=NP<=EXPTIME
Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время.
Класс NP включает в себя класс P, поскольку любую задачу, решаемую за полиномиальное время на детерминированной (обычной) машине Тьюринга, можно решить и на недетерминированной за полиномиальное время, просто этап предположения опускается.
Если все задачи класса NP решаются за полиномиальное время и на детерминированной машине, то P=NP. Тем не менее, никем не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.
Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такие задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.
Таким образом, для программиста NP-полнота означает полный перебор, причем сложность этого перебора будет экспоненциальной или факториальной. Но следует понимать, что не всякий полный перебор имеет такую сложность. Наапример, если решать задачи из предвдущего выпуска полным перебором, то сложность полученных алгоритмов будет полиномиальной - O(n^2) для задачи про подпоследовательности и O(n^6) для задачи про подматрицы.
Наконец, существует класс задач EXPTIME. Эти задачи решаются за экспоненциальное время. В настоящее время можно доказать, что EXPTIME-полные задачи невозможно решить за детерминированное полиномиальное время. Кроме того, доказано, что P<>EXPTIME.
Приведем теперь список некоторых задач, которые являются NP-полными:
o ВЕРШИННОЕ ПОКРЫТИЕ ГРАФА. Заданы граф G(V, E) и число K, не превосходящее количества вершин в графе. Нужно выяснить, существуют ли К или меньше вершин таких, что любое ребро в графе содержало хотя бы одну из них.
o РАСКРАШИВАЕМОСТЬ ГРАФА (ХРОМАТИЧЕСКОЕ ЧИСЛО). Заданы граф G(V, E) и число K, не превосходящее количества вершин в графе. Нужно выяснить, можно ли раскрасить вершины графа в K различных цветов так, чтобы концы любого ребра оказались раскрашены в 2 различных цвета.
o ГАМИЛЬТОНОВ ЦИКЛ И ПУТЬ. Задан граф G(V, E). Нужно выяснить, существует ли в данном графе гамильтонов цикл и гамильтонов путь.
o УПАКОВКА В КОНТЕЙНЕРЫ. Дано N предметов, размеры которых S[i]. Требуется определить, можно ли их разбить на K кучек так, чтобы сумма размеров предметов в каждой кучке не превосходила R.
o ЗАДАЧА КОММИВОЯЖЕРА. Задано множество M городов и расстояния между ними D[i,j]. Нужно определить, существует ли маршрут, начинающийся в k-м городе, проходящий через все города по одному разу и заканчивающийся в начальном городе с тем условием, что его длина не превышает K.
o СУММА РАЗБИЕНИЯ. Задано N предметов и их массы M[i]. Требуется определить, можно ли выделить такую группу предметов, чтобы их масса равнялась K.
o РЮКЗАК. Задано N предметов, их массы M[i] и стоимости C[i]. Существует ли такая группа этих предметов, что их суммарная масса не превосходит P, а суммарная стоимость не меньше S. Иногда задача формулируется следующим образом: под P понимают вместимость рюкзака и просят найти максимально возможное S (то есть заполнить рюкзак так, чтобы суммарная стоимость всех положенных в него предметов оказалась наибольшей).
Основное назначение этого списка - дать вам возможность попытаться свести задачи, которые вы подозреваете в NP-полноте к этим: если это удасться, то вы должны, не ища более оптимального решения, грамотно организовать перебор. Разумеется, этот список является далеко не полным. Дополнительную информацию о сложности алгоритмов, а также большой список труднорешаемых задач (более 300) можно найти в прекрасной книге М. Гэри и Д. Джонсона "Вычислительные машины и труднорешаемые задачи".


Этим выпуском мы открываем огромную тему в программировании: "Структуры данных и алгоритмы их обработки". Существует много литературы, посвященной этим вопросам, отметим здесь лишь несколько книг: Д.Э. Кнут, "Искусство программирования", том I "Основные алгоритмы"; А. Ахо, Д. Хопкрофт, Д. Ульман, "Структуры данных и алгоритмы"; Р. Седжвик, "Фундаментальные алгоритмы на C++".
В этом выпуске мы не будем рассматривать собственно структур данных, а лишь коснемся некоторых моментов, связанных с использованием указателей.
Указателем называется переменная, которая хранит адрес в памяти другой переменной. Указатели бывают двух типов: нетипизированные (содержат в себе просто некий адрес) и типизированные (содержат в себе адрес переменной конкретного типа). Рассмотрим примеры:
type PInt = ^integer;
PRec = ^TRec;
TRec = record
a: integer;
pa: PInt;
end;
var r: PRec;
В данном примере у нас есть r - указатель на запись, в которой содержится переменная целого типа и указатель на эту же переменную. Тогда доступ к полю a можно получить двумя способами:
c := r^.a
или
c := r^.pa^
При этом мы считаем, что запись, на которую ссылается переменная r, уже заполнена:
r^.a := 1;
r^.pa := @r^.a;
Здесь ^ - оператор разыменования указателя - получения содержимого памяти по адресу. Обратим ваше внимание на то, что этот оператор применим лишь к типизированным указателям. Оператор @ обратен оператору ^ - он позволяет получить адрес переменной.
Поместим теперь в определение записи TRec еще один указатель – указатель на такую же запись:
type PRec = ^TRec;
TRec = record
a: integer;
pa: PInt;
rec: PRec;
end;
Если поле rec будет указывать на саму запись, то ничего интересного мы не получим. Напротив поле rec может указывать на другую запись, та на третью и так далее. Если на некотором шаге поле rec ни на что не указывает, то оно должно равняться значению nil. Таким образом можно организовывать весьма длинные цепочки. Кроме того, в определение записи можно добавить еще указатели, даже массивы указателей, получая при этом весьма сложные структуры.
Вообще говоря традиционно считается, что указатели - сложная для новичков тема, поэтому, если вы испытываете какие-то трудности с указателями, обратитесь к соответствующей литературе, благо ее сейчас более, чем достаточно, или же пишите нам - мы обязательно объясним вам непонятные моменты. Указатели не только сложная, но и чрезвычайно важная тема, знание которой потребуется от вас в ближайших выпусках.
В избранное