ВУЗ:
Составители:
Предисловие
Использование компьютеров связано с возможностью алгоритмического решения
задач и эффективного вычисления функций. Между тем в математике широко
используются функции, заданные неэффективными определениями. Это приводит к тому,
что некоторые функции поддаются вычислению с помощью алгоритма, скажем на
компьютере, как только для этого будет составлена надлежащая программа, тогда как
другие функции, заданные неэффективным
определением, могут требовать творческого
подхода для вычисления своих значений. Столь же часты доказательства разрешимости
задач, не сопровождаемые алгоритмами их решения.
Формализация понятия вычислимости позволяет увидеть связь алгоритмов с
процессом логического вывода, установить пределы доказуемости в формальных
системах, получить результаты о неполноте математики.
В действительности класс задач, доступных классическим средствам, в
некотором
трудно уточняемом смысле строго шире класса задач, решаемых алгоритмически. В
пособии проясняется смысл этого утверждения, и излагаются некоторые математические
модели вычислимости. За последние десятилетия стало ясно, что различие между быстро
и долго решаемыми задачами не менее философски и практически важно, чем различие
между алгоритмически разрешимыми и неразрешимыми, и теория сложности
вычислений
стала одной из центральных в логике (и вообще в математике). Поэтому также в пособии
рассматриваются основные понятия теории сложности алгоритмов.
Особое внимание автор обращает на две темы: ламбда–исчисление и теорема
Гёделя о неполноте.
Как изучать теорию алгоритмов? С чего начинать? Нам привлекательна следующая
стратегия, описанная в истории, взятой
из книги [19].
Кувшин
Знаменитый китайский профессор из известного китайского университета сидел
перед новой группой студентов. Прямо перед ним стоял большой стеклянный кувшин,
полупрозрачный, легкого зеленоватого оттенка.
Профессор смотрел на студентов, не произнося ни слова. Затем он наклонился
вправо. У его правой ноги лежала кучка камней, каждый из которых мог бы поместиться
в
кулак. Он взял один из камешков и очень осторожно опустил его в кувшин через узкое
горлышко. Потом взял следующий и повторил эту процедуру. Он проделывал это до тех
пор, пока камни не поднялись до самого горлышка и не заполнили весь кувшин.
Он повернулся к группе и сказал:
– Скажите
мне, этот кувшин полон?
Группа согласно зашелестела. Кувшин, без сомнения, был наполнен.
Профессор ничего не сказал и обернулся в левую сторону. Около его левой ноги
была насыпана горка мелкой гальки. Он набрал полную горсть и стал аккуратно засыпать
гальку через горлышко кувшина. Горсть за горстью, он сыпал гальку в кувшин, а
она
просыпалась сквозь щели между камнями, пока не дошла до самого верха, и уже
невозможно было насыпать даже маленькую толику.
Он повернулся к аудитории и спросил:
– Скажите мне, полон ли кувшин сейчас?
Группа пробормотала, что все выглядит так, как если бы на этот раз кувшин
действительно был полон; возможно, полон
; наверное.
Профессор ничего не сказал и снова повернулся к правой стороне. Около его ноги
была насыпана горка крупного сухого песка. Он набрал горсть песка и начал аккуратно
сыпать его через горлышко кувшина. Песок просыпался сквозь камни и гальку, а
профессор горсть за горстью сыпал его в кувшин, пока песок не
достиг горлышка и стало
ясно, что больше насыпать невозможно.
Страницы
- « первая
- ‹ предыдущая
- …
- 3
- 4
- 5
- 6
- 7
- …
- следующая ›
- последняя »
