Cтраница 2
Он не может обеспечить 100-процентную загрузку центрального процессора бесконечно долго, так как в среднем в каждую секунду у алгоритма есть работы только на 975 мс. Продолжите нарисованный график за пределы 150 мс и определите, когда центральный процессор, наконец, в первый раз перейдет в состояние простоя. [16]
В главе 1 я довольно много места уделил обсуждению точки зрения сильного искусственного интеллекта, согласно которой мыслительные явления находят свое воплощение в рамках математического понятия алгоритма. В главе 2 я особо подчеркнул, что алгоритм есть действительно очень глубокое и Богом данное понятие. В этой главе я старался доказать, что такие Богом данные математические идеи существуют в определенном смысле вне времени и независимо от нас смертных. Не могут ли эти соображения служить своего рода подтверждением справедливости концепции сильного искусственного интеллекта, допуская возможность некоего высшего существования мыслительной деятельности. Это вполне возможно - и я даже собираюсь далее привести ряд соображений в поддержку в чем-то похожей точки зрения. Но если у мыслительных явлений и вправду имеется такое вместилище, я все же не думаю, что это может относиться и к понятию алгоритма. Тут нужно что-то более тонкое. Последующее обсуждение будет в значительной степени опираться на тот факт, что связанные с понятием алгоритма объекты составляют очень узкую и ограниченную часть математики. [17]
ХФМ), то оракул предъявляет некоторый цикл С s X. Будем считать, что каждый матроид Mi задан своим оракулом О, а действие алгоритма есть обращение к одному из оракулов Ot. [18]
Решение задач ( 32) дает новые базисные матрицы Btl для каждого неоптимального блока. Далее с их помощью строится новая сокращенная задача, и начинается новый цикл. Поскольку алгоритм есть частная реализация релаксационной процедуры, сходимость за конечное число итераций следует из теоремы 4.3 - 2 при исходных условиях. [19]
Для обоих классов реального времени выполняется первое условие. Все, что дает пометка процесса, как процесса реального времени, - это гарантия, что этот процесс получит более высокое значение goodness, чем все процессы разделения времени. У алгоритма есть еще одно дополнительное свойство: если у процесса, который запускался последним, осталось неиспользованное процессорное время, он получает бонус, позволяющий выиграть в спорных ситуациях. Идея состоит в том, что при прочих равных условиях более эффективным представляется запустить Предыдущий процесс, так как его страницы и кэш с большой вероятностью еще находятся на своих местах. [20]
Для обоих классов реального времени выполняется первое условие. Все, что дает пометка процесса, как процесса реального времени, - это гарантия, что этот процесс получит более высокое значение goodness, чем все процессы разделения времени. У алгоритма есть еще одно дополнительное свойство: если у процесса, который запускался последним, осталось неиспользованное процессорное время, он получает бонус, позволяющий выиграть в спорных ситуациях. Идея состоит в том, что при прочих равных условиях более эффективным представляется запустить предыдущий процесс, так как его страницы и кэш с большой вероятностью еще находятся на своих местах. [21]
Начиная с первой пары элементов, проверяем, возможно ли при перестановке элементов подобрать коэффициенты а, и а т так, чтобы получившееся сочетание было тупиковым. Получившаяся процедура может оказаться не тупиковой; последовательным ее улучшением по ( 3 - 50) и ( 3 - 52) приводим ее к тупиковой. Основная черта данного алгоритма есть перебор тупиковых процедур в порядке убывания их средних стоимостей, и его трудоемкость может быть охарактеризована общим числом тупиковых процедур. Тупиковыми процедурами будут лишь те из 2п, в которых соотношение ( 3 - 51) удовлетворяется для каждого элемента, и поэтому 2п можно считать оценкой сверху для числа тупиковых процедур. Практически число тупиковых процедур бывает значительно меньше. [22]
Такие числа называют псевдослучайными и вычисляют на ЭВМ. Это обычно удобнее, чем использование специальных генераторов. Но для каждого алгоритма есть свое предельное число членов последовательности, которое можно использовать в расчетах; при большем числе членов теряется случайный характер чисел, например - обнаруживается периодичность. [23]
Процесс вычисления зависит от исходного объекта, к к-рому применяется алгоритм. Поэтому сложность вычислений данного алгоритма есть функция, сопоставляющая каждому объекту из области применимости данного алгоритма число, характеризующее сложность процесса применения этого алгоритма к данному объекту. [24]
Заранее неясно, увеличиваются ли вычислительные возможности при переходе от преобразований конечных множеств к унитарным преобразованиям конечномерных пространств. Сейчас есть основания полагать, что такое увеличение действительно происходит. В качестве примера можно привести задачу о разложении числа на множители: для обычных компьютеров неизвестны полиномиальные алгоритмы ее решения, а для квантовых компьютеров такие алгоритмы есть. [25]
Можно ли строго математически доказать истинность алгоритма. Дело в том, что задание на построение алгоритма решения действительно важной для практики задачи определяется не формально. Дедуктивное доказательство истинности какого-нибудь предложения может быть проведено только в рамках самой математики. Если понятие алгоритма есть объект математический, то условие задачи содержит нематематические объекты. [26]
С этой точки зрения укрупненная схема алгоритма есть план алгоритма, изображенный в виде схемы. Именно так ее надо понимать и в соответствии с этим составлять. [27]
На следующем уровне иерархии крайне важная идея о том, что сами компьютеры можно заставить переводить программы с высших на низшие уровни, развивается еще далее. В начале 1950 - х годов, когда программа ассемблера уже использовалась в течение нескольких лет, было подмечено, что существуют несколько характерных структур, появляющихся в программе за программой. По-видимому, так же как и в шахматах, это были некие характерные структуры, естественно возникающие тогда, когда люди пытаются найти алгоритмы - точные описания процессов, которые они хотят осуществить. Иными словами, кажется, что в алгоритмах есть некие компоненты высшего уровня, при помощи которых они могу г быть описаны с большей легкостью и эстетизмом, нежели на весьма ограниченном машинном языке или языке ассемблера Обычно такой компонент высшею уровня в алгоритме представляет собой не одну-две машинных команды, но целый конгломерат; при этом эти команды не обязательно соседствуют в памяти Подобный компонент может быть представлен на языке высшего уровня как некое единство, или блок. [28]
Нам потребуется понятие подъязыка. Поскольку, вообще говоря, язык не является конечным множеством слов, вводя понятие подъязыка, мы должны соблюдать определенную осторожность. Предположим, что L s - некоторый другой формальный язык. W ( х, s), применимый к некоторым парам х, s, то множество тех х, каждое из которых входит хотя бы в одну такую пару, называется подъязыком языка L. В частности, область применимости любого алгоритма есть подъязык. [29]
Нам потребуется понятие подъязыка. Поскольку, вообще говоря, язык не является конечным множеством слов, вводя понятие подъязыка, мы должны соблюдать определенную осторожность. Предположим, что L sj - некоторый другой формальный язык. Если существует) алгоритм W ( х, s), применимый к некоторым парам х, s, то множество тех х, каждое из которых входит хотя бы в одну такую пару, называется подъязыком языка L. В частности, область применимости любого алгоритма есть подъязык. [30]