Надо Знать

добавить знаний



Алгоритм



План:


Введение

Страница "Алгебры" аль-Хорезми - персидского математика, от имени которого происходит слово алгоритм.

Алгоритм (латинизов. Algorithmi, от имени персидского математика IX в. аль-Хорезми) - последовательность, система, набор систематизированных правил выполнения вычислительного процесса, что обязательно приводит к решению определенного класса задач после конечного числа операций. [1] При написании компьютерных программ алгоритм описывает логическую последовательность операций. Для визуального изображения алгоритмов часто используют блок-схемы.

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

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

Частичная формализация понятия алгоритма началась с попыток решения задачи разрешимости ( нем. Entscheidungsproblem ), Которую сформулировал Давид Гильберт в 1928 году. Следующие формализации были необходимы для определения эффективной обчислювальности [2] или "эффективного метода" [3]; до сих формализаций принадлежат рекурсивные функции Геделя -Ербрана- Клини 1930, 1934 и 1935 годов, λ-исчисление Алонзо Черча 1936 г., "Формулировка 1" Эмиля Поста 1936 года, и машина Тьюринга, разработана Аланом Тьюринга течение 1936, 1937 и 1939 годов. В методологии алгоритм является базисным понятием и составляет основу описания методов. Из методологии получается качественно новое понятие алгоритма как оптимальность с приближением к прогнозируемому абсолюта. Сделав все в последовательности алгоритма по граничных условий задачи имеем идеальное решение насущных проблем научно-практического характера. В современном мире алгоритм любой деятельности в формализованном выражении составляет основу образования на примерах, за подобия. На основе сходства алгоритмов различных сфер деятельности была сформирована концепция (теория) экспертных систем.


1. История

Слово алгоритм происходит от имени персидского ученого, астронома и математика Аль-Хорезми. Примерно 825 до н.е. он написал трактат, в котором описал придуманную в Индии позиционную десятичную систему счисления.

В первой половине XII века книга попала в Европы в переводе латинском языке под названием Algoritmi de numero Indorum. Считается, что первое слово в переводе соответствует неудачной латинизации имени Аль-Хорезми, а название перевода звучит как "Алгоритм об индийской математике".

Из-за неверного толкования слова Algoritmi как существительного в множестве ним стали называть метод вычисления.

Баронесса Ада Лавлейс, которую считают первым программистом.

Первый алгоритм, предназначенный для выполнения на автоматическом вычислительном устройстве ( компьютере), описала Ада Лавлейс в 1843 году. Алгоритм должен вычислять числа Бернулли и работать на аналитической машине Бэббиджа. Этот алгоритм считается первой компьютерной программой, а его розробниця, Ада Лавлейс - первым программистом [4].

С 1930-х годов начинается бурное развитие отрасли исследование алгоритмов и становления информатики в ее современном виде. В 1935 году Стивен Клини разработал первую формулировку теории рекурсии, и показал эквивалентность разработанной системы частично рекурсивным функциям. В 1936 году независимо были опубликованы работы Алана Тьюринга и Эмиля Поста, в которых приведены похожие системы для определения понятия алгоритма. А уже в 1937 году было доказано эквивалентность различных определений [5].

Машина Тьюринга предлагала конструкцию, пригодную для автоматической интерпретации. Построена под влиянием Алана Тьюринга в Великобритании вычислительная система ACE (завершена в 1950 году), и системы, построенные по архитектурой фон Неймана в США и в других странах (в СССР - МЭСМ, разработанная в 1950 году в Институте электротехники АН УССР группой ученых под руководством Сергея Лебедева), были первыми универсальными вычислительными устройствами, которые полностью удовлетворяли требования обчислювальности [6].

Течение 1935 - 1960 годов было разработано многочисленные идеи и технологии, которые легли в основу современной информатики.

