Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

Предисловие
нении алгоритма 9t зависит от исходных данных задачи х = (х\,..., xk) и называется вычислением С« (х\,..., xk). Если сложность алгоритма, грубо говоря, характеризуется длиной его программы, то сложность вычисления характеризуется числом операций («временем»), количеством используемой «памяти» и другими величинами. Известны проблемы, разрешимые в принципе сравнительно простыми алгоритмами, основанными на переборе сверхастрономического числа вариантов (например, оптимальные алгоритмы в шахматах), но с очень «сложными» вычислениями, и, наоборот, встречаются довольно сложные алгоритмы, сравнительно быстро приводящие к цели — вычислению «функции» фа (хь ... ,х&)> значение которой является решением задачи с параметрами х\, ..., xk. Всякое ограничение перебора связано с усложнением алгоритма. Особенность алгоритмов, реализуемых формулами, контактными схемами и логическими сетями без обратных связей, состоит в том, что число необходимых операций находится в прямой (а часто и в прямо пропорциональной) зависимости от «сложности» схемы, т. е. алгоритма. Однако такими схемами охватывается лишь очень узкий класс алгоритмов.
На оценках сложности алгоритмов основан алгоритмический подход к определению случайности и количества информации, развиваемый в последние годы в работах А. Н. Колмогорова1), П. Мартин-Лёфа2), Л. И. Левина и др.
Вопросы сложности алгоритмов, вычисляющих булевы функции, рассматривались в работах В. А. Кузьмина3) и А. А. Маркова4). Оценкам сложности «начальных отрезков» неразрешимых алгоритмических проблем разрешения посвящены работы Я. М. Барздиня5), М. И. Кановича и Н. В. Петри6).
1) Колмогоров А. Н., Три подхода к определению понятия «количество информации», Проблемы передачи информации, 1, вып. 1 (1965), стр. 3—11.
2) М а р т и н - Л ё ф П., О понятии случайной последовательности, Теория вероятностей и ее применения, 11, вып. 1 (1966), 198—200.
3) К у з ь м и н В. А., Реализация функции алгебры логики автоматами, нормальными алгоритмами и машинами Тьюринга, сб. Проблемы кибернетики, вып. 13, 1965, стр. 75—96.
4) Марков А А., О нормальных алгорифмах, связанных с вычислением булевых функций, Изв. АН СССР, серия матем., 31, вып. 1 (1967).
5) Барздинь Я. М., Сложность программ, ДАН СССР, 182, № 6 (1968), 1249—1252.
6) К а н о в и ч М. И., О сложности разрешающих алгорифмов, ДАН СССР, 186, № 5 (1969), 1008—1009; Канович М. И., Петри Н. В., Некоторые теоремы о сложности нормальных алгорифмов и вычислений, ДАН СССР, 184, № 6 (1969); Петри Н. В., Об алгорифмах, связанных с предикатами и булевыми функциями, ДАН СССР, 185, № 1 (1969); Петри Н. В, Сложность алгорифмов и время их работы, ДАН СССР, 186, № 1 (1969), 30—31,

 

1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика