JК
Журнал Компьютерра - 6 от 14 февраля 2006 года :: Компьютерра
Страница: 183 из 198Попробую изложить его здесь более или менее строго, потратив на это константное время (сейчас поймете, что это такое) — как свое, так и читателей.
Предельно коротко и нестрого (зато интуитивно) классы P и NP можно описать так: P — это вычислительные задачи, которые легко решить; NP — задачи, для которых легко проверить, верно ли предполагаемое решение. Перейдем к более точным формулировкам.
Начнем с моделей вычислений. Математические модели компьютеров появились раньше, чем сами электронно-вычислительные машины, но задержка оказалась небольшой. В 1936 году Эмиль Пост (Emil Leon Post), а в 1937 году — Алан Тьюринг (Alan Turing) независимо друг от друга разработали теоретическую модель, которая легла в основу теории алгоритмов. Первый программируемый компьютер — механический агрегат под названием Z3 — был создан уже в 1941 году[ЭНИАК — отнюдь не первый компьютер. Сам ЭНИАК был завершен в 1946 году, но в то время программа, по которой он действовал, была «зашита» в железо, и для перепрограммирования ЭНИАКа нужно было менять его схемы]. Идеальный компьютер очень прост (таково общее свойство большинства полезных математических моделей). Он представляет собой бесконечную в одну сторону (пусть справа) ленту, по которой бегает одна-единственная головка. В каждой ячейке ленты может стоять ноль, единица или не стоять ничего. На каждом шаге выполнения алгоритма головка может сдвинуться влево, сдвинуться вправо либо записать в ячейку, над которой она находится, ноль или единицу.
Предельно коротко и нестрого (зато интуитивно) классы P и NP можно описать так: P — это вычислительные задачи, которые легко решить; NP — задачи, для которых легко проверить, верно ли предполагаемое решение. Перейдем к более точным формулировкам.
Начнем с моделей вычислений. Математические модели компьютеров появились раньше, чем сами электронно-вычислительные машины, но задержка оказалась небольшой. В 1936 году Эмиль Пост (Emil Leon Post), а в 1937 году — Алан Тьюринг (Alan Turing) независимо друг от друга разработали теоретическую модель, которая легла в основу теории алгоритмов. Первый программируемый компьютер — механический агрегат под названием Z3 — был создан уже в 1941 году[ЭНИАК — отнюдь не первый компьютер. Сам ЭНИАК был завершен в 1946 году, но в то время программа, по которой он действовал, была «зашита» в железо, и для перепрограммирования ЭНИАКа нужно было менять его схемы]. Идеальный компьютер очень прост (таково общее свойство большинства полезных математических моделей). Он представляет собой бесконечную в одну сторону (пусть справа) ленту, по которой бегает одна-единственная головка. В каждой ячейке ленты может стоять ноль, единица или не стоять ничего. На каждом шаге выполнения алгоритма головка может сдвинуться влево, сдвинуться вправо либо записать в ячейку, над которой она находится, ноль или единицу.