Математическая машина Тьюринга и вычислительная сложность. Учебное пособие
Мирзоев Махмашариф Сайфович, Сатторов Абдурасул Эшбекович, Джонмахмадов Исломиддин Тешаевич
Код товара: 4844218
(0 оценок)Оценить
ОтзывНаписать отзыв
ВопросЗадать вопрос
1 / 2
1 / 2
Издательство:
Год издания:
2020
Описание
Характеристики
В учебном пособии изложены подходы к формализации понятий алгоритма. В нем уточняется понятие алгоритма через математическую машину Тьюринга и машину с неограниченным количеством регистров (МНР) и рассматриваются некоторые оценки сложности алгоритмов. Помимо теоретических и практических материалов пособие содержит задания для самостоятельной работы. Содержание учебного пособия соответствует Федеральному государственному образовательному стандарту высшего образования третьего поколения и методическим требованиям, предъявляемым к учебным изданиям. Пособие адресовано учителям информатики, преподающим информатику в профильных классах, а также предназначено для студентов высших учебных заведений, обучающихся по направлению педагогического образования профилей "Информатика и математика", "Физика и информатика", "Технология и информатика", "Математика и информатика", "Прикладная информатика". Пособие может быть полезно широкому кругу читателей, интересующимся основами теории вычислимости.
Содержание
Введение
ГЛАВА 1. УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА С
ПОМОЩЬЮ МАШИНЫ ТЬЮРИНГА
1.1. Математическое понятие машины Тьюринга.
Алфавит машины Тьюринга. Основные операции
над машиной Тьюринга
1.2. Понятие конфигураций машины Тьюринга (МТ)
1.3. Операции над машинами Тьюринга
1.4. Базис элементарных машин Тьюринга
Универсальная машина Тьюринга
1.5. Правильная вычислимость функции по
Тьюрингу. Эквивалентность двух уточнений
алгоритма
1.6. Уточнение понятия алгоритма через машину с
неограниченными регистрами
Контрольные вопросы
Практические задания
ГЛАВА 2. АНАЛИЗ И СЛОЖНОСТИ АЛГОРТМОВ
2.1. Введение в теорию сложности вычислений
Меры сложности
2.2. Классы сложности
2.3. Введение в теорию NP-полноты
2.4. Полиномиальная сводимость и полнота
Контрольные вопросы
Литература
Приложения
ГЛАВА 1. УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА С
ПОМОЩЬЮ МАШИНЫ ТЬЮРИНГА
1.1. Математическое понятие машины Тьюринга.
Алфавит машины Тьюринга. Основные операции
над машиной Тьюринга
1.2. Понятие конфигураций машины Тьюринга (МТ)
1.3. Операции над машинами Тьюринга
1.4. Базис элементарных машин Тьюринга
Универсальная машина Тьюринга
1.5. Правильная вычислимость функции по
Тьюрингу. Эквивалентность двух уточнений
алгоритма
1.6. Уточнение понятия алгоритма через машину с
неограниченными регистрами
Контрольные вопросы
Практические задания
ГЛАВА 2. АНАЛИЗ И СЛОЖНОСТИ АЛГОРТМОВ
2.1. Введение в теорию сложности вычислений
Меры сложности
2.2. Классы сложности
2.3. Введение в теорию NP-полноты
2.4. Полиномиальная сводимость и полнота
Контрольные вопросы
Литература
Приложения
Отзывы
Вопросы
Поделитесь своим мнением об этом товаре с другими покупателями — будьте первыми!
Дарим бонусы за отзывы!
За какие отзывы можно получить бонусы?
- За уникальные, информативные отзывы, прошедшие модерацию
Как получить больше бонусов за отзыв?
- Публикуйте фото или видео к отзыву
- Пишите отзывы на товары с меткой "Бонусы за отзыв"
Задайте вопрос, чтобы узнать больше о товаре
Если вы обнаружили ошибку в описании товара «Математическая машина Тьюринга и вычислительная сложность. Учебное пособие» (авторы: Мирзоев Махмашариф Сайфович, Сатторов Абдурасул Эшбекович, Джонмахмадов Исломиддин Тешаевич), то выделите её мышкой и нажмите Ctrl+Enter. Спасибо, что помогаете нам стать лучше!