Формальные средства для представления алгоритмов имели не только теоретическую значимость. Разработка алгоритмических языков для программирования вычислительных устройств началась в 1951 году с публикации немецкого инженера Ганса Рутисхаузера ( нем. Heinz Rutishauser ). Сначала важной казалась проблема нотации, ее исследовал Алексей Ляпунов, но постепенно она отошла на второй план [7].

Первая язык, Планкалькуль ( нем. Plankalk?l ) Была разработана Конрадом Цузе в 1946 году, но из-за отсутствия компиляторов выполнения написанных на этом языке программ было невозможно. Описание языка был напечатан в 1972 году, а в 2000 году был создан компилятор для подмножества языка. [8]

В середине 1950-тех был разработан язык программирования Фортран Джоном Бакус с IBM. В конце 1950-тех был разработан Алгол и Кобол, для учебных целей Бейсик (1963) и Паскаль (начало 1970-х). Для системного программирования в Bell Laboratories был разработан C [9].

λ-Исчисление дало толчок к созданию в конце 1950-тех функциональной языка программирования Лисп. На основе идей Лиспа было создано Scheme. Язык ML была разработана Робином Милнером в конце 1970-х. В конце 1980-е был создан язык Haskell [10].

Под влиянием исследований в области искусственного инетелекту разработан парадигму логического программирования. В отличие от императивной и функциональной парадигм, логическое программирование не требует от разработчика описывать способ решения поставленной задачи. Planner - первый язык логического программирования, была разработана в 1969 году. В начале 1970-х был разработан Пролог, который впоследствии стал распространенным языком логического программирования со стандартом ISO, утвержденным в 1995 году [11].


2. Определение

2.1. Неформальное определение

Каждый алгоритм предполагает существование начальных (входных) данных и в результате работы приводит к получению определенного результата. Работа каждого алгоритма происходит путем выполнения последовательности некоторых элементарных действий. Эти действия называют шагами, а процесс их выполнения называют алгоритмическим процессом. Таким образом отмечают свойство дискретности алгоритма [12].

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

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

Вхідні дані алгоритму можуть бути обмежені набором припустимих вхідних даних. Застосування алгоритму до неприпустимих вхідних даних може призводити до того, що алгоритм ніколи не зупиниться, або потрапить в тупиковий стан (зависання) з якого не зможе продовжити виконання.


2.2. Формальне визначення

Різноманітні теоретичні проблеми математики та прискорення розвитку фізики та техніки поставили на порядок денний точніше визначення поняття алгоритму.

Перші спроби уточнення поняття алгоритму та його дослідження здійснювали в першій половині XX століття Алан Тюринг, Еміль Пост, Жак Ербран, Курт Гедель, Андрій Марков, Алонзо Черч. Було розроблено декілька означень поняття алгоритму, але згодом було з'ясовано, що всі вони визначають одне й те саме поняття (див. теза Черча). [13]


2.2.1. Машина Тюринга

Схематична ілюстрація роботи машини Тюринга.

Основна ідея, що лежить в основі машини Тюринга, дуже проста. Машина Тюринга - це абстрактна машина (автомат), що працює зі стрічкою окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок, яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує голівка, та, на основі зчитаного символу й внутрішнього стану робить наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку, або пересунути голівку на одну комірку ліворуч або праворуч. [14]

На основі дослідження цих машин було висунуто тезу Тюринга (основна гіпотеза алгоритмів):

Для знаходження значень функції, заданої в деякому алфавіті, тоді і лише тоді існує деякий алгоритм, коли функція обчислювана за Тюрингом, тобто, коли її можна обчислити на придатній машині Тюринга.

Ця теза є аксіомою, постулатом, і не може бути доведена математичними методами, оскільки алгоритм не є точним математичним поняттям.


2.2.2. Рекурсивні функції

З кожним алгоритмом можна зіставити функцію, яку він обчислює. Однак постає питання, чи можна довільній функції зіставити машину Тюринга, а якщо ні, то для яких функцій існує алгоритм? Досліження цих питань призвело до створення в 1930-их роках теорії рекурсивних функцій [15].

