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