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

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