Курс «Сложность вычислений»


Оглавление (нажмите, чтобы открыть):

Курс «Сложность вычислений»

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

Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область на стыке математики и информатики содержит как «великие» нерешенные задачи (например, P=?=NP, за решение которой, кстати, объявлен приз в $1,000,000), так и красивые теоремы и понятия (например, интерактивные протоколы). Первая часть курса будет посвящена базовым понятиям, конструкциям, фактам в этой области: вероятностные алгоритмы, вычисления с оракулами, полиномиальная иерархия, булевы схемы, интерактивные протоколы.

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

Материалы:

  • Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach.
  • Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  • Oded Goldreich, Foundations of Cryptography. Lecture Notes, Weizmann Institute of Science.
  • Подобные курсы, читавшиеся лектором ранее (с lecture notes и видеозаписями):
    Структурная теория сложности(конспекты)
    Сложностная криптография(конспекты)

Лекции курса

Недетерминированные машины Тьюринга. Классы P и NP. Оптимальный алгоритм Левина. Сводимости, NP-полнота.

NP-полнота задач CIRCUIT-SAT и SAT. Сведение поиска к распознаванию. Существование не NP-полной не полиномиально разрешимой задачи в NP.

Оракульные вычисления. Полиномиальная иерархия. Полнота задачи $QBF_k$. Теоремы о коллапсе. Семейства схем полиномиального размера. Коллапс полиномиальной иерархии как следствие $NP\subseteq P/poly$. Языки во втором уровне полиномиальной иерархии, не имеющие схем фиксированного полиномиального размера.

Вычисления с ограничениями по памяти. Схемы полилогарифмической глубины.

PSPACE-полнота задачи QBF. Иерархии DSpace, DTime, NTime.

Введение в сложность вычислений, Крупский В.Н., 2006

Введение в сложность вычислений, Крупский В.Н., 2006.

Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете
МГУ им. М. В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности
«Защита информации». Излагаются основные идеи и методы теории сложности вычислений.
Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов.

Модели Тьюринга.
Это семейство моделей вычислений наиболее честно отражает время вычислений. Возможных вариантов определения много. Машина Тьюринга состоит из управляющего устройства (УУ) и потенциально бесконечной внешней памяти, структура которой не меняется со временем. Она снабжена программой, задающей правила ее функционирования.

Память разбита на одинаковые ячейки, предназначенные для хранения букв фиксированного конечного алфавита (одна буква в ячейке). Имеется одна или несколько (конечное число) читающе-пишущих головок. В каждый момент времени головка обозревает одну ячейку памяти. За один такт работы головка может изменить содержимое этой ячейки и переместиться к одной из соседних (или остаться на месте). Функционированием головок управляет УУ. В каждый момент времени УУ находится в одном из фиксированного конечного множества внутренних состояний. Один такт работы состоит в следующем: машина читает содержимое обозреваемых ячеек и внутреннее состояние, выбирает из программы инструкцию, однозначно определяемую этими данными, и исполняет ее. В инструкции сказано, каким должно стать новое внутреннее состояние, какие буквы должны быть записаны в обозреваемые ячейки и куда должны переместиться головки.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в сложность вычислений, Крупский В.Н., 2006 — fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России. Купить эту книгу

Лекция 9. Сложность вычислений с помощью алгоритмов

Читайте также:

  1. Активация клиентов MAK с помощью VAMT
  2. Алгоритм и примеры задач, решаемых с помощью алгоритмов
  3. Александр Солженицын. Нобелевская лекция по литературе. 1972
  4. Анализ алгоритмов
  5. Введение ДНК в клетки растений с помощью Ti- и Ri-плазмид
  6. Введение ДНК в растения с помощью Ti- и Ri-плазмид
  7. Вводная лекция
  8. ВВОДНАЯ ЛЕКЦИЯ
  9. Вводная лекция
  10. ВТОРАЯ ЛЕКЦИЯ
  11. ВТОРАЯ ЛЕКЦИЯ. ЯМА.
  12. Выполнение однострочных и многострочных запросов с помощью внедренных операторов SQL и курсоров

