Размещено на http://www.allbest.ru/

Федеральное государственное образовательное бюджетное учреждение

«Сибирский государственный университет телекоммуникаций и информатики»

Реферат

по истории

История разработки алгоритмов

Выполнил:

аспирант

Жеголко К.В.

Научный руководитель:

Фроловский В.Д.

г. Новосибирск 2015



Оглавление

• алгоритм евклид программирование
• Введение
• 1. Алгоритмы в математике от древних цивилизаций до современного времени
• 1.1. Древний Египет
• 1.2. Древний Вавилон
• 1.3. Древняя Греция. Пифагор. Евклид
• 1.4. «Dixit Algorizmi». Ал-Хорезми
• 1.5. Ключевые события в истории развития теории алгоритмов
• 1.6. Основные результаты теории алгоритмов
• 2. Эволюционные алгоритмы и история их появления
• 2.1.Генетические алгоримы
• 2.2 Современное состояние теории алгоритмов
• 2.2.1 Использование других наук в алгоритмах
• 2.2.2 Наиболее значимые применения алгоритмов
• Заключение
• Библиографический список


Введение

На протяжении всей жизни человеку приходится сталкиваться с алгоритмами (например, правила дорожного движения, правило нахождения корней квадратного уравнения, рецепт приготовления блюда и т. д. и т. п.). При этом часто мы не осознаем того факта, что работаем с алгоритмом, заменяя слово «алгоритм» словами «правило», «устав», «инструкция» и т. д. Дело в том, что для повседневной жизни не требуется четкого определения алгоритма, достаточно уметь применять его на жизненном уровне. Неудивительно, что в определенный момент времени человечество пришло к выводу, что такое масштабное понятие, как «алгоритм», достойно отдельной науки.

Итак, теория алгоритмов - это наука, изучающая общие свойства и закономерности алгоритмов, разнообразные формальные модели их представления. На основе формализации понятия алгоритма возможно сравнение алгоритмов по их эффективности, проверка их эквивалентности, определение областей применимости.

Разработанные в 1930-х годах разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч), равно как и предложенные в 1950-х годах модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.

Теория алгоритмов обогатила математику, пожалуй, как ни одна известная наука: ее постулаты лежат в основе доказательства, одного из главных ее понятий.

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

1. Алгоритмы в математике от древних цивилизаций до современного времени

1.1 Древний Египет

История понятия «алгоритм» уходит корнями в древние цивилизации, как сама математика. Если о математике достоверно неизвестно ещё более древних цивилизаций, чем древний Египет и древний Вавилон, то о последних всё же можно кое-что сказать. О математике древних египтян известно из папируса Райнда, который был найден и расшифрован в XIX веке. В папирусе перечислено множество задач на измерение площадей полей и подсчёт единиц. В нём также излагаются инструкции жрецов для писцов. Быть писцом в древнем Египте было почётно, т.к. писец заведовал административно- хозяйственной частью, подсчитывал и указывал, сколько куда человек нужно направить и на какие работы в каком количестве. От него зависело состояние дел.

В папирусе Райнда[1] содержатся инструкции о том, как подсчитывать. И эти инструкции есть документальное подтверждение существования алгоритма ещё в древнем Египте. Однако такой алгоритм ещё не рассматривался самой математикой, к тому же сама математика ещё не была осознана как отдельная область деятельности. Основным объектом математики древнего Египта были числа и элементарные операции над ними. По папирусу Райнда видно, что основным алгоритмом при вычислении операций деления натуральных чисел и сложения дробей был перебор. На бумаге записывались последовательно числа, элементарные операции с этими числами (т.е. умножение на два, на пять и на десять и сложение), а затем перебором подбирались правильные ответы, которые сходились в проверке. Можно сказать, что это был алгоритм проверки.

Из тех материалов, что дошли до нас о древнем Египте нельзя заключить, что тогда существовало отдельное понятие алгоритма, хотя, по сути, в математику уже тогда закладывались основные алгоритмические истины: последовательное оперирование конечными объектами, с результатом вновь в виде конечного объекта. В книге так оценена математика древнего Египта: «математика представляла собой совокупность знаний, ещё не расчленившуюся на арифметику, алгебру, геометрию и выступающую, прежде всего как собрание правил для численного решения простейших арифметических, алгебраических и геометрических задач».

1.2 Древний Вавилон

