lekcii6 (Лекции), страница 5

Обработка сообщений., описанная в примере (1.9.1). называется эффективной процедурой или алгоритмом. Более точно, алгоритм — это точно заданная последовательность правил. указывающая, каким образом можно за конечное чнс.ю шагов получать выходное сообщение опредеие>шаго вида, используя заданное исходное сообщение. Пример (1.9.1) пшволяет обнаружить некшорые снойсгва алгоритл>ов., а ил>сино: (1) массовость., ъ е. потенциальная бесконечность исходных сообщеняй„предназначенных >ьш переработки а.>горн>мол>; (2) детерминированность процесса применения алгоритма, зак.пача>ащегося в последовательном выполнении дискро>ных дейсгвий (шагов), однозначно определяемых резулыаталш каждого предыдущего шага, Класс < Описание сложности О(1) О(!об п) 0(п) О(пз) 0(пз) а х" б а„.<х" -1-...

+ а<х -1- ае 0(2") (... ((О„х + а„<)х -1- а„з)...)х + Оа, (3) элементарность каждого шага обработки. который;юлжен быль дсстато пю лег- КО ВЫПОЛНИМ: (4) 1жзультативность алгоритма, т. е. шчное описаняе того. что считается разулыатом прил<енения алгоритма после выполнения агах требуемых шагов. Нрезвычайпо важныл< с точки зрения практической эффективности а:поритмов является еще одно свойство: (5) сложность алгоритма опреде.жется количеством простых операций. которые нужно соверппг<ъ,яро< обработки сообщения.

Это ко:<ичсство прямо зависит сг длины входного сообщения п и обычно задается некоторой функцией !(п). Таким образом, сложность ограничивает применимость алгоритма. Ллгоритм, выпогшяющийся за постоянное время, можно применять к любол<у входному сообщен>по. Есяи время выло.щения пропорционально п или п, то такой аи.оритм неприменим к длинным исходным сообщениям, поскольку время выполнения становится нсприсл<лемо ба>вшил<. Иногда очевидный алгоритм можно существенно улучшить за счет другого подхода к проблеме. Пусть нообходилю вычислить значение лшогочлсна п(п -!- 1) Прямое вычисление потребует п и и — 1 б и — 2-~- -!-1 = операций умно- 2 л(п -1- 3) жени» и п операций сложения, всего, т.

е. его сложность .. 0(пх). Л осли 2 переписать зада <у в виде то можно об<анись п улпюжениими и и сложениями всего пппь 2п операциял<и, т. е. порядок сложности этого алгоритма, называемого схемой!'оряера, 0(п). Сложность <ьпорятма определяет< как долго придется ждать, пока будет получен резумьгаг его работы. Одноврел<снно сложность определяет разл<ер зады<и, которая может быть решена давным алгоритмом за лриемлсл<ое врел<я. Если иногда можно подождать л<еи<ц иля даже три, зо ждать < од или 10 лег почти всегда бессмысленно.

Поэтому всегда актуальна задача о поиске наиболее эффективных (т. е. быстро работающих) алгоритмов. Кроме обы шой врсменнбй с.южное<и алгоритл<ов часто рассматрива<от и пространственную сложность обьсм памяти, необходимый алгоритму для переработки входного сообще<шя д:шны п. ,Л.<я обозначении класса сложности используется О-нотация (93. 76]. У всякого алгоритма., как у функции, .есть шавная часп . которая занимав< болыпе всею времеви;<ля выполнения. Анализируя количество выполнений главной части дечают вывод о поведении а.згорнтма в зависимости <и длины исходного сообщения (63) Тогда появлжгся возлюжность сказать, какие задачи могут быть реп<сны за присмлслюе время, а какие не будут реп<сны практически никогда.

Все алгоритмы >южно разбить па классы по нх сложности (88): Ллгоритмы с пос<оянпым временем выполнения. нвпрямер доступ к элементу ыассива. При увеличении разл<ера задачи вдвое время выпазпения не меняется. Ллгорнтмы с логарифмическим временем выполнения, например би- нарный поиск.

Время выло>ясна» удваивается при увеличении раз- мера задачи в и раз. Ллгоритмы с линейным арса<енсы выполнения, например последова- тельный поиск илн схелш Горнера. При увеличении размера задачи вдвое время выполнения также удваивается. О(п!обп! Ллгор<пмы с .<инеарифмическил< временем выполиеняя, например быстрая сортировка.

Время выполнения увеличивается немного больше< чем вдное< при увеличешш размера задачи в два раза. Ллгоритыы с квадратичным временем выполнения, наприл<ер про- стые азгорвтмы сортировки. Время выполнения увеличивается в 4 раза при увеличении размера задачи а 2 раза. Ллгоритмы с кубическим временеы выполнены<, наприл<ер умножо- пие матриц.

Врелш выполнения увеличивается в 8 раза при увеличе- нии размера задачи в 2 раза. Ллгорнтл<ы с экспопснциальным врел<епем выло:щения, наприла:р за- дача о составлении расписания. Бремя выполнения увсличиваетси в 2" раз при увеличении размера задачи в 2 раза. И сегодня задача построения эффективных алгорвтмов остается весьма актуа.п,ной. Заведующий кафедрой матемшяческой кибернетики факультета ВМиК МГУ профессор Ллсксеев В. В.

пишет: лДля того. чтобы передать задачу компьютеру, казалось бы достаточно разработать какой-нибудь алгорятм решения. Но оказывас<ы<, по и при сов>именных сверхскоросл ных компьютерах некоторые алгоритмы не <ю>тходят, <юскольку требуя>г се<паком много времени Напрямер, если алгоритм п>ебущ пер.:брать все бглевы функции от п переменных, ш комвыотер пе сможет эта сделать даже за миллион лет уже три п = 7. Выходов даа либо ускорять колшысгеры, либо придумывать новые нес<авдартные алгоритмы. Оказывается. что веставдартные елгоритмы существуя>г д<ы многих задач. Например, умножение в столбик двух и-ра>рядаых чисел требует О(пз) битовых операций. Только в 1962 63 гг.

были обнаружены более быс>рые а:пор<ггмы со сложностыс О(г<~~) для л<сбого г > 9 Спи основаны на разложении чисел на мвожители (т. и. китайская теорема об остатках (64)) Оказии>ется. что и умножение матриц строка па столбец . это не самый быстрый способ (он требует О(пл) арнфметическях операций для матриц порядка л). Уже более 15 лет известна Оценка О(пз ~). но да.<ьпейшее ее увушпение еще впереди.

К сожалению, для большинства за,'<ач на практике не существует пока алгоритмов с палипомиальной верхней оценкой сложности. а экспоненцию<ьнав сложносп . очень быс<ро рас<ущая величина С другой стор>лы, для эп<х автор<имое нет и нижней оценки сложности ванне. чем л<шейная. Так по с ситуацией здесь еще предстоит разбигнтъся. Похоже. что для рк<работки быстрых алгори>мов назо применять хорошо развитые раикшы математики,. такие, например, как а.небраэ Важность сложноогных характеристик алгоритмов особенно неявка ззя таких ответственных применений. как крин>аграфия.

Защитой с г расшифровки люжет бып высокая сложность алгоритма декодирования. Своеобразной шн<)>ровке — обфускации — подвер<аются и программы. исходный коз коп>рых маскируется от реинжениринга. В наследном случае с<ойкость скрываемого кода определяется сложностью а.поритма распознавания исходного токсга программы. За.мечамие. Предлагая новый я>ш модифицированный алгоритм, необходимо всегда давать сго сзожпосгную оценку, без ко<арой нсвозл<ожно судить о полезности этого алгоритма.

Во всяком случае, алгоритм бел такой оценки не считается научно обоснованным. Кролле тогш во мноп<х случаях, заказчик на.<агает весьма жесткие ограничения на пространственную и временную сложпосп алгоритма и программы реп<сник задачи. Например. на олимпиадах по про<раммированию предельное время выполнония последовательности тестов жюри программой всегда задается таким, чтобы лобовой азгор<ггм заледомо не уложился бы.

Например, степень полинома и вь<бирается наатолько болыпой. чтобы без схемы Горнсра с ее линейной сложностью было невгаможно за малое время его табулировать(вычислить значения такого многочлена во многих точках). В нашем курсе понятие алгоритма и аго свойс<на будут изучены даст<ос <но подробао н достаточно с<рого.

'Зто обусловлено тем, что алгоритмы образуют сердцевину информатики, яв.ппотся тем общим знаменателем, который образует се основу и объединяет различные направления. Здесь уместно повтор<ггь лшсние Д. Кнута: «Лучп<ий, с моей точки зрения, .способ определить информатику — это сказать, что она занимается изучением езгорнтлюв» (34). Но прежде чем занятье»< детальным изучением алгоритмов и их свойс<в, нам необходимо рассмотреть вопросы, связанные с интерпретацией сообщений, н, в частности, выяснить, как рсавизукпся отображения 0 и э>', связывающие сообщения с содержащейся в них информацией.