ТЕОРИЯ АЛГОРИТМОВ

Понятие о сложности

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

Следовательно, принципиальная алгоритмическая разрешимость ещё не означает практическую реализуемость. Рассмотрим некоторые характеристики вычислений.

Считаем, что при вычислении мы используем алгоритм.

Различают сложность описания алгоритма и исходных данных, и сложность применения алгоритма к исходным данным.

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

Введем следующее определение. Говорят, что неотрицательная функция g(n) есть 0(f(n)) если существует такая постоянная c, что g(n)≤cf(n) для всех, кроме конечного (возможно пустого) множества значений n, <1, 2, 3,…>. В этом случае записываем: g(n)=0(f(n)).

Сложность исходных данных понимается как длина (размер) их записи. Что такое размер входа? Всё зависит от того, что является входом. Размером входа, в общем случае, считают число символов, с помощью которых записан вход.

Пусть входом является целое число. Считаем, что число представлено в системе счисления с некоторым фиксированным основанием. В этих системах число символов, необходимых для представления целого числа n равно ]logAn[, где – основание системы, а ]х[ обозначает наименьшее целое q, такое, что . Известно, что , здесь log2B является константой при фиксированном В. Таким образом, число символов, необходимых для представления целого числа n есть 0(log2n).

Рассмотрим второй пример. Пусть требуется перемножить квадратные n×n матрицы А и В. Ясно, что подходящей мерой сложности исходных данных будет число пропорциональное l= n 2 , имея в виду, что для запоминания отдельного числа (элемента матрицы) выделен определенный объем памяти.

Во многих задачах входом является граф. Граф G=(V,X) можно, например, задать его матрицей смежностей АG=(aij) размера , где aij=1, если ребро и aij=0 в противном случае. Ясно, что максимальное число возможных ребер равно Однако многие графы являются разреженными, т. е. число их ребер много меньше М. В этом случае лучше задать граф перечислением его ребер, с помощью списков смежностей.

При задании списков смежностей для каждой вершины , выписывается множество вершин, смежных с v,

Размер этого представления зависит от суммы длин списков. Каждое ребро вносит вершину в два списка, поэтому сумма длин списков содержит элементов. Но для различения вершин, как правило, вводятся числовые индексы. Так как имеется вершин, то для индексов потребуется двоичных или десятичных разрядов. Следовательно, при таком представлении графа G=(V,X) потребуется символов.

Более экономной записью информации в ячейках памяти ЭВМ (выделенного для одного числа) можно добиться, что для задания графа G=(V,X) требуется ячеек памяти.

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

Кроме того, сложность вычислений зависит от способа формулировки задачи. В качестве примера рассмотрим следующую задачу. Требуется узнать, является ли натуральное число n простым или составным. Чтобы анализировать сложность задачи надо выяснить, как задано число n. Если n задано как произведение своих простых делителей: , то задачи нет вообще; если n задано в унарной форме, т.е. n=11…1, то сложность записи равна (числу единиц), а сложность задачи, как можно показать, равна = (если использовать известный способ решения этой задачи – решето Эратосфена, состоящий в том, что число N последовательно делят на простые числа p1,p2,…, . Если ни на одно из этих чисел N не делится, то оно простое, иначе составное). Если число n записано в десятичной форме, то сложность записи числа (длина записи) равна l=log10n, а сложность решения в этом случае равна =2 l/2 , т.е. сложность решения представляет собой экспоненту от длины записи числа n.

Мастер Йода рекомендует:  Apache PHP XML MySQL для Windows

Следует обратить внимание на то обстоятельство, что одной и той же задаче могут соответствовать разные языки, представляющие условия или входные данные задачи. Это связано со способами кодировки данных. Из всех языков представляющих исходную задачу, выбирается «разумный язык» или разумный способ кодировки её условий. Таким образом, каждой задаче соответствует “разумный язык” её представляющий.

Временная сложность вычислений (алгоритма)

Временная сложность вычислений (алгоритма) характеризует число операций для решения задачи заданного размера.

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

Определим временную сложность алгоритма как число операций в худшем случае по всем входам размера (длины) n. Иначе временная сложность алгоритма это функция, которая каждому входу размера n ставит в соответствие максимальное (по всем индивидуальным задачам размера n) число операций, затрачиваемых алгоритмом на решение индивидуальной задачи этого размера.

Кроме меры сложности в наихудшем случае вводят временную сложность алгоритма А в среднем на входе размера n:

здесь p(ai) – вероятность появления задачи ai; µ(A(ai)) — число операций, затрачиваемых алгоритмом на решение индивидуальной задачи ai; Рn– множество рассматриваемых задач размера n, Рn=< ai>

При изучении сложности алгоритма, в основном интересуются его поведением при применении его к очень большим входам. Различие между сложностями 10n 3 и 9n 3 считаются несущественными, более важен показатель степени, а не коэффициент. Сложность алгоритма оценивается асимптотической сложностью, т.е. порядком роста числа операций при неограниченном росте размера входа. Например, если вход размера n обрабатывается за время cn 2 , где с – некоторая постоянная, то сложность этого алгоритма есть 0(n 2 ), т.е. постоянная с не содержится в оценке. Для практических задач величина этого коэффициента может быть важна, если они различаются существенно. Если время работы алгоритмов А1 и А2 пропорционально, например, 10 10 n 2 и 9n 2 соответственно, то практическое использование алгоритма А1 проблематично.

Для решения выбранной задачи иногда можно использовать различные алгоритмы.

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

Выясним как изменяется эффективность различных алгоритмов с ростом быстродействия ЭВМ на которых реализуются эти алгоритмы.

Пусть имеем 5 алгоритмов различной сложности для решения одной и той же задачи. Положим. что каждое действие алгоритма осуществляется за 1 млс. Характеристики алгоритмов приведены в следующей таблице .

Из этой таблицы видно, что увеличение времени решения задачи, например с 1-ой секунды до одного часа позволяет для алгоритма А1 увеличить размер решаемой задачи в 3600 раз, а для алгоритма А5 только в 2,33 раза.

Предположим, что быстродействие ЭВМ возросло в 10 раз. В нижеследующей таблице показано, как при этом возрастут размеры входов [29].

Из таблицы видно, что увеличение быстродействия в 10 раз даёт возможность для алгоритма А1 увеличить размер входа в 10 раз, а для алгоритма А5 увеличение размера входа практически не произошло. Таким образом, чем большую временную сложность имеет алгоритм, тем меньшее улучшение даёт увеличение быстродействия.

Полиномиальные алгоритмы и задачи. Класс Р

Считается, что алгоритм – полиномиальный или имеет полиномиальную временную сложность, если существует полином p(x) такой, что на любом входном слове длины n алгоритм завершает вычисления после выполнения не более чем p(n) операций.

Ясно, что, алгоритмы А1 и А2, временные сложности которых равны, например, будет считаться полиномиальными, ибо их сложности ограничены полиномами, т.е. имеют порядок не выше, чем и соответственно.

Говорят, что задача разрешима за полиномиальное время или полиномиально разрешима, если для неё существует полиномиальный алгоритм. При этом считается, что задача является «хорошей».

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

Среди полиномиальных алгоритмов быстрыми являются линейные алгоритмы, которые обладают сложностью порядка n, где n – размерность входных данных. К линейным алгоритмам относится школьный алгоритм нахождения суммы десятичных чисел, каждое из которых состоит из n цифр. Сложность этого алгоритма – 0(n).

В класс Р кроме линейных задач попадают, например, следующие задачи.

Умножение целых чисел. Школьный метод умножения 2-х n-разрядных чисел имеет временную сложность порядка . Существует алгоритм Шёнхаге-Штрассена умножения чисел (заданных в двоичной системе счисления) с меньшей сложностью, именно со сложностью порядка .

Умножение матриц. Обычный метод имеет порядок сложности 0(n3). Существует более быстрый алгоритм умножения матриц — алгоритм Штрассена [2] который имеет сложность порядка .

Найти кратчайший путь на графе состоящем из n вершин и m рёбер. Сложность алгоритма 0(mn) .

Быстрое преобразование Фурье требует арифметических операций.

Задача Прима – Краскала – Кэли. Дано n городов. Нужно соединить все города телефонным кабелем так, чтобы общая длина кабеля была минимальной. Эта задача решается с помощью жадного алгоритма сложности .].