О математике древнего Вавилона мы знаем из клинописных глиняных табличек. Из них, в частности известно, что тогда решались математические задачи, в том числе не имеющие отношения к практической деятельности, хотя по большей части формулировки не были отвлечёнными: вместо привычных нам переменных тогда использовались слова «длина» (x), «ширина» (y), «глубина» (z), «площадь» (xy), «объём» (xyz).

Тогда же зародились начала алгебры, т.е. решения систем линейных и квадратичных уравнений. Причём сами задачи (из тех, что дошли до нашего времени в виде глиняных табличек) имели отвлечённый характер. «Я вычел из площади сторону моего квадрата, это 14,30» - эту формулировку можно перевести на современный математический язык так: x2--x=14,30. Далее следует вычисление: «Ты берёшь 1, коэффициент. Ты делишь пополам 1, это 0;30. Ты умножаешь 0;30 на 0;30, это 0;15. Ты складываешь [это] с 14,30 и это есть 14,30;15, что является квадратом для 29;30. Ты складываешь 0;30, которое ты умножал, с 29;30, получается 30, сторона квадрата». Здесь, по сути, идёт описание действий вычислителя, т.е. описывается конкретная инструкция вычислителю.



1.3 Древняя Греция. Пифагор. Евклид

В древней Греции математика приобретает самостоятельную ценность. Так возникает пифагорейская школа, где ученики Пифагора доказывают различные факты лишь на основании логических рассуждений. «Пифагор преобразовал эту науку [математику] в форму свободного образования. Он изучал эту науку, исходя из первых её оснований, и старался получать теоремы при помощи чисто логического мышления, вне конкретных представлений» [Прокл, V в.].

Появляется фундаментальный труд Евклида, в котором предложен знаменитый «алгоритм Евклида» нахождения наибольшего общего делителя. Конечно, словосочетание «алгоритм Евклида» появилось и установилось гораздо позже, до этого был «метод Евклида». Открытие этого алгоритма позволило доказать несколько фундаментальных теорем теории целых чисел (разложение любого числа на произведение простых делителей). Характерно для древней Греции, что алгоритм сформулирован для произвольных чисел, а не для конкретных, как в более древних цивилизациях (Вавилоне, Египте). Такая традиция общих формулировок была заложена именно в древней Греции. И именно из-за того, что алгоритм по своей сути представляет некоторый общий метод решения однотипных задач, он впоследствии приобретёт самостоятельную математическую ценность.

1.4 «Dixit Algorizmi». Ал-Хорезми

Современная история математики большую роль формированию алгебры в том виде, который мы имеем сейчас, относит к трудам ал-Хорезми, арабского учёного, перенёсшего индийскую позиционную арифметику на запад.

«Слово “алгорифм” в форме “алгоризм” часто (вслед за английским поэтом Чоусером с 1350 г.) употреблялось в качестве заглавия изложений индийского счисления в рукописях XII-XV вв. и в книгах XV-XVI вв.»[3]. Свои трактаты ал-Хорезми начинал со слов «dixit algorizmi», что означает «Говорит ал-Хорезми».

Алгоризм овладевал всё большими территориями. Арифметика, представленная ал-Хорезми была более практичной, т.к., в отличие от системы счёта на абаке, была основана на индийской позиционной системе счисления, позволявшей быстро и просто считать, не прибегая к громоздкому абаку.

Цифры проникли во все стороны деятельности, связанные со счётом. Новая позиционная нумерация постепенно вытеснила старую практически во всех странах.

Позднее особую устойчивость приобретает словоупотребление «алгоритм Евклида». И вплоть до XX века слово «алгоритм» употребляется только так.

1.5 Ключевые события в истории развития теории алгоритмов

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

IV-III века до н.э. Появление первых алгоритмов: Алгоритм Евклид для наибольшего общего делителя, решето Эратосфена.

1822 - Чарльз Беббидж приступил к созданию "разностной машины"

1926 - Борувка - первый алгоритм нахождения остовного дерева (далее Ярник, Прим и Крускал).

1936 - В Германии Конрад Зусе приходит к выводу, что программы, состоящие из битовых комбинаций, можно запоминать; он подает заявку на патентование метода автоматического выполнения вычислений с использованием "памяти комбинаций"

1936 - Алан Тьюринг, строгое понятие алгоритма (машина Тьюринга). Тезис Черча: любой алгоритм может быть представлен в виде машины Тьюринга.

1939 - Леонид Канторович - формулировка задачи линейного программирования, первый алгоритм для ее решения.

