lekcii5 (Лекции), страница 9

0(?оь'и) Алгоритмы с логарифмическим временем выполнения, например би- нарный поиск. Время выполнения удваивается при увеличении раз- мера задачи в и раз. О(»,) Алгоритмы с линейным временем вьшолнения, например гюследова- тельный поиск или схема Горнера, При увеличении размера зада ш вдвое время выполнения также удваивается. О(»,!оя'и) Алгоритмы с липеарифмическим временем выполнения, например, быстрая сортировка. Время выполнения увеличивается немного больше, чем вдвое, при увеличении размера задачи в два раза. 0(п2) Алгоритмы с квадратичным временем выполнения, например про- стые алгоритмы сортировки. Время выполнения увеличивается в 4 раза, при увеличении размера задачи в 2 раза,.

0?»а) Алгоритмы с кубическим временем выполнения> например умноже- ние матриц. ?Зремя вьшолнения увеличивается в 8 раза при увеличе- нии размера задачи в 2 раза. 0(2") Алгоритмы с экспоненциальным временем выполнения, например за- дача о составлении расписания. Время выполнения увеличивается в 2" раз при увеличении размера задачи в 2 раза. «Для того, чтобы передать зада >у компьютеру. казалось бы достаточно разработать какой-нибудь алгоритм решения. Но оказывается, >то н нрн современных сверхскоростных коъшьютерах некоторые алгоритмы не подходят, поскольку требуют слишком много времени.

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

были обнаружены более быстрые алгоритмы со сложностью 0(п>+«) для любого е ) О. Онн основаны на разложении чисел на множители (т. н. китайская теорема об остатках !64]). Оказывается, что н умножение ма> риц спцюка на сп>олбец -- это не самый быстрый способ (он требует 0(пз) арифметических операций для матриц порядка и). Уже более 15 лет известна оценка 0(пв а"), но дальнейшее ее улучшение еще впереди. К сожалению, для болыпннства задач на практике не существует пока алгоритмов с нолнномнальной верхней оценкой сложности, а, эксноненцнальная сложность .— очень быстро растущая вели г>«на.

С >Ч>угой стороны, для этих алгоритмов нет н нижней оценки сложности выше, чем линейная. Так что с ситуацией здесь еще предстоит разбираться. Похоже, что для разработки быстрых алгоритмов надо применять хорошо развнтыа раздолы математики, такие, например, как алгебра,« 35 И сегодня задача построения эффективных алгоритмов остается весьма актуальной. Заведующий кафедрой математи и'ской кибернетики факультета ВМиК М?'У профессор Алексеев В. Ь, пишет: Важность сложностных характеристик алгоритмов особенно велика лля таких ответственных применений, как криптография.

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

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

Решив эти вощюсы, мы сможем задавать правильные исходные данные для алгоритмов и правилыю интерпретировать сообщения, полученные в результате их применения. Лекция 5 1.10 Интерпретация дискретных сообщений Сообгцения интерпретируются л>одьми в соответствии с их представлениями о внешнем клире, о среде (естественной или искусственной), информацию о которой содержат эти сообщения. Именно этим обстоятельством объясняется то, что одно и то же сообщение интерпретируется разными людьми по-разному.

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

На этом бе<еда завер)пилась и собеседники разошлись, очень довольные собой и друг другом. Один из лк)бопытных свидетелей беседы обратился к философу за разъяснением ес содержания. «Мой собеседник оказался очень мудрым человеком», сказал философ. «Сначала я сказал ему, что плохо жить одному, как перст. На что он ответил, что, конечно, вдвоем жить лучше. Тогда я сказал ему, что еще лучше, когда в семье трос, имея в виду ребенка. Он согласился и заметил, что ребенок сплотит семью. И жизнь пойдет полной чашей, отметил я напоследок, а он, показав луковипу, как бы ска; зал,что тогда даже мелкис неприятности не оудут омрачать радости жизни».

Свидетель усомнился в интерпретации Ф и НОгп11л за, разъяснениями к Одно!лаз!2му. «Он, ничего, пар!'нь смелый, но куда, ему против меня», сказал О. «Сна гала он говорит мн!.: Зй ты, одноглазый и рт», на 1то я отвечал; «Л ты со своими двумя не О21еньто задавайся». 22 он никак не уймется: «А ведь на двоих-то у нас всего три глаза . Тут я показал ему кулак. Он испугался и решил к!яриться.

«Выпьем, !ТО ли. » - —. предло!хил он, на что я ответил: «Иди за бутылкой, закуска найдется». Мораль очевидна. Чтобы не оказаться в положении собеседников из притчи, фиксируют представление о внешнем мире в виде его модели. Мы здесь опишем сущность этого понятия, не уточняя пока полностью определений. Формальное и строгое изложение данного материала отложим до специальных курсов.

Строя математическое понятие модели, мы исходим из того, что внешний мир (среда) состоит из объектов (предметов), которые обладают определенными свойствами (атрибутами) и находятся в определенных отношениях друг с другом. Объектам, их атрибутам и отношениям ставятся в соответствие знаки (имена), из которых строятся сообщения (напомним, что дискретное сообщение это последовательность знаков).

Интерпретация дискретного сообщения при наличии модели сводится к тому, что каждому знаку, входящему в состав сообщения, ставится в соответствие объект, свойство (атрибут) объекта, или отношение между обьектами, представляемое этим знаком ~23, 32~. Определение 1.10.1. Назовем А-местных! отношением на М1южестве ЛХ совокупность (множество) г!' у1юрядоченных наборов из Л элементов множества ЛХ вида (х1,хэ, ..., х») (иначе говоря, отношение г это подмножество декартова произв1дсния т'~ С ЛХ~; верхний индекс у г указывает местность (число мест) отношения.