Клас обчислюваних функцій було описано в спосіб, що нагадує побудову деякої аксіоматичної теорії на базі системи аксіом. Спочатку було вибрано найпростіші функції, обчислюваність яких очевидна. Потім було сформульовано правила (оператори) побудови нових функцій на основі вже існуючих. Необхідний клас функцій складається з усіх функцій, які можна отримати з найпростіших застосуванням операторів.

Подібно тезі Тюринга в теорії обчислюваних функцій висунуто гіпотезу, що має назву теза Черча :

Числова функція тоді і лише тоді алгоритмічно обчислювана, коли вона частково рекурсивна.

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

Таким чином, неформально алгоритм можна визначити як чітку систему інструкцій, що визначають дискретний детермінований процес, який веде від початкових даних (на вході) до шуканого результату (на виході), якщо він існує, за скінченну кількість кроків; якщо шуканого результату не існує, алгоритм або ніколи не завершує роботу, або заходить у глухий кут.


2.2.3. Нормальні алгорифми Маркова

Нормальні алгорифми Маркова - це система послідовних застосувань підстановок, які реалізують певні процедури отримання нових слів з базових, побудованих із символів деякого алфавіту. Як і машини Тюринга, нормальні алгоритми не виконують самих обчислень: вони лише виконують перетворення слів шляхом заміни літер за заданими правилами [16].

Нормально обчислюваною називають функцію, яку можна реалізувати нормальним алгоритмом. Тобто, алгоритмом, який кожне слово з множини припустимих даних функції перетворює на її вихідні значення [17].

Творець теорії нормальних алгоритмів А. А. Марков висунув гіпотезу, яка отримала назву принцип нормалізації Маркова :

Для знаходження значень функції, заданої в деякому алфавіті, тоді і лише тоді існує деякий алгоритм, коли функція нормально обчислювана.

Подібно до тез Тюринга та Черча, принцип нормалізації Маркова не може бути доведений математичними засобами.


2.3. Стохастичні алгоритми

Однако, приведенное выше формальное определение алгоритма в некоторых случаях может быть слишком строгим. Иногда возникает необходимость в использовании случайных величин [18]. Алгоритм, работа которого определяется не только входными данными, но и значениями полученными из генератора случайных чисел, называют стохастическим (или рандомизированным, от англ. randomized algorithm ) [19]. Формально, такие алгоритмы нельзя называть алгоритмами поскольку существует вероятность (близка к нулю), что они не остановятся. Однако, стохастические алгоритмы часто бывают эффективнее детерминированы, а в отдельных случаях - единственным способом решить задачу [18].

На практике вместо генератора случайных чисел используют генератор псевдослучайных чисел.

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

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

  • алгоритмы типа Лас-Вегас всегда дают корректный результат, но время их работы определен.
  • алгоритмы типа Монте-Карло, в отличие от предыдущих, могут давать неправильные результаты с известной вероятностью (их часто называют методами Монте-Карло).

2.4. Другие формализации

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

и другие.


3. Нумерация алгоритмов

Нумерация алгоритмов играет важную роль в их исследовании и анализе [21].

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

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

Существование нумерации позволяет работать с алгоритмами так же, как с числами. Особенно полезна нумерация в исследовании алгоритмов, работающих с другими алгоритмами.


4. Алгоритмически неразрешимые задачи

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

Функцию f называют вычислимой ( англ. computable ), Если существует машина Тьюринга, которая вычисляет значение f для всех элементов множества определения функции. Если такой машины не существует, функцию f называют необчислюваною. Функция считаться необчислюваною даже если существуют машины Тьюринга, способны вычислить значение для подмножества из всего множества входных данных [22].

Случай, когда результатом вычисления функции f является булево значение истина или ложь (или множество {0, 1}) называют задачей, которая может быть разрешимой, или неразрешимой в зависимости от вычислимости функции f [22].

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

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

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