1945 - Джон фон Нейман (John von Neumann) в своем докладе по проектированию EDVAC (Electronic Discrete Variable Automatic Computer) ввел понятие запоминаемой программ

1947 - Георг Данциг создает симплекс метод

1948 - Альфред Тарский - алгоритм проверки истинности любого утверждения о вещественных числах в логике первого порядка.

1948 - Клод Шеннон опубликовал "Математическую теорию связи", заложив таким образом основу современного понимания коммуникационных процессов

1948 - Ричард Хемминг сформулировал способ обнаружения и корректировки ошибок в блоках данных

1952 - алгоритм архивирования Хаффмана

1954 - Сьюард - сортировка подсчетом (линейное время в среднем)

1959 - Джон Маккарти разработал LISP (list processing) - язык для использования в задачах искусственного интеллекта

1962 - Дэвис, Лоджеман, Лавлэнд - DLL алгоритм для SAT и других NP-полных задач.

1962 - Форд и Фалкерсон - полиномиальный алгоритм нахождения максимального потока.

1962 - Хоар - Quicksort (алгоритм быстрой сортировки)

1962 - Адельсон-Вельский и Ландис - AVL-деревья (балансированные деревья)

1964 - Дж.Вильямс - Heapsort (сортировка с помощью кучи)

1965 - Алан Робинсон - основание логического программирования.

1965 - Хартманис и Стернс: определение понятия «вычислительная сложность», зарождение теории сложности. Понятие массовой задачи?

1965 - Владимир Левенштейн - Введение редакторского расстояния

1969 - Штрассен - быстрый алгоритм перемножения матриц

1970 - Юрий Матиясевич - вычислительная неразрешимость решения диофантовых уравнений (решена 10ая проблема Гильберта).

1971 - Вапник и Червоненкис - метод опорных векторов (support vector machines и VC размерность).

1971-1972 - Кук, Левин, Карп - основание теории NP-полноты.

1975 - Джон Холланд - разработка генетических алгоритмов

1976 - Диффи и Хеллман - установление непосредственной связи между криптографией и теорией сложности.

1977 - Лемпель и Зив - алгоритм для архивирования текстов.

1976 - Кнут, Моррис и Пратт - линейный алгоритм поиска подстрок

1977 - Алгоритм Бойера-Мура поиска подстрок

1978 - Райвест, Шамир, Адлеман - разработка криптосистемы RSA.

1979 - Гэри и Джонсон - систематизация теории NP-полноты.

1979 - Леонид Хачиян - полиномиальный алгоритм решения задачи линейного программирования

1981 - Карл Померанц - метод квадратичного решета для разложения чисел на множители

1982 - Эндрю Яо - определение функции с секретом.

1982 - Тейво Кохонен - самоорганизующиеся карты (self-organizing maps)

1984 - Кармаркар - метод внутренней точки для задачи линейного программирования

1985 - Александр Разборов - Теорема Разборова (нижняя экспоненциальная оценка на сложность решения задачи о клике монотонными схемами).

1986 - Псевдослучайный генератор Блюма, Блюма и Шуба

1989 - Тим Бернерс-Ли предложил CERN (Европейскому совету ядерных исследований) проект World Wide Web

1989 - Голдвассер, Микали и Раков - определение доказательства с нулевым разглашением.

1991 - Корман, Лейзерсон и Райвест - «Введение в алгоритмы» - главная книга по алгоритмам во всем мире.

1992 - Ади Шамир - IP = PSPACE (важный результат в теории сложности, объясняющий, что два разных понимания сложности задачи на самом деле совпадают).

1992 - Арора, Сафра и Арора, Лунд, Мотвани, Судан, Шегеди - Теорема о вероятностно-проверяемых доказательствах (PCP-theorem).

1993 - МакМиллан - Символьный алгоритм верификации программ

1994 - Питер Шор - Квантовый алгоритм разложения чисел на множители.

1994 - В университете Южной Калифорнии Леонард Адлеман продемонстрировал, что ДНК может быть использована как вычислительное средство

1994 - Преобразование Берроуза-Вилера

1996 - Алгоритм Гровера для поиска на квантовом компьютере

2002 - Агравал, Кайал, Саксена, полиномиальный алгоритм проверки числа на простоту.

2004 - Алгоритм Вильямса - прорыв барьера 2^n для задачи о максимальном разрезе.

1.6 Основные результаты теории алгоритмов

