О книге
Рассмотрены машины Тьюринга, вопросы алгоритмической разрешимости, основные классы сложности, NP-полнота, схемная сложность.
Для студентов МГТУ им. Н. Э. Баумана, обучающихся по специальностям "Информационная безопасность автоматизированных систем" и "Компьютерная безопасность". Пособие может быть полезно студентам других специальностей, связанных с информатикой, вычислительной техникой и информационной безопасностью.
Список литературы
- Булос Д., Джеффри Р. Вычислимость и логика: Пер. с англ. М.: Мир, 1994. 396 с.
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: Изд-во МЦНМО, 2003. 325 с.
- Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов: В 3 ч. Ч. 3. Вычислимые функции. М.: Изд-во МЦНМО, 2002. 299 с.
- Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов: В 3 ч. Ч. 2. Языки и исчисления. М.: Изд-во МЦНМО, 2002. 288 с.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М.: Мир, 1982. 416 с.
- Емеличев В.А. и др. Лекции по теории графов. М.: URSS, 2009. 382 с.
- Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: Изд-во МЦНМО, 1999. 192 с.
- Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001. 260 с.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ: Пер. с англ. М.: Вильямс, 2005. 1290 с.
- Лупанов О.Б. Асимптотические оценки сложности управляющих систем: Учеб. пособие. М.: Изд-во Моск. гос. ун-та, 1984. 137 с.
- Феллер В. Введение в теорию вероятностей и ее приложения: В 2 т. М.: Либроком, 2010. Т. 1. 511 с.; Т. 2. 766 с.
- Хопкрофт Д.Э., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений: Пер. с англ. М.: Вильямс, 2008. 527 с.
- Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии. М.: Изд-во МЦНМО, 2002. 103 с.
- Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. 399 с.
- Яблонский С.В. Введение в дискретную математику. М.: Высш. шк., 2010. 384 с.
- Arora S., Barak B. Computational complexity: a Modern Approach. Cambridge; New York: Cambridge University Press, 2009. 579 p.
