Автор: Морозов А.С.
Название: Введение в вычислимость. Учебное пособие
Издательство: Новосибирск: НГУ
Год: 2005
Страниц: 114, нет стр. 108
Формат: djvu
Размер: 15,5 Мб
Язык: Русский

Одним из основных понятий теории алгоритмов, инвариантным к вычисляемой функции и алгоритму, является вычислимость. Цель настоящего курса — дать основные идеи, связанные с понятиями алгоритма и вычислимости. Цели и задачи, решаемые в теории алгоритмов: анализ сложности алгоритмов; исследование и анализ рекурсивных алгоритмов; формализация понятия «алгоритм» и исследование формальных алгоритмических систем; формальное доказательство алгоритмической неразрешимости ряда задач; классификация задач, определение и исследование сложностных классов; получение явных функций трудоемкости в целях сравнительного анализа алгоритмов; разработка критериев сравнительной оценки качества алгоритмов. Учебное пособие адресовано студентам, обучающимся по направлениям "Компьютерные и информационные науки", "Информатика и вычислительная техника", но будет полезно и студентам группы направлений "Математика и механика", а также всем желающим начать самостоятельное изучение математической логики.