Доказательство неразрешимости проблемы остановки важен тем, что к ней можно свести другие задачи. Например, проблему остановки на пустой ленте (определить для заданной машины Тьюринга остановится она, будучи запущена на пустой ленте) можно свести к простой задачи остановки, доказав, тем самым, ее неразрешимость [22].


5. Анализ алгоритмов

5.1. Доказательство корректности

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

Использование математического аппарата для анализа алгоритмов и их реализаций называют формальными методами. Формальные методы предусматривают применение формальных спецификаций и обычно набора инструментов для синтаксического анализа и доведения свойств спецификаций. Абстрагирования от деталей реализации позволяет установить свойства системы независимо от ее реализации. Кроме того, точность и однозначность математических утверждений позволяет избежать многозначности и неточности естественных языков [24].

По гипотезе Ричарда Мейса "избежание ошибок лучше устранения ошибок" [25]. По гипотезе Хоара "доведение программ решает проблему корректности, документации и совместимости" [26]. Доказательство корректности программ позволяет выявлять свойства по отношению ко всему диапазону входных данных. Для доказательства корректности программ, понятие корректности было расширено на два типа:

  • Частичная корректность - программа дает корректный результат для тех случаев, когда она завершается.
  • Полная корректность - программа завершает работу и выдает корректный результат для всех элементов из диапазона входных данных.

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

P {Q} R

где P - это предпосылка, что должно выполняться перед запуском программы Q, а R - писляумова, правильная после завершения работы программы.

Формальные методы были успешно применены к широкому кругу задач, в частности: разработка схем, искусственного интеллекта, систем, чувствительных к надежности, безопасности, автоматических систем на железной, верификации микропроцессоров, спецификации стандартов и спецификации и верификации программ [27].


5.2. Время работы

Графики функций приведенных в таблице ниже.

Распространенным критерием оценки алгоритмов является время работы и порядок роста продолжительности работы в зависимости от объема входных данных. [28]

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

Время, затраченное алгоритм как функция от размера задачи n, называют временной сложностью этого алгоритма T (n). Асимптотики поведения этой функции при увеличении размера задачи называют асимптотической временной сложности, а для ее обозначения используют нотацию Ландау (большая O).

Именно асимптотическая сложность определяет размер задач, алгоритм способен обработать. Например, если алгоритм обрабатывает входящие данные размером n за время cn ?, где c - некоторая постоянная, то говорят, что временная сложность такого алгоритма O (n ?).

Часто, під час розробки алгоритму намагаються зменшити асимптотичну часову складність для найгірших випадків. На практиці ж, трапляються випадки, коли достатнім є алгоритм, який "зазвичай" працює швидко.

Грубо кажучи, аналіз середньої асимптотичної часової складності можна поділити на два типи: аналітичний та статистичний. Аналітичний метод дає точніші результати, але складний у використанні на практиці. Натомість статистичний метод дозволяє швидше здійснювати аналіз складних задач [29].

В наступній таблиці наведено поширені асимптотичні складності з коментарями [30].

Складність Комментарий Примеры
O (1) Сталий час роботи не залежно від розміру задачі Очікуваний час пошуку в хеші
O (log log n) Дуже повільне зростання необхідного часу Очікуваний час роботи інтерполюючого пошуку n елементів
O (log n) Логарифмічне зростання - подвоєння розміру задачі збільшує час роботи на сталу величину Обчислення x n; двійковий пошук в масиві з n елементів
O ( n) Лінійне зростання - подвоєння розміру задачі подвоїть і необхідний час Додавання/віднімання чисел з n цифр; лінійний пошук в масиві з n елементів
O ( n log n) Лінеаритмічне зростання - подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі Сортування злиттям або купою n елементів; нижня границя сортування порівнянням n елементів
O ( n ?) Квадратичне зростання - подвоєння розміру задачі вчетверо збільшує необхідний час Елементарні алгоритми сортування
O ( n ?) Кубічне зростання - подвоєння розміру задачі збільшує необхідний час у вісім разів Звичайне множення матриць
O ( c n) Експоненціальне зростання - збільшення розміру задачі на 1 призводить до c -кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат Некоторые задачі комівояжера, алгоритми пошуку повним перебором