Нахождение эйлерова цикла в графе с m рёбрами. Алгоритм нахождения эйлерова цикла имеет сложность порядка 0(m), см., например.

| следующая лекция ==>
Порядок силового расчета | Задачи, для которых не существует полиномиального алгоритма, считаются трудно разрешимыми

Дата добавления: 2014-01-07 ; Просмотров: 1292 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Сложность вычислений и основы криптографии

Курс знакомит со сложностью вероятностных вычислений и теоретическими основами криптографии. Мы изучим вероятностные классы сложности и основные приемы, которые используются для анализа и построения вероятностных алгоритмов, узнаем, что такое интерактивные протоколы, игры Артура и Мерлина, докажем знаменитую теорему Шамира IP=PSPACE, обсудим классы задач подсчета, поговорим о вероятностно проверяемых доказательства и PCP-теореме. В криптографической части курса мы поговорим об односторонних функциях, генераторах псевдослучайных чисел, протоколах с открытым и публичным ключом, привязке к биту и о доказательствах с нулевым разглашением.

Формально курс является продолжением курса Основы вычислимости и теории сложности, но на лекции приглашаются все желающие. Рекомендуется иметь представление о следующих понятиях: машины Тьюринга (детерминированные и недетерминированные), классы P, NP, PSPACE, NP-полнота, полиномиальная иерархия, булевы схемы. Все определения будут напоминаться по просьбе слушателей.

  • S. Arora, B. Barak, Computational Complexity: A modern approach.
  • Ch. Papadimitriou, Computational Complexity.
  • O. Goldreich, Foundations of cryptography.
  • Н.К. Верещагин, Конспект лекций по теоретико-сложностным проблемам криптографии. [pdf]