Появлению формализованного понятия алгоритма в математике мы обязаны Тьюрингу, Посту, Чёрчу, Маркову и Колмогорову и др. Именно они явно поставили и решили задачу формального описания понятия «алгоритм». Само понятие алгоритма было осознано только к началу XX века. В работах Бореля (1912г.) и Вейля (1921 г.) встречаются едва ли не самые ранние примеры использования понятия эффективно вычислимой процедуры. «Я намеренно оставляю в стороне большую или меньшую практическую деятельность; суть здесь та, что каждая из этих операций осуществима в конечное время при помощи достоверного и недвусмысленного метода», -- подчёркивает Борель, говоря о «вычислениях, которые могут быть реально осуществлены»[7].

С возникновением понятия алгоритма в математике начали появляться теоремы о несуществовании алгоритмов для решения некоторых задач. Эти теоремы впоследствии и заложили фундамент теории алгоритмов. Теория алгоритмов очень быстро обнаружила ряд фундаментальных приложений в математике. Среди них: связь алгоритмов и исчислений, неразрешимость арифметики, алгоритмичность доказательств.

Также теория алгоритмов позволила определить некоторые подходы в теоретическом и практическом программировании.

Ниже перечислены основные открытия, связанные с общими понятиями алгоритма и исчисления:

1. Общее понятие алгоритма как самостоятельное (отдельное) понятие.

2. Представительные вычислительные модели.

3. Общее понятие исчисления как самостоятельное (отдельное) понятие.

4. Представительные порождающие модели.

5. Выяснение связей между алгоритмами и исчислениями.

6. Время и ёмкость как сложности вычисления и порождения.

7. Вычислимые функции и породимые множества.

8. Понятие частично-рекурсивной функции.

9. Возможность арифметического и даже диофантова представления любого перечислимого числового множества.

10. Построение неразрешимого породимого числового множества.

11. Проблема сводимости Поста.

12. Понятие относительного алгоритма, или алгоритма с оракулом.

13. Понятие вычислимой операции.

14. Понятие программы: программы как объекты вычисления и порождения.

15. Понятие нумерации и теория нумераций.

16. Начало создания инвариантной, или машинно-независимой, теории сложности вычислений.

17. Теория сложности энтропии конструктивных объектов.

18. Удобные и экономные вычислительные модели[2].

Таким образом, даже просто просматривая этот список, убеждаемся, что возникновение общего понятия алгоритма само по себе очень обогатило математику, фактически открыв новую её ветвь. Но ещё более удивительно, когда видим, насколько глубоко проникла теория алгоритмов в другие области математики. Её приложения настолько фундаментальны, что заставили пересмотреть некоторые основы математики. Например, само понятие доказательства оказывается подпонятием алгоритма.



2. Эволюционные алгоритмы и история их появления

Природа поражает своей сложностью и богатством всех своих проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, которые стали более очевидны, когда мы стали глубже исследовать себя самих и мир вокруг нас. Наука - это одна из сменяющих друг друга систем веры, которыми мы пытается объяснять то, что наблюдаем, этим самым изменяя себя, чтобы приспособиться к новой информации, получаемой из внешнего мира. Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией: теорией эволюции через наследственность, изменчивость и отбор.

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как «Происхождение Видов», в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как «эволюционный синтез» укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, «спуск с модификацией». Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в природе.

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - «Адаптация в естественных и искусственных системах» («Adaptation in Natural and Artifical Systems», 1975)[5]. В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

Главная трудность с возможностью построения вычислительных систем, основанных на принципах естественного отбора и применением этих систем в прикладных задачах, состоит в том, что природные системы достаточно хаотичны, а все наши действия, фактически, носят четкую направленность. Мы используем компьютер как инструмент для решения определенных задач, которые мы сами и формулируем, и мы акцентируем внимание на максимально быстром выполнении при минимальных затратах. Природные системы не имеют никаких таких целей или ограничений, во всяком случае нам они не очевидны. Выживание в природе не направлено к некоторой фиксированной цели, вместо этого эволюция совершает шаг вперед в любом доступном ее направлении.

Возможно это большое обобщение, но все же усилия, направленные на моделирование эволюции по аналогии с природными системами, к настоящему времени можно разбить на две большие категории:

1) системы, которые смоделированы на биологических принципах. Они успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на небиологическом языке;

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

Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life)[11].

Конечно, эволюция биологических систем не единственный «источник вдохновения» создателей новых методов, моделирующих природные процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

2.1 Генетические алгоримы