6. Представлення алгоритмів

Блок-схема алгоритму визначення дієвідміни в дієслові.

В процесі розробки алгоритму можуть використовуватись різні способи його опису, які відрізняються за простотою, наочністю, компактністю, мірою формалізації, орієнтації на машинну реалізацію тощо [31].

Форми запису алгоритму:

  • словесна або вербальна (мовна, формульно-словесна);
  • псевдокод (формальні алгоритмічні мови);
  • схемна:
    • структурограми (схеми Нассі-Шнайдермана);
    • графічна (блок-схема, виконується за вимогами стандарту).

7. Властивості алгоритмів

Алгоритми мають ряд важливих властивостей: [32]

Скінченність
алгоритм має завжди завершуватись після виконання скінченної кількості кроків. Процедуру, яка має решту характеристик алгоритму, без, можливо, скінченності, називають методом обчислень.
Дискретність
процес, що визначається алгоритмом, можна розчленувати (розділити) на окремі елементарні етапи (кроки), кожен з яких називається кроком алгоритмічного процесу чи алгоритму. [31]
Визначеність
кожен крок алгоритму має бути точно визначений. Дії, які необхідно здійснити, повинні бути чітко та недвозначно визначені для кожного можливого випадку.
Вхідні дані
алгоритм має деяку кількість (можливо, нульову) вхідних даних, тобто, величин, заданих до початку його роботи або значення яких визначають під час роботи алгоритму.
Исходные данные
алгоритм має одне або декілька вихідних даних, тобто, величин, що мають досить визначений зв'язок із вхідними даними.
Эффективность
Алгоритм вважають ефективним, якщо всі його оператори досить прості для того, аби їх можна було точно виконати за скінченний проміжок часу з допомогою олівця та аркушу паперу.
Масовість
властивість алгоритму, яка полягає в тому, що алгоритм повинен забезпечувати розв`язання будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до області застосування алгоритму.

8. Пример

В якості прикладу можна навести алгоритм Евкліда.

Алгоритм Евкліда - ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, один з найдавніших алгоритмів, що досі використовують [33]. Описаний в Началах Евкліда (приблизно 300 до н. е.), а саме, в книгах VII та X. В сьомій книзі алгоритм описано для цілих чисел, а в десятій - для довжин відрізків.

Існує декілька варіантів алгоритму, нижче записано в псевдокоді рекурсивний варіант:

 функція нсд(a, b) якщо b = 0 поверни a інакше поверни нсд(b, a mod b) 

См.. также

Nuvola apps edu mathematics blue-p.svg
В Википедии есть портал

Литература

  • Классические учебники
  • История
    • Gerard O'Regan A Brief History of Computing. - Springer, 2008. - ISBN 978-1-84800-083-4
    • Friedrich L. Bauer Origins and Foundations of Computing = Kurze Geschichte der Informatik. - Springer, 2010. - ISBN 978-3-642-02991-2
  • Каталоги алгоритмів
    • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein Introduction to Algorithms 2-ге. - MIT Press, 2001. ISBN 0-262-03293-7.
    • под ред. Ming-Yang Kao Encyclopedia of Algorithms. - Springer, 2008. - (Springer Reference). - ISBN 978-0-387-30162-4
    • под ред. Mikhail J. Atallah та Marina Blanton Algorithms and theory of computation handbook. General concepts and techniques. - 2-ге. - Chapman & Hall/CRC, 2010. - (applied algorithms and data structures). - ISBN 978-1-58488-822-2 та другий том ISBN 978-1-58488-820-8

код для вставки
Данный текст может содержать ошибки.

скачать

© Надо Знать
написать нам