Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Алгоритм



План:


Введення

Wikitext-ru.svg
Цю статтю варто вікіфіціровать.
Будь ласка, оформіть її згідно правил оформлення статей.
Аль-Хорезмі на радянській марці

Алгоритм, від імені вченого аль-Хорезмі ( перс. خوارزمی [Al-Khwārazmī]) - точний набір інструкцій, що описують порядок дій виконавця для досягнення результату виконання завдання за кінцевий час. У старій трактуванні замість слова "порядок" використовувалося слово "послідовність", але в міру розвитку паралельності в роботі комп'ютерів слово "послідовність" стали замінювати більш загальним словом "порядок". Це пов'язано з тим, що робота якихось посібників алгоритму може бути залежна від інших інструкцій або результатів їх роботи. Таким чином, деякі інструкції повинні виконуватися строго після завершення роботи посібників, від яких вони залежать. Незалежні інструкції або інструкції, що стали незалежними через завершення роботи посібників, від яких вони залежать, можуть виконуватися в довільному порядку, паралельно або одночасно, якщо це дозволяють використовуються процесор і операційна система.

Раніше часто писали "алгоритми ф м", зараз таке написання використовується рідко, але, тим не менш, має місце (наприклад, Нормальний алгорифм Маркова).

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

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

Часткова формалізація поняття алгоритму почалася зі спроб рішення проблеми дозволу ( ньому. Entscheidungsproblem ), Яку сформулював Давид Гільберт в 1928. Наступні етапи формалізації були необхідні для визначення ефективних обчислень [1] або "ефективного методу" [2]; серед таких формалізації - рекурсивні функції Геделя - Ербрана - Кліні 1930, 1934 і 1935 рр.., λ-числення Алонзо Черча 1936 р., " Формулювання 1 " Еміля Поста 1936 і машина Тьюринга. У методології алгоритм є базисним поняттям і отримує якісно нове поняття як оптимальності в міру наближення до прогнозованого абсолюту. У сучасному світі алгоритм у формалізованому виразі становить основу освіти на прикладах, за подобою. На основі подібності алгоритмів різних сфер діяльності була сформована концепція (теорія) експертних систем.


1. Історія терміна

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

Сучасне формальне визначення алгоритму було дано в 30-50-х роки XX століття в роботах Тьюринга, Посту, Черча ( тезу Черча - Тьюринга), Н. Вінера, А. А. Маркова.

Саме слово "алгоритм" походить від імені перського вченого Абу Абдуллах Мухаммеда ібн Муса аль-Хорезмі (алгоритм - аль-Хорезмі). Близько 825 року він написав твір, в якому вперше дав опис придуманої в Індії позиційної десяткової системи числення. На жаль, перський оригінал книги не зберігся. Аль-Хорезмі сформулював правила обчислень в новій системі і, ймовірно, вперше використовував цифру 0 для позначення пропущеної позиції в записі числа (її індійське назва араби переклали як as-sifr або просто sifr, звідси такі слова, як "цифра" і "шифр"). Приблизно в цей же час індійські цифри почали застосовувати і інші арабські вчені. У першій половині XII століття книга аль-Хорезмі в латинському перекладі проникла в Європу. Перекладач, ім'я якого до нас не дійшло, дав їй назву Algoritmi de numero Indorum ("Алгоритми про рахунок індійському"). По-арабськи ж книга іменувалася Кітаб аль-джебр валь-мукабала ("Книга про складання і віднімання"). З оригінального назви книги походить слово Алгебра (алгебра - аль-джебр - складання).

Таким чином, ми бачимо, що латинізоване ім'я середньоазіатського вченого було винесено в заголовок книги, і сьогодні ні в кого немає сумнівів, що слово "алгоритм" потрапило в європейські мови саме завдяки цьому твору. Однак питання про його сенс тривалий час викликав запеклі суперечки. Протягом багатьох століть походженням слова давалися різні пояснення.

Одні виводили algorism з грецьких algiros (хворий) і arithmos (число). З такого пояснення не дуже ясно, чому числа саме "хворі". Або ж лінгвістам хворими здавалися люди, які мають нещастя займатися обчисленнями? Своє пояснення пропонував і енциклопедичний словник Брокгауза і Ефрона. У ньому алгорифм (до речі, до революції використовувалося написання алгоріѳм, через фіту) проводиться "від арабського слова Аль-Горетм, то є корінь". Зрозуміло, ці пояснення навряд чи можна визнати переконливими.

