ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.02.2021
Просмотров: 186
Скачиваний: 1
Введение
в
теорию
алгоритмов
.
Развитие
математики
во
второй
половине
XIX
в
.
стимулировалось
в
основном
математикой
нечисловых
объектов
-
открытием
неэвклидовых
геометрий
,
появлением
абстрактных
алгебраических
теорий
типа
теории
групп
и
т
.
д
.
Одним
из
решающих
обстоятельств
,
приведших
к
пересмотру
оснований
математики
,
т
.
е
.
принципов
,
лежащих
в
основе
математических
рассуждений
,
явилось
создание
Кантором
теории
множеств
.
Довольно
быстро
стало
ясно
,
что
понятия
теории
множеств
в
силу
своей
общности
лежат
в
основе
всего
здания
математики
.
Однако
почти
столь
же
быстро
было
показано
,
что
некоторые
кажущиеся
вполне
естественными
рассуждения
в
рамках
этой
теории
приводят
к
неразрешимым
противоречиям
—
парадоксам
теории
множеств
.
Все
это
потребовало
точного
изучения
принципов
математических
рассуждений
(
до
сих
пор
казавшихся
интуитивно
ясными
)
математическими
же
средствами
.
Возникла
особая
отрасль
математики
-
основания
математики
,
или
метаматематики
.
Опыт
парадоксов
теории
множеств
научил
математику
крайне
осторожно
обращаться
с
бесконечностью
и
по
возможности
даже
о
бесконечности
рассуждать
с
помощью
финитных
методов
.
Существо
финитного
подхода
заключается
в
том
,
что
он
допускает
только
конечные
комплексы
действий
над
конечным
числом
объектов
.
Выяснение
того
,
какие
объекты
и
действия
над
ними
следует
считать
точно
определенными
,
какими
свойствами
и
возможностями
обладают
комбинации
элементарных
действий
,
что
можно
и
чего
нельзя
сделать
с
их
помощью
, -
все
это
стало
предметом
теории
алгоритмов
и
формальных
систем
,
которая
первоначально
возникла
в
рамках
метаматематики
и
стала
важнейшей
ее
частью
.
Главным
внутриматематическим
приложением
теории
алгоритмов
явились
доказательства
невозможности
алгоритмического
(
т
.
е
.
точного
и
однозначного
)
решения
некоторых
математических
проблем
.
Такие
доказательства
(
да
и
точные
формулировки
доказываемых
утверждений
)
неосуществимы
без
точного
понятия
алгоритма
.
Пока
техника
использовала
чисто
вычислительные
методы
,
эти
высокие
проблемы
чистой
математики
ее
мало
интересовали
.
В
технику
термин
«
алгоритм
»
пришел
вместе
с
вычислительной
техникой
.
Понадобилось
осознавать
,
каким
требованиям
должна
удовлетворять
последовательность
действий
(
или
ее
описание
),
чтобы
считаться
конструктивно
заданной
,
т
.
е
.
иметь
право
называться
алгоритмом
.
В
этом
осознании
огромную
помощь
инженерной
интуиции
оказала
практика
использования
вычислительных
машин
,
сделавшая
понятие
алгоритма
ощутимой
реальностью
.
С
точки
зрения
современной
практики
алгоритм
-
это
программа
,
а
критерием
алгоритмичности
процесса
является
возможность
его
запрограммировать
.
Именно
благодаря
этой
реальности
-
алгоритма
,
а
также
потому
,
что
подход
инженера
к
математическим
методам
всегда
был
конструктивным
,
понятие
алгоритма
в
технике
за
короткий
срок
стало
необычайно
популярным
(
быть
может
,
даже
больше
,
чем
в
самой
математике
).
Однако
у
всякой
популярности
есть
свои
издержки
.
В
повседневной
практике
слово
«
алгоритм
»
употребляется
слишком
широко
,
теряя
зачастую
свой
точный
смысл
.
Приблизительные
описания
понятия
«
алгоритм
» (
вроде
того
,
которое
приведено
в
первой
фразе
этого
параграфа
)
часто
принимаются
за
точные
определения
.
В
результате
за
алгоритм
зачастую
выдается
любая
инструкция
,
разбитая
на
шаги
.
Ясное
представление
о
том
,
что
такое
алгоритм
,
важно
,
конечно
,
не
только
для
правильного
словоупотребления
.
Оно
нужно
и
при
разработке
конкретных
алгоритмов
,
особенно
когда
имеется
в
виду
их
последующее
программирование
.
Чтобы
ориентироваться
в
огромном
разнообразии
алгоритмов
,
необходимо
уметь
сравнивать
различные
алгоритмы
решения
одних
и
тех
же
задач
,
причем
не
только
по
качеству
решения
,
но
и
по
характеристикам
самих
алгоритмов
(
числу
действий
,
расходу
памяти
и
т
.
д
.).
Такое
сравнение
невозможно
без
введения
точного
языка
для
обсуждения
всех
этих
вопросов
;
иначе
говоря
,
сами
алгоритмы
должны
стать
такими
же
предметами
точного
исследования
,
как
и
те
объекты
,
для
работы
с
которыми
они
предназначены
.