Курс «Сложность вычислений»

Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа и выхода.

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

Временная сложность алгоритма (в худшем случае) — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных.

Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).

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

Асимптотическая сложность

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

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

Обозначение Интуитивное объяснение Определение
f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически 0), n_0 : \forall(n>n_0) \; |f(n)| \leq |Cg(n)| » style=»max-w /> или 0), n_0 : \forall(n>n_0) \; f(n) \leq Cg(n)» style=»max-w />
f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически 0), n_0 : \forall (n>n_0) \; |Cg(n)| \leq |f(n)|» style=»max-w />
f ограничена снизу и сверху функцией g асимптотически 0), n_0 : \forall (n>n_0) \; |Cg(n)|
g доминирует над f асимптотически 0),\exists n_0 : \forall(n>n_0) \; |f(n)|
f доминирует над g асимптотически 0),\exists n_0 : \forall(n>n_0) \; |Cg(n)|
f эквивалентна g асимптотически


Примеры

  • «пропылесосить ковер» требует время, линейно зависящее от его площади ( Θ(A) ), то есть на ковер, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объем работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
  • «найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей ( O(log2(n)) ), так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за раз (открываний книги). При увеличении объема страниц до ста тысяч, проблема все еще решается за заходов. (См. Двоичный поиск.)
Мастер Йода рекомендует:  Как получить значения CSS переменных с помощью Javascript

Замечания

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

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

Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения [1] . Вместе с тем и понятие «малости» входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения, асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее «эффективных» алгоритмов. Другой пример — фибоначчиевы кучи, несмотря на асимптотическую эффективность, с практической точки зрения программная сложность реализации и высокие значения констант в формулах времени работы делают их меннее привлекательными, чем обычные бинарные пирамиды [1] .

Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом — порядка n+n!/C, где C — постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй — нет, хотя, например, при С=10 (10 10 ) дело обстоит как раз наоборот. [2]

Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ.

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

В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Классы сложности

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