Згаданий вище переклад твору аль-Хорезмі став першою ластівкою, і протягом кількох наступних століть з'явилося безліч інших праць, присвячених все того ж питання - навчання мистецтву рахунку за допомогою цифр. І всі вони в назві мали слово algoritmi або algorismi.

Про аль-Хорезмі пізніші автори нічого не знали, але оскільки перший переклад книги починається словами: "Dixit algorizmi: ..." ("Аль-Хорезмі говорив: ..."), все ще пов'язували це слово з ім'ям конкретної людини. Дуже поширеною була версія про грецький походження книги. В англо-норманської рукописи XIII століття, написаної у віршах, читаємо:

"Алгорізм був придуманий в Греції. Це частина арифметики. Придуманий він був майстром на ім'я Алгорізм, який дав йому своє ім'я. І оскільки його звали Алгорізм, Він назвав свою книгу "Алгорізм".

Близько 1250 англійський астроном і математик Іоанн Сакробоско написав працю з арифметики Algorismus vulgaris, на століття став основним підручником з обчисленням в десяткової позиційної системі числення в багатьох європейських університетах. У вступі Сакробоско назвав автором науки про рахунок мудреця на ім'я Алгус (Algus). А в популярній середньовічної поемі " Роман про Розу "(1275-1280) Жана де Мена "грецький філософ Алгус" ставиться в один ряд з Платоном, Аристотелем, Евклідом і Птолемеєм ! Зустрічався також варіант написання імені Аргус (Argus). І хоча, згідно з давньогрецької міфології, корабель " Арго "був побудований Ясоном, саме цьому Арго приписувалося будівництво корабля.

"Майстер Алгус" (або Аргус) став в середньовічній літературі уособленням рахункового мистецтва. І у вже згадуваній "Романі про троянду", і в відомої італійської поемі "Квітка", написаної Дуранте, є фрагменти, в яких говориться, що навіть "mestre Argus" не зуміє підрахувати, скільки разів сваряться і миряться закохані. Англійський поет Джефрі Чосер в поемі " Книга герцогині "( 1369 р.) пише, що навіть "славний лічильник Аргус" (noble countour Argu) не зможе порахувати чудовиськ, які з'явилися в кошмарних видіннях герою.

Втім, грецька версія була не єдиною. Міфічний алгоритмів (Algor) іменувався то королем Кастилії (Rex quodam Castelliae), то індійським королем, то арабським мудрецем (philosophus Algus nomine Arabicus).

Баронеса Ада Лавлейс, яку вважають першим програмістом.

Проте з часом такі пояснення все менше займали математиків, і слово algorism (або algorismus), незмінно присутнє в назвах математичних творів, знайшло значення способу виконання арифметичних дій за допомогою арабських цифр, тобто на папері, без використання абака. Саме в такому значенні воно увійшло в багато європейські мови. Наприклад, з поміткою "устар." воно присутнє в представницькому словнику англійської мови Webster's New World Dictionary, виданому в 1957 р.

Алгоритм - це мистецтво рахунку за допомогою цифр, але спочатку слово "цифра" відносилося лише до нуля. Знаменитий французький трувери Готьє де Куансі (Gautier de Coincy, 1177-1236) в одному з віршів використовував слова algorismus-cipher (які означали цифру 0) як метафору для характеристики абсолютно нікчемного людини. Очевидно, розуміння такого способу вимагало відповідної підготовки слухачів, а це означає, що нова система числення вже була їм досить добре відома.

