Математическая машина Тьюринга и вычислительная сложность (400,00 руб.)

Стр.1

Стр.2

Стр.3

М.С. Мирзоев, А.Э. Сатторов, И.Т. Джонмахмадов И ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ Учебное пособие МАТЕМАТИЧЕСКАЯ МАШИНА ТЬЮРИНГА МОСКВА 2020

Стр.1

УДК 510.52. ББК 22.19 М 63 М 63 Математическая машина Тьюринга и вычислительная сложность: Учебное пособие / М.С. Мирзоев, А.Э. Сатторов, И.Т. Джонмахмадов. — М.: Прометей, 2020. — 88 с. Мирзоев М.С. ISBN 978-5-00172-033-1 В учебном пособии изложены подходы к формализации понятий алгоритма. В нем уточняется понятие алгоритма через математическую машину Тьюринга и машину с неограниченным количеством регистров (МНР) и рассматриваются некоторые оценки сложности алгоритмов. Помимо теоретических и практических материалов пособие содержит задания для самостоятельной работы. Содержание учебного пособия соответствует Федеральному государственному образовательному стандарту высшего образования третьего поколения и методическим требованиям, предъявляемым к учебным изданиям. Пособие адресовано учителям информатики, преподающим информатику в профильных классах, а также предназначено для студентов высших учебных заведений, обучающихся по направлению педагогического образования профилей «Информатика и математика», «Физика и информатика», «Технология и информатика», «Математика и информатика», «Прикладная информатика». Пособие может быть полезно широкому кругу читателей, интересующимся основами теории вычислимости. ISBN 978-5-00172-033-1 © Мирзоев М.С., Сатторов А.Э., Джонмахмадов И.Т., 2020 © Издательство «Прометей», 2020

Стр.2

ОГЛАВЛЕНИЕ Введение .............................................. 4 ГЛАВА 1. УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА С ПОМОЩЬЮ МАШИНЫ ТЬЮРИНГА .................. 7 1.1. Математическое понятие машины Тьюринга. Алфавит машины Тьюринга. Основные операции над машиной Тьюринга . . . . . . . . . . . . . 7 1.2. Понятие конфигураций машины Тьюринга (МТ) .. 9 1.3. Операции над машинами Тьюринга .......... 12 1.4. Базис элементарных машин Тьюринга ........ 17 Универсальная машина Тьюринга ........... 22 1.5. Правильная вычислимость функции по Тьюрингу. Эквивалентность двух уточнений алгоритма .......................25 1.6. Уточнение понятия алгоритма через машину с неограниченными регистрами ..............32 Контрольные вопросы ......................... 38 Практические задания......................... 39 ГЛАВА 2. АНАЛИЗ И СЛОЖНОСТИ АЛГОРТМОВ ..... 41 2.1. Введение в теорию сложности вычислений..... 41 Меры сложности.......................... 56 2.2. Классы сложности ........................ 63 2.3. Введение в теорию NP-полноты.............. 67 2.4. Полиномиальная сводимость и полнота ....... 74 Контрольные вопросы ......................... 80 Литература ......................................... 81 Приложения ........................................ 83 — 3 —

Стр.3