Самостоятельная работа №5 По предмету: Алгоритмы проектирования Алгоритмы на языке «разделяй и властвуй»

Краткое содержание
Короче говоря, сегодня кэш-память установлена ​​"пирамидно". Кэш первого уровня, самый быстрый по скорости, но самый маленький по размеру, является частью кристалла процессора. Они сделаны по той же технологии, что и регистры процессора, поэтому очень дороги, но очень быстры и, главное, надежны. Его размер составляет всего несколько десятков Кбайт, но это очень важно для быстрой обработки. Кэш-память второго уровня может располагаться на том же кристалле процессора.
Понятие о классах R и NP, NP-полных задачах
План:

1. 
   Проблема классов P и NP.
   
2. 
   Докажите, что задача NP-полная.
   
3. 
   Понятие NP-полной задачи
   

Проблема P и NP
Каждый студент, изучающий информатику, должен услышать о проблемах P и NP. Возможно, это самая известная нерешенная проблема в информатике. Одна из 7000-летних призовых задач, выбранных Институтом математики Клэя, с призом в 1 миллион долларов за первое правильное решение, все еще остается открытой. Докажите проблему P = NPили решать информатику, может оказать глубокое влияние на математику, криптографию, искусственный интеллект, обработку мультимедиа, экономику и другие области. Эту проблему можно сформулировать расплывчато
«Любая проблема, которую может быстро исследовать компьютер, также может быть быстро решена компьютером?».
Хотя существование этой проблемы обсуждалось Джоном Нэшем и Куртом Гёделем в 1950-х годах, проблема была официально представлена ​​в 1971 году Стивеном Куком в его знаменитой статье «Сложность процедур обучения теоремам». Прежде чем углубиться в официальное заявление и объяснение проблемы, давайте сначала рассмотрим некоторые определения, относящиеся к теме.
Связанные термины и определения: -

• 
  Слово «компьютер», использованное в двусмысленном заявлении выше, относится к детерминированной машине Тьюринга (DTM). Проще говоря, это машина, которая может выбрать только один этап ключа. Неразветвленная машина. Каждый существующий компьютер работает так.
  
• 
  Многочлен — это выражение, состоящее из переменных, возведенных в определенные степени, и их коэффициентов. Например, квадратное произведение вида ax² + bx + c.
  
• 
  
  Временная сложность алгоритма — это время, затрачиваемое алгоритмом на выполнение, в зависимости от длины входных данных. Обычно обозначается заглавной буквой O. Например, если мы напишем алгоритм для печати всех элементов размера 2n один за другим, его временная сложность будет O(n).
  
• 
  
  Полиномиальная временная сложность — временная сложность алгоритма равна n^{O(1)}.
  
• 
  
  P = Набор задач, которые можно решить за умноженное время с помощью детерминированной машины Тьюринга.
  
• 
  
  NP = множество задач с решениями, которые могут быть решены за недетерминированное полиномиальное время (ответ да или нет), т.е. могут быть решены с помощью недетерминированной машины Тьюринга [4] в кратчайшие сроки.
  
• 
  
  Недетерминированная машина Тьюринга (НТМ) — это машина ветвления. Если есть много возможностей для следующего шага расчета, эта машина может отключить их все одновременно. НТМ способны предсказать правильный вариант из множества вариантов за время O(1).
  

Альтернативное определение NP состоит в том, что при наличии допустимого решения DTM представляет собой набор решений, который позволяет проверить его правильность за полиномиальное время. Следует отметить, что все P-задачи также относятся к NP, потому что, если задача решается многократно с помощью DTM, проверка возможного решения оказывается проще, чем решение.И так, DTM также может выполнять проверку за полиномиальное время. Итак, тривиально, P⊆NP т.е. P является нижней частью NP.
Также важно знать, что все компьютеры, доступные сегодня, являются чисто теоретическими компьютерами, используемыми в мысленных экспериментах DTM и NTM. Как говорит профессор Эрик Демен.
«Так что это (НТМ) очень мощная модель. Конечно, нет компьютеров, которые бы так работали, к сожалению, мне это больше интересно».