Багато століть абак був фактично єдиним засобом для практичних обчислень, ним користувалися і купці, і міняйли, і вчені. Переваги обчислень на лічильної дошці роз'яснював у своїх творах такий видатний мислитель, як Герберт Аврилакского (938-1003), який став у 999 р. папою римським під ім'ям Сильвестра II. Нове з величезними труднощами пробивав собі дорогу, і в історію математики увійшло наполегливе протистояння таборів алгорісміков і абацістов (іноді званих гербекістамі), які пропагували використання для обчислень абака замість арабських цифр. Цікаво, що відомий французький математик Ніколя Шюке (Nicolas Chuquet, 1445-1488) до реєстру платників податків міста Ліона був вписаний як алгорісмік (algoriste). Але пройшло не одне сторіччя, перш ніж новий спосіб рахунку остаточно утвердився, стільки часу потрібно було, щоб виробити загальновизнані позначення, удосконалити і пристосувати до запису на папері методи обчислень. У Західній Європі вчителів арифметики аж до XVII століття продовжували називати "магістрами абака", як, наприклад, математика Нікколо Тарталью (1500-1557).

Отже, твори з мистецтва рахунку називалися Алгоритмами. З багатьох сотень можна виділити і такі незвичайні, як написаний у віршах трактат Carmen de Algorismo (латинське carmen і означає вірші) Олександра де Вілла Деї (Alexander de Villa Dei, розум. 1240) або підручник віденського астронома і математика Георга Пурбаха (Georg Peurbach, 1423-1461) Opus algorismi jocundissimi ("Веселі твір за алгоритмом").

Поступово значення слова розширювалося. Вчені починали застосовувати його не тільки до суто обчислювальних, але і до інших математичних процедур. Наприклад, близько 1360 р. французький філософ Микола Орем (Nicolaus Oresme, 1323/25-1382) написав математичний трактат Algorismus proportionum ("Обчислення пропорцій"), в якому вперше використав ступеня з дробовими показниками і фактично впритул підійшов до ідеї логарифмів. Коли ж на зміну абаку прийшов так званий рахунок на лініях, численні посібники з нього стали називати Algorithmus linealis, тобто правила рахунку на лініях.

Можна звернути увагу на те, що первісна форма algorismi через якийсь час втратила останню букву, і слово набуло більш зручне для європейського вимови вид algorism. Пізніше і воно, в свою чергу, піддалося спотворенню, швидше за все, пов'язаному зі словом arithmetic.

В 1684 Готфрід Лейбніц у творі Nova Methodvs pro maximis et minimis, itemque tangentibus ... вперше використав слово "алгоритм" (Algorithmo) у ще більш широкому сенсі: як систематичний спосіб вирішення проблем диференціального числення.

В XVIII столітті в одному з німецьких математичних словників, Vollstandiges mathematisches Lexicon (виданому в Лейпцигу в 1747 р.), термін algorithmus все ще пояснюється як поняття про чотири арифметичних операціях. Але таке значення не було єдиним, адже термінологія математичної науки в ті часи ще тільки формувалася. Зокрема, вираз algorithmus infinitesimalis застосовувалося до способів виконання дій з нескінченно малими величинами. Користувався словом алгоритм і Леонард Ейлер, одна з робіт якого так і називається - "Використання нового алгоритму для вирішення проблеми Пелля" (De usu novi algorithmi in problemate Pelliano solvendo). Ми бачимо, що розуміння Ейлером алгоритму як синоніма способу вирішення завдання вже дуже близько до сучасного.

Однак знадобилося ще майже два століття, щоб усі старовинні значення слова вийшли з ужитку. Цей процес можна простежити на прикладі проникнення слова "алгоритм" в російську мову.

Історики датують 1691 роком один із списків давньоруського підручника арифметики, відомого як "Рахункова мудрість". Цей твір відоме в багатьох варіантах (найраніші з них майже на сто років старше) і сходить до ще більш стародавніх рукописів XVI ст. За ними можна простежити, як знання арабських цифр і правил дій з ними поступово поширювалося на Русі. Повна назва цього підручника - "Сія книга, глаголемо по гелленських і по грецьки арифметика, а по німецьки алгорізма, а по русски числових лічильна мудрість".