Одним из ответвлений эволюционных алгоритмов являются генетические, основывающиеся на естественном отборе и генетике.

Основная изюминка алгоритма -- скрещивание (комбинирование). Как несложно догадаться идея алгоритма наглым образом взята у природы. Так вот, путем перебора и самое главное отбора получается правильная «комбинация».

Алгоритм делится на три этапа:

- скрещивание;

- селекция (отбор);

- формирование нового поколения.

Если результат не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

- количество поколений (циклов) достигнет заранее выбранного максимума;

- исчерпано время на мутацию.

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере установленном в Институте перспективных исследований Принстонского университета. Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года, австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970) и Кросби (1973), с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов[4]. Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998).

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру, искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века -- группа Рехенсберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции. Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975). Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver -- первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал об Evolver в 1990 году.

2.2 Современное состояние теории алгоритмов

2.2.1 Использование других наук в алгоритмах

Информатика и ее центральная область, теория алгоритмов, возникла недавно. И естественно, что она многое берет у старших наук-соседей.

Физика. Влияние физики в информатике проявилось только в последние годы и вызвало настоящий взрыв новых исследований. Центральным направлением, объединяющим эти науки, стало изучение нестандартных моделей вычислений. Как показал еще физик Ричард Фейнман, физические явления, такие как спин электрона, могут быть использованы для вычислений. Современные исследования показали, по-видимому, квантовые алгоритмы не сводятся к обычной (использующей биты) модели вычислений. Следовательно, пространство эффективно решаемых задач расширяется. Упомянем здесь также такие темы, как вычисления с вещественными числами (Real RAM), оптический компьютер и даже (!) бильярдные вычисления[9].

Теория вероятностей. Одна из наиболее применяемых математических теорий в информатике. Два ключевых направления: оценка времени работы алгоритма «в среднем», и вероятностные алгоритмы. Исследования в теории сложности показывают, что детерминированные алгоритмы не всегда дают наилучшие решение. Более того, на практике вероятностные алгоритмы могут работать заметно быстрее даже при наличии альтернативного детерминированного алгоритма (например, задача проверки на простоту).

Биология. Для решения самых трудных задач своей деятельности человек обращается за помощью к природе. Что делать, если мы хотим найти решение для таких трудных и неформализуемых задач, как классификация и распознавание образов? Посмотреть, как эта задача решается в природе - то есть человеческим мозгом! Так возникла идея симуляции и моделирования вычислительных способностей нейронов. Предложенная модель получила название нейронных сетей. Затем был сделан следующий шаг. Важно не только как человек решает конкретную задачу (младенцы довольно плохо приспособлены к жизни), важно с какой феноменальной скоростью человек обучается в течении своей жизни. Так возникла теория машинного обучения (machine learning).

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

Математическая логика. Собственно, из нее и выросла теория алгоритмов. Мечтой математиков начала XX века было создание единого (вычислительного) метода решения математических проблем. К сожалению, как показал уже Тьюринг, существуют вычислительно неразрешимые задачи. Тем не менее, логика дала мощный аппарат выражения различных свойств математических объектов и формальные правила работы с этими свойствами. В современной теоретической информатике логика используется для разработки новых языков программирования, задач автоматической верификации программ и для изучения сложности вычислительных задач (proof complexity)[10].

Функциональный анализ. Оказывается, что и непрерывная математика необходима в разработке алгоритмов. Это случается, в основном, при компьютерной обработке явлений, имеющих непрерывную природу. Это, конечно же, цифровая обработка аудио и видео записей. Такие широко используемые стандарты, как MPEG и JPG содержат идеи, взятые из свойств преобразования Фурье и активно используют дискретный аналог операции свертки.

2.2.2 Наиболее значимые применения алгоритмов

Первым прикладным направлением, по существу выделившим теорию вычислений в отдельное направление стали численное решение уравнений из физики, расчеты в атомной сфере и управление космическими кораблями и спутниками.

Следующим источником множества вычислительных задач стали вопросы оптимизации задачи в экономике. К основным достижениям стоит отнести формулировку задачи линейного программирования (Канторовича), симплекс-метод, алгоритмы Кармаркара и алгоритм Хачияна.

Успехи математической статистики и развитие измерительных приборов и рентгенов породили необходимость в алгоритмах автоматической диагностики и обработки данных томографии. Сейчас с огромной скоростью проводится внедрение компьютерной техники в самых разных направлениях медицины.