Класс P

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

Класс NP

Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество времени. Следует заметить, что недерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют детерминированной машине Тьюринга с ограниченной памятью. Таким образом, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (т.е. неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.

Проблема равенства классов P и NP

Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.

Знаменитые учёные

  • Стивен Кук
  • Ричард Карп
  • Леонид Левин
  • Александр Разборов
  • Ади Шамир

Примечания

  1. 12Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, Клифорд Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — ISBN 5-8459-0857-4
  2. А. А. Зыков Основы теории графов. — 3-е изд. — М.: Вузовская книга, 2004. — С. 10. — 664 с. — ISBN 5-9502-0057-8

См. также

Ссылки

  • Курсы по теории вычислимости и сложности вычислений
  • Юрий Лифшиц «Современные задачи теоретической информатики». Курс лекций по алгоритмам для NP-трудных задач.
  • А. А. РазборовTheoretical Computer Science: взгляд математика // Компьютерра. — 2001. — № 2. (альтернативная ссылка)
  • А. А. РазборовО сложности вычислений // Математическое просвещение. — МЦНМО, 1999. — № 3. — С. 127-141.

Wikimedia Foundation . 2010 .

Смотреть что такое «Теория сложности вычислений» в других словарях:

Сведение (теория сложности вычислений) — У этого термина существуют и другие значения, см. Сведение. В теории сложности вычислений сведение преобразование одной задачи к другой. В общем случае, если у нас есть алгоритм, преобразующий экземпляры задачи в экземпляры задачи , которые … Википедия

Теория сложности — может ссылаться на: Изучение сложных систем Теория хаоса Теория сложности вычислений Теоретическое рассмотрение Колмогоровской сложности строки, изучаемое в теории алгоритмов, определяемое по длине кратчайшей двоичной программы, которая может… … Википедия

Теория алгоритмов — Теория алгоритмов наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач,… … Википедия

Теория автоматов — Теория автоматов раздел дискретной математики, изучающий абстрактные автоматы вычислительные машины, представленные в виде математических моделей и задачи, которые они могут решать. Теория автоматов наиболее тесно связана с… … Википедия

Модель вычислений — Иные значения см. разделе в Компьютерное моделирование. Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для… … Википедия

Модели вычислений — Иные значения см. разделе в Компьютерное моделирование. Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для… … Википедия

Класс сложности — В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0… … Википедия

АЛГОРИТМОВ ТЕОРИЯ — раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия алгоритм , прослеживаются в математике в течение всего времени ее существования. Однако само это понятие сформировалось лишь в 20 в. и … Математическая энциклопедия

Алгоритмов теория — раздел математики, изучающий общие свойства Алгоритмов. Содержательные явления, приведшие к образованию понятия «алгоритм», прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь… … Большая советская энциклопедия

Машин и механизмов теория — наука об общих методах исследования и проектирования машин (См. Машина) и Механизмов. Наиболее развита часть науки, называемая теорией механизмов, в которой изучаются преимущественно свойства механизмов, являющиеся общими для всех (или… … Большая советская энциклопедия

Вторая лекция мини-курса «Основы теории вычислимости и сложность вычислений»

8 мая в 15:20 в аудитории 1011 состоится лекция «Сложность вычислений» минкурса «Основы теории вычислимости и сложность вычислений». Докладчик Селиванов Виктор Львович.

Цель миникурса – познакомить слушателей с некоторыми понятиями, результатами, методами и приложениями теории вычислимости, теории сложности вычислений и теории автоматов. Сложность вычислений будет проиллюстрирована теорией NP-полноты и теоремами Тарского о разрешимости в теории полей.

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

Курс «Сложность вычислений» Школы анализа данных Яндекса. Лектор Н.К.Верещагин

1. Вычислительные модели. Машины Тьюринга и арифметические алгоритмы.
2. Теорема об иерархии. Сведение задач друг к другу.
3. Класс NP. Сведение задач друг к другу.
4. Теорема Кука-Левина. Доказательства NP полноты.
5. Приближенное решение задач оптимизации.
6. #P полные задачи. Сведения задач подсчета друг к другу.
7. PSpace полные задачи. Определение вычислительной сложности проблем.
8. Вероятностные алгоритмы. Схемная сложность.
9. Интерактивные доказательства. Схемная сложность.
10. Доказательства с нулевым разглашением. Односторонние функции.
11. Односторонняя функция.
12. Применения односторонних функций. Односторонние функции.

Все лекции доступны по ссылке
https://vk.com/v >

001. Вычислительные модели. Машины Тьюринга и арифметические алгоритмы — Н.К.Верещагин — видео смотреть онлайн

002. Теорема об иерархии. Сведение задач друг к другу — Н.К.Верещагин — видео смотреть онлайн

003. Класс NP. Сведение задач друг к другу — Н.К.Верещагин — видео смотреть онлайн

004. Теорема Кука-Левина. Доказательства NP полноты — Н.К.Верещагин — видео смотреть онлайн

005. Приближенное решение задач оптимизации — Н.К.Верещагин — видео смотреть онлайн

006. #P полные задачи. Сведения задач подсчета друг к другу — Н.К.Верещагин — видео смотреть онлайн

007. PSpace полные задачи. Определение вычислительной сложности проблем — Н.К.Верещагин — видео смотреть онлайн

008. Вероятностные алгоритмы. Схемная сложность — Н.К.Верещагин — видео смотреть онлайн

009. Интерактивные доказательства. Схемная сложность — Н.К.Верещагин — видео смотреть онлайн

Комментарии (14)

Роман Халкечев

Ребята, это ШАДовский курс, стоит это явно отметить.

Вячеслав Рудь

Роман, что такое шад?

Роман Халкечев

Вячеслав, https://yandexdataschool.ru/ А вообще есть еще такая штука как поисковик и можно пользоваться ей, когда возникают подобные вопросы 🙂

Ильдар Зарипов

Oxana Oxana

Спасибо за пост, у нас в городе о ШАД и мечтать нечего, только на онлайн надежда

Адам Елдаров

Oxana, там заочка есть

Oxana Oxana

Адам, спасибо, и правда ведь — есть заочка!


Igor Kleiner

Oxana, о шад и не надо мечтать. У них плохой уровень

Mirror Reflection

>21 век >век безлимитного интернета >тысяч образовательных ресурсов и материалов >литературы на любой вкус и цвет >мечтать об оффлайн-обучении, ограниченном во времени и ресурсах, с весомой степенью искажения материала человеческим фактором P.S. комент не баттхёрта ради, just one man’s opinion.

Pavel Shvets

Igor, посоветуйте что-нибудь, будьте добры

Igor Kleiner

Pavel, вы на английском читатет? И что конкретно в области вас интересует?

Pavel Shvets

Igor, можно и на английском, интересуют курсы по оптимизации, графическим моделям и что-нибудь нетривиальное по графам

Методические указания к курсу ”Сложность вычислений” (стр. 1 )

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КУРСУ ”СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ”

Содержание учебной дисциплины

Введение. Определение сложности вычислений. Вычислительные модели. Меры сложности. Сложностные классы P и NP.

Тема 1. Машина Тьюринга как вычислительная модель.

§ 1. Детерминированная машина Тьюринга.

§ 2. Языки, допускаемые машиной Тьюринга.

§ 3. Многоленточная машина Тьюринга.

§ 4. Недетерминированная машина Тьюринга.

§ 5. Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.

Тема 2. Проблемы, решаемые за полиномиальное время

[1], стр.94 — 122 (алгоритмы сортировок)

[1], стр.255 — 279 (умножение матриц)

[1], стр.128 — 161 (операции над множествами)

[1], стр.197 — 251 (алгоритмы на графах).

Тема 3. Труднорешаемые проблемы.

§ 1. Классы P и NP.

§ 3. Полиномиальное сведение.

§ 4. NP – полные проблемы.

4.1. Проблема выполнимости булевой функции (ВЫП).

4.2. NP – полнота проблемы выполнимости КНФ (КНФ).

4.3. NP – полнота проблемы выполнимости 3-КНФ (3-КНФ).

4.4. Проблемы, к которым сводится проблема 3-КНФ:

Проблема независимого множества (НМ).

Проблема узельного покрытия (УП).

Проблема ориентированного гамильтонова цикла (ОГЦ).

Проблемы, к которым сводится проблема ОГЦ:

Проблема неориентированного гамильтонова цикла (НГЦ).

Проблема коммивояжера (ПК)

Тема 4. Другие сложностные классы.

§ 1 Классы PS и NPS. PS — полнота. Булевы фукнкции с кванторами (КБФ).

§ 2. Классы языков, основанных на рандомизации.

Быстрая сортировка как пример рандомизированного алгоритма. Язык рандомизированной машины Тьюринга. Класс RP. Класс ZPP.

Теория

Тема 5. Сложность арифметических проблем.

§ 1. Сложность проверки простоты числа.

§ 2. Сложность вычислений в модулярной арифметике.

§ 3. Рандомизированная полиномиальная проверка простоты.

§ 4. Недетерминированные проверки простоты.

Теория

[3], проверка простоты.

[3], построение больших простых чисел.

[3], алгоритмы факторизации.

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

Теория

[1], приближенные вычисления.

Методические указания к самостоятельной работе

по курсу “Сложность вычислений”

Введение. Определение сложности вычислений. Вычислительные модели. Меры сложности. Сложностные классы P и NP.

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

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

Третий путь аксиоматический, здесь Блюмом были предложены две аксиомы меры сложности. Из доказанных в этой теории теорем следует, что существуют вычислимые функции, не имеющие “наилучшей ” программы вычислений.

Наиболее употребимые меры сложности – время работы машины M (число шагов, переходов) на входе ω до окончания работы, обозначается tM (n), где n – длина слова ω. Другой, часто применяемой мерой сложноcти, является емкость, обозначается SM (n), т. е. максимальная длина используемого участка ленты на всех рабочих лентах, по всем шагам вычисления. Если вычисление не заканчивается, время и емкость считаются бесконечными.

Тема 1. Машина Тьюринга как вычислительная модель.

§ 1. Детерминированная машина Тьюринга.

§ 2. Языки, допускаемые машиной Тьюринга.

§ 3. Многоленточная машина Тьюринга.

§ 4. Недетерминированная машина Тьюринга.

§ 5. Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.

Самостоятельные занятия

В логике с помощью понятия машины Тьюринга строится теория неразрешимых проблем, однако в вычислительной практике чаще приходится иметь дело с разрешимыми, но “трудно решаемыми” проблемами. Выбирая и здесь в качестве вычислительной модели машину Тьюринга, мы руководствуемся тем, что она проста и допускает те же языки, что и компьютер, причем сложность вычислений на машине Тьюринга полиномиальна от числа шагов компьютера.

Машина Тьюринга представляет собой абстрактную вычислительную машину, состоящую из управления с конечным числом состояний и бесконечной ленты, разделенной на ячейки, в каждой из которых хранится один ленточный символ, и одна из ячеек является текущей позицией ленточной головки. Формальная запись машины Тьюринга — это упорядоченный набор M = (X, Q, q 0, F, I), где

X – внешний алфавит символов (букв на ленте), включающий символ Λ;

Q – конечный алфавит внутренних состояний;

q0 – инициальное состояние (начало работы), q0 ∈ Q;

F– множество заключительных состояний, F⊂ Q;

I — множество инструкций, или машинных команд, каждая из которых принадлежит множеству (Q \ F) × X × <→>× Q × X × .

Переходы осуществляются на основе текущего состояния и обозреваемого считывающей головкой символа к следующему состоянию, переписыванию символа и сдвигу головки (вправо R, влево L, на месте S).

Можно определить функцию переходов

δ : (Q \ F) × X* → Q × X* × , где X* — слова в алфавите X.

В случае однозначной функции δ машина Тьюринга называется детерминированной машиной Тьюринга.

Текущей конфигурацией машины Тьюринга называют цепочку значащих (отличных от Λ) символов, записанных на ленте в данный момент времени, вместе с символом состояния, помещенным в цепочку перед обозреваемым символом.

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

В качестве примера рассмотрим работу детерминированной машины Тьюринга, вычисляющей функцию ⎪m — n⎪. Упорядоченную пару натуральных чисел (m, n) представляем как слово 0m10n в алфавите X \ <Λ>= <0,1>, ячейки слева и справа от которого содержат символ Λ.

Курс «Основы теории вычислимости и сложность вычислений»

С 24 по 26 апреля пройдут лекции заключительного курса весеннего семестра Computer Science клуба ‘Основы теории вычислимости и сложность вычислений’.

Виктор Львович Селиванов проведет серию лекций на тему «Основы теории вычислимости и сложность вычислений».

Виктор Львович — заслуженный работник высшей школы РФ, почетный работник науки и техники РФ, главный научный сотрудник лаборатории теоретического программирования Института систем информатики им. А.П. Ершова СО РАН.

Научные интересы В.Л. Селиванова лежат в области математической логики, теории вычислений, теории автоматов, теории сложности и вычислимости в анализе и топологии. Его работы посвящены, в основном, теории вычислимости, иерархиям регулярных языков и сверхъязыков, теории областей Ершова — Скотта, в частности — классификации объектов в указанных областях с помощью сводимостей и определимости. Исследования ведутся в контакте с рядом известных отечественных и зарубежных специалистов в указанных областях.

Место и время:
24 апреля — 15:20 в ауд.1011

Все лекции пройдут по адресу: ул. Кремлевская, д.35

Урок 62
§36. Сложность вычислений
(§36. Сложность вычислений)

Содержание урока

Что такое сложность вычислений?

Что такое сложность вычислений?

Центральная задача теории алгоритмов — выяснить, существует ли алгоритм решения той или иной задачи. Если существует, то возникает следующий вопрос: а можно ли им воспользоваться на практике, при современном уровне развития вычислительной техники? То есть способен ли компьютер за приемлемое время получить результат? Например, в игре в шахматы возможно лишь конечное количество позиций и, значит, только конечное количество различных партий. Следовательно, теоретически можно перебрать все возможные партии и выяснить, кто побеждает при правильной игре — белые или чёрные. Однако количество вариантов настолько велико, что современные компьютеры не могут выполнить такой перебор за приемлемое время.

Что мы хотим от алгоритма? Во-первых, чтобы он работал как можно быстрее. Во-вторых, чтобы объём необходимой памяти был как можно меньше. В-третьих, чтобы он был как можно более прост и понятен, что позволяет легче отлаживать программу. К сожалению, эти требования противоречивы, и в серьёзных задачах редко удаётся найти алгоритм, который был бы лучше остальных по всем показателям.

Часто говорят о временной сложности алгоритма (быстродействии) и пространственной сложности, которая определяется объёмом необходимой памяти. Поскольку память постоянно дешевеет, а быстродействие компьютеров растёт медленно, мы будем рассматривать главным образом временную сложность — время выполнения программы, работающей по данному алгоритму.

В общем случае, говоря о сложности алгоритма, нужно уточнить, о каком исполнителе идёт речь, какие элементарные операции мы используем. Как правило, это один из универсальных исполнителей (во многих случаях универсальным исполнителем можно считать компьютер). Временем работы алгоритма называется количество выполненных им элементарных операций Т. Такой подход позволяет оценивать именно качество алгоритма, а не свойства исполнителя (например, быстродействие компьютера, на котором выполняется алгоритм).

Как правило, величина Т будет существенно зависеть от объёма исходных данных: поиск в списке из 10 элементов завершится гораздо быстрее, чем в списке из 10 000 элементов. Поэтому сложность алгоритма обычно связывают с размером входных данных п и определяют как функцию Т(n). Например, для алгоритмов обработки массивов в качестве размера п используют длину массива. Функция Т(n) называется временной сложностью алгоритма.

Мастер Йода рекомендует:  Canvas API от Facebook
Добавить комментарий