Таким чином, слово "алгоритм" розумілося першими російськими математиками так само, як і в Західній Європі. Однак його не було ні в знаменитому словнику В. І. Даля, ні через сто років у "Тлумачному словнику російської мови" під редакцією Д. Н. Ушакова (1935 р.). Зате слово "алгорифм" можна знайти і в популярному дореволюційному Енциклопедичному словнику братів Гранат, і в першому виданні Великої радянської енциклопедії (Вікіпедія), виданому в 1926 р. І там, і там воно трактується однаково: як правило, за яким виконується та чи інша з чотирьох арифметичних дій у десятковій системі числення. Однак до початку XX ст. для математиків слово "алгоритм" вже означало будь арифметичний або алгебраїчний процес, що виконується за суворо визначеними правилами, і це пояснення також дається в наступних виданнях Вікіпедія.

Алгоритми ставали предметом все більш пильної уваги вчених, і поступово це поняття посіло одне з центральних місць у сучасній математиці. Що ж до людей, від математики далеких, то до початку сорокових років це слово вони могли почути хіба що під час навчання в школі, в поєднанні "алгоритм Евкліда". Незважаючи на це, алгоритм все ще сприймався як термін суто спеціальний, що підтверджується відсутністю відповідних статей в менш об'ємних виданнях. Зокрема, його немає навіть в десятитомної Малої радянської енциклопедії (1957 р.), не кажучи вже про однотомний енциклопедичних словниках. Але зате через десять років, у третьому виданні Великій радянській енциклопедії (1969 р.) алгоритм вже характеризується як одна з основних категорій математики, "не володіють формальним визначенням у термінах більш простих понять, і абстрагіруемих безпосередньо з досвіду". Як ми бачимо, відмінність навіть від трактування першому виданні Вікіпедія разюча! За сорок років алгоритм перетворився в одне з ключових понять математики, і визнанням цього стало включення слова вже не в енциклопедії, а в словники. Наприклад, воно присутнє в академічному "Словнику російської мови" (1981 р.) саме як термін з області математики.

Одночасно з розвитком поняття алгоритму поступово відбувалася і його експансія з чистої математики в інші сфери. І початок їй поклала поява комп'ютерів, завдяки якому слово "алгоритм" увійшло в 1985 р. в усі шкільні підручники інформатики і знайшло нове життя. Взагалі можна сказати, що його сьогоднішня популярність напряму пов'язана зі ступенем поширення комп'ютерів. Наприклад, у третьому томі "Дитячої енциклопедії" (1959 р.) про обчислювальних машинах говориться чимало, але вони ще не стали чимось звичним і сприймаються скоріше як певний атрибут світлого, але досить далекого майбутнього. Відповідно і алгоритми жодного разу не згадуються на її сторінках. Але вже на початку 70-х рр.. минулого століття, коли комп'ютери перестали бути екзотичною дивиною, слово "алгоритм" стрімко входить в ужиток. Це чутливо фіксують енциклопедичні видання. В " Енциклопедії кібернетики "(1974 р.) у статті" Алгоритм "він вже пов'язується з реалізацією на обчислювальних машинах, а в" Радянській військовій енциклопедії "(1976 р.) навіть з'являється окрема стаття" Алгоритм розв'язання задачі на ЕОМ ". За останні півтора- два десятиліття комп'ютер став невід'ємним атрибутом нашого життя, комп'ютерна лексика стає все більш звичною. Слово "алгоритм" в наші дні відомо, ймовірно, кожному. Воно впевнено зробило крок навіть в розмовну мову, і сьогодні ми нерідко зустрічаємо в газетах і чуємо у виступах політиків вираження кшталт "алгоритм поведінки", "алгоритм успіху" або навіть "алгоритм зради". Академік Н. Н. Моїсеєв назвав свою книгу "Алгоритми розвитку", а відомий лікар Н. М. Амосов - "Алгоритм здоров'я" і "Алгоритми розуму". А це означає, що слово живе, збагачуючись все новими значеннями і смисловими відтінками.


2. Визначення алгоритму

2.1. Неформальне визначення

Кожен алгоритм передбачає існування початкових (вхідних) даних і в результаті роботи призводить до отримання певного результату. Робота кожного алгоритму відбувається шляхом виконання послідовності деяких елементарних дій. Ці дії називають кроками, а процес їх виконання називають алгоритмічним процесом. Таким чином виявляється властивість дискретності алгоритму [3].

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

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

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


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

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

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


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

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

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

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

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

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


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

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

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

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

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

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

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


2.2.3. Нормальний алгоритм Маркова

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

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

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

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

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


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

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

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

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

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

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