С ростом объемов информации возникла необходимость в эффективных механизмах ее хранения и использования. алгоритмы обработки запросов в базах данных относятся к числу наиболее широко применимых.

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

Главным направлением развития информационных технологий последних двух десятилетий стал Интернет и распределенные вычисления. Теория алгоритмов здесь находит свое применение в задачах маршрутизации пакетов (TCP/IP и DNS) и поисковых системах. Небывалый успех системы Google стал, пожалуй, самым запоминающимся случаем, когда простая математическая идея (алгоритм PageRank) привела к феноменальному коммерческому успеху.

Особое значение играет решение задач, успех в которых нельзя строго сформулировать - так называемые задачи искусственного интеллекта. Перечислим лишь некоторые: автоматическое распознавание речи, отпечатков пальцев, лиц людей, системы распознавания свой - чужой, автоматическая классификация, автоматический контроль качества.

В конце концов, теория алгоритмов пришла к тому, что объектами обработки стали сами алгоритмы. Основными задачами являются автоматическая верификация и оптимизация программ и системы по распараллеливанию выполнения программ на многопроцессорных вычислительных системах.

Следующим направлением являются лингвистические алгоритмы: проверка орфографии, автоматический перевод, «разговаривающие» программы. Следующим шагом стала работа с грамматикой.

Наконец, компьютерам стали доверять все более и более важные задачи. Методы машинного обучения используются в разработке роботов (особенно заманчивой звучит создание футбольной команды роботов, способной выиграть у чемпионов мира 2050 года). Естественно ожидать, что время распространения устройств, оснащенных датчиками и способных самостоятельно принимать оптимальное решение, наступит очень скоро.

Наиболее популярным прикладным направление в самое последнее время стали исследования в биоинформатике: вычисление (восстановление) геномов и построение наиболее вероятной цепочки мутаций, которая переводит один генотип в другой.



Заключение

Подытожим, благодаря способности фиксировать и выражать свой разум (или, по меньшей мере, разумное поведение) посредством алгоритмов, мы способны создавать вычислительные машины, выполняющие полезные задачи. Вследствие этого, уровень «интеллектуальности» вычислительных машин ограничен уровнем «интеллектуальности» алгоритмов, на которых они основаны. Мы можем сконструировать вычислительную машину для решения какой-то задачи, только если существует алгоритм ее решения. В свою очередь, если не существует алгоритма решения какой-либо задачи или проблемы, то и ее решение лежит за рамками возможностей вычислительных машин.

Тему ограниченности алгоритмических возможностей в математике установил Курт Гёдель (Kurt Gцdel) в 1930 году, опубликовав «теорему о неполноте». По существу в этой теореме утверждается, что в любой математической теории такой как традиционная арифметика, существуют утверждения, чья истинность или ложь не может быть установлена алгоритмически.

Осознание этого пошатнуло фундамент математики, а изучение возможностей алгоритмов положило начало формированию такой науки как «теория вычислительных машин и систем» (computer science). Как еще преобразится теория алгоритмов в будущем, покажет время.



Библиографический список

1. Theory of Computation: Goals and Perspective

http://eccc.hpi-web.de/eccc/info/DISCUSSIONS/GoalsPerspectives.html

2. ACM/IEEE Computing Curricula 2001

http://se.math.spbu.ru/cc2001/

3. Most cited articles in Computer Science

http://citeseer.ist.psu.edu/articles.html

4. Ривест Р., Кормен Т., Лейзерсон Ч. “Алгоритмы: построение и анализ”

5. Michael Nielsen: Principles of Effective Research

http://www.qinfo.org/people/nielsen/blog/archive/000120.html

6. А.Разборов. Theoretical Computer Science: взгляд математика.

http://www.computerra.ru/offline/2001/379/6782/

7. Лэнс Фортноу. Мои любимые теоремы.

http://weblog.fortnow.com/2006/01/favorite-theorems-preview.html

8. Мультимедиа продукт "История Информатики"

http://cshistory.nsu.ru

9. Computer Sciences - основные вехи ("Timeline of Computing History", Computer, Vol. 29, No.10 Translated from the original English version and reprinted with permission (IEEE))

http://www.dvgu.ru/meteo/PC/ComputerHystor.htm

10. History of Algorithms

http://cs-exhibitions.uni-klu.ac.at/index.php?id=193

11. Timeline of algorithms

http://en.wikipedia.org/wiki/Timeline_of_algorithms

Размещено на Allbest.ru

...