Введение в теорию сложности. Методические указания для студентов механико-математического факультета

В данных методических указаниях изложены основы теории сложности алгоритмов и вычислений. Указания составлены на основе лекций, читаемых автором для студентов механико-математического факультета, специализирующихся по кафедре алгебры и дискретной математики. Методические указания предназначены для студентов отделений ''Прикладная математика'' и ''Защита информации'' механико-математического факультета 1 CЛОЖНОСТЬ АЛГОРИТМОВ......Page 3 2 КЛАССЫ СЛОЖНОСТИ......Page 6 3.1 Детерминированная одноленточная машина Тьюринга......Page 8 3.2 Многоленточные машины......Page 9 3.3 Эквивалентность машин......Page 11 3.4 Иерархия классов DTIME......Page 18 4.1 Недетерминированные машины Тьюринга......Page 24 4.2 Классы NTIME, NP и co-NP......Page 26 4.3 Альтернативное определение класса NP......Page 30 5 КЛАССЫ ПО ЕМКОСТНОЙ СЛОЖНОСТИ......Page 32 Вялый М.Н. «Сложность вычислительных задач» : http://www.nat......Page 34