Volume 90 pages
2020 year
Математическая машина Тьюринга и вычислительная сложность
About the book
В учебном пособии изложены подходы к формализации понятий алгоритма. В нем уточняется понятие алгоритма через математическую машину Тьюринга и машину с неограниченным количеством регистров (МНР) и рассматриваются некоторые оценки сложности алгоритмов. Помимо теоретических и практических материалов пособие содержит задания для самостоятельной работы.
Содержание учебного пособия соответствует Федеральному государственному образовательному стандарту высшего образования третьего поколения и методическим требованиям, предъявляемым к учебным изданиям.
Пособие адресовано учителям информатики, преподающим информатику в профильных классах, а также предназначено для студентов высших учебных заведений, обучающихся по направлению педагогического образования профилей «Информатика и математика», «Физика и информатика», «Технология и информатика», «Математика и информатика», «Прикладная информатика». Пособие может быть полезно широкому кругу читателей, интересующимся основами теории вычислимости.
В университете на лекциях о машине Тьюринга рассказывали мало и непонятно. Мне нужна была какая-нибудь дополнительная литература на эту тему. Попалась эта книга.
Операции над машинами Тьюринга, теория NP-полноты, информация про то, что программа имеет вид таблицы, определенный алгоритм или нет - это все есть в книге, с примерами. Изложение конечно академическое, с формулами, но для серьезного глубокого погружения в тему идеально подходит.
Reviews, 1 review1