2.4. Інші формалізації

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

  • багатострічковій і недетерміновані машини Тьюринга;
  • регістрова і РАМ машина - прототип сучасних комп'ютерів і віртуальних машин;
  • кінцеві і клітинні автомати

та інші.


3. Формальні властивості алгоритмів

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

  • Дискретність - алгоритм повинен представляти процес вирішення завдання як послідовне виконання деяких простих кроків. При цьому для виконання кожного кроку алгоритму потрібно кінцевий відрізок часу, тобто перетворення вихідних даних у результат здійснюється в часі дискретно.
  • Детермінованість (визначеність). У кожен момент часу наступний крок роботи однозначно визначається станом системи. Таким чином, алгоритм видає один і той же результат (відповідь) для одних і тих самих вихідних даних. У сучасному трактуванні в різних реалізацій одного і того ж алгоритму повинен бути ізоморфний граф. З іншого боку, існують імовірнісні алгоритми, в яких наступний крок роботи залежить від поточного стану системи і генерується випадкового числа. Однак при включенні методу генерації випадкових чисел в список "вихідних даних", імовірнісний алгоритм стає підвидом звичайного.
  • Зрозумілість - алгоритм для виконавця повинен включати тільки ті команди, які йому (виконавцю) доступні, які входять в його систему команд.
  • Завершаемості (кінцівка) - при коректно заданих вихідних даних алгоритм повинен завершувати роботу і видавати результат за кінцеве число кроків. З іншого боку, імовірнісний алгоритм то й ніколи не видати результат, але ймовірність цього дорівнює 0.
  • Масовість (універсальність). Алгоритм має бути застосовний до різних наборів вихідних даних.
  • Результативність - завершення алгоритму певними результатів.
  • Алгоритм містить помилки, якщо призводить до одержання неправильних результатів або не дає результатів зовсім.
  • Алгоритм не містить помилок, якщо він дає правильні результати для будь-яких допустимих вихідних даних.

4. Види алгоритмів

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

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


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

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

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

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


6. Алгоритмічно нерозв'язні завдання

Формалізація поняття алгоритму дозволила досліджувати існування задач, для яких не існує алгоритмів пошуку рішень. Згодом була доведена неможливість алгоритмічного обчислення рішень ряду задач, що робить неможливим їх вирішення на будь-якому обчислювальному пристрої. Функцію f називають обчислюється ( англ. computable ), Якщо існує машина Тьюринга, яка обчислює значення f для всіх елементів множини визначення функції. Якщо такої машини не існує, функція f називають невичісляемой. Функція буде вважатися невичісляемой, навіть якщо існують машини Тьюринга, здатні обчислити значення для підмножини зі всієї безлічі вхідних даних [13].

Випадок, коли результатом обчислення функції f є логічне вираз "істина" або "брехня" (або безліч {0, 1}), називають завданням, яке може бути розв'язуваної або нездійсненним в залежності від вичісляемості функції f [13].

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

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

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

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


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

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

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

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

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

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

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

P { Q } R

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

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


7.2. Час роботи

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

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

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

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

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

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

Грубо говоря, анализ средней асимптотической временной сложности можно разделить на два типа: аналитический и статистический. Аналитический метод дает более точные результаты, но сложен в использовании на практике. Зато статистический метод позволяет быстрее осуществлять анализ сложных задач [20].

В следующей таблице приведены распространенные асимптотические сложности с комментариями [21].


Сложность Коментар Приклади
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 -кратному увеличению необходимого времени; удвоение размера задачи увеличивает необходимое время в квадрат Некоторые задачи коммивояжёра, алгоритмы поиска полным перебором

8. Наличие исходных данных и некоторого результата

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

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

Для разработки алгоритмов и программ используется алгоритмизация - процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально важны детерминированность, результативность и массовость, а также правильность результатов решения поставленных задач.

Алгоритм - это понятное и точное предписание, исполнительно совершить последовательность действий, направленных на достижение цели.


9. Представление алгоритмов

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

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

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


10. Эффективность алгоритмов

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

Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики. В 50-х гг. XX века появилась даже отдельная её область - быстрые алгоритмы. В частности, в известной всем с детства задаче об умножении десятичных чисел обнаружился ряд алгоритмов, позволяющих существенно (в асимптотическом смысле) ускорить нахождение произведения. См. быстрое умножение

Ярким примером является алгоритм Чудновского для вычисления числа π .


11. Приклад

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

Алгоритм Евклида - эффективный метод вычисления наибольшего общего делителя (НОД). Назван в честь греческого математика Евклида; один из древнейших алгоритмов, который используют до сих пор [22].

Описан в "Началах" Евклида (примерно 300 до н. э.), а именно в книгах VII и X. В седьмой книге описан алгоритм для целых чисел, а в десятой - для длин отрезков.

Существует несколько вариантов алгоритма, ниже записанный в псевдокоде рекурсивный вариант:

 функция нсд(a, b) если b = 0 возврат a иначе возврат нод(b, a mod b) 


Иллюстрация выполнения алгоритма Евклида для вычисления НОД чисел 1599 и 650.

НОД чисел 1599 и 650:

Крок 1 1599 = 650*2 + 299
Шаг 2 650 = 299*2 + 52
Шаг 3 299 = 52*5 + 39
Шаг 4 52 = 39*1 + 13
Шаг 5 39 = 13*3 + 0



Примітки

  1. Kleene 1943 in Davis 1965:274
  2. Rosser 1939 in Davis 1965:225
  3. (Игошин, с. 314)
  4. (Игошин, с. 317)
  5. Basics: The Turing Machine (with an interpreter! - scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php. Good Math, Bad Math (9 февраля 2007).
  6. (Игошин, раздел 33)
  7. Энциклопедия кибернетики, т. 2, c. 90-91.
  8. (Игошин, раздел 34)
  9. 1 2 "Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time." Henri Cohen A Course in Computational Algebraic Number Theory - Springer-Verlag, 1996. - P. 2. - ISBN 3-540-55640-0.
  10. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein. - ISBN 0-262-03293-7.
  11. (Розділ 12, с. 12-22 в Atallah, 2010)
  12. (Ігошин, розділ 36)
  13. 1 2 3 Peter Linz An Introduction to Formal Languages ​​and Automata - Jones and Bartlett Publishers, 2000. - ISBN 0-7637-1422-4.
  14. "Computability and complexity", Encyclopedia of computer Science and Technology, Facts On File, 2009, ISBN 978-0-8160-6382-6
  15. (O'Regan, розділ 4.5)
  16. (Розділ 5.3.6 в Enders, 2003)
  17. (Розділ 5.3.7 в Enders, 2003)
  18. (O'Regan, с. 119)
  19. А. Ахо, Дж. Хопкрофта, Дж. Ульман Побудова та аналіз обчислювальних алгоритмів = The Design and Analysis of Computer Algorithms - "Світ", 1979.
  20. (Розділ 11 в Atallah, 2010)
  21. (Розділ 1 в Atallah, 2010)
  22. Knuth D The Art Of Computer Programming, Volume 2: Seminumerical Algorithms - 3rd. - Addison-Wesley, 1997. - ISBN 0201896842.

Література

  • Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Ривест, Кліффорд Штайн Алгоритми: побудова й аналіз = INTRODUCTION TO ALGORITHMS - 2-е вид. - М .: "Вільямс", 2006. - С. 1296. - ISBN 0-07-013151-1.
  • Дональд Кнут Мистецтво програмування, том 1. Основні алгоритми = The Art of Computer Programming, vol.1. Fundamental Algorithms - 3-е изд. - М .: "Вільямс", 2006. - С. 720. - ISBN 0-201-89683-4.
  • Порубльов Ілля Миколайович, Ставровський Андрій Борисович Алгоритми і програми. Рішення олімпіадних завдань - М .: "Вільямс", 2007. - С. 480. - ISBN 978-5-8459-1244-2.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
EM-алгоритм
Алгоритм Ву
Алгоритм Apriori
Алгоритм де Кастельжо
Алгоритм Брезенхема
Алгоритм Шора
Детермінований алгоритм
Rainbow (алгоритм)
Адаптивний алгоритм
© Усі права захищені
написати до нас
Рейтинг@Mail.ru