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

У статті ми розберемо основні поняття алгоритму.

Історія появи алгоритмів

Алгоритм - поняття, що з'явилися у XII столітті. Саме слово "алгоритм" походить від латинської інтерпретації імені відомого математика середнього сходу Мухаммеда аль Хорезмі, який написав книгу "Про індійський рахунок". У цій книзі описано, як правильно записувати натуральні числа, використовуючи арабські цифри, та наведено опис алгоритму дій стовпчиком над такими числами.

У XII столітті книга "Про індійський рахунок" була перекладена на Латинська мова, тоді і з'явилося дане визначення.

Взаємодія алгоритму з людиною та машиною

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

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

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

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

Що таке алгоритм?

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

Який із способів буде використаний, залежить від кількох факторів: від складності задачі, від того, наскільки необхідно деталізувати процес розв'язання задачі тощо.

Графічний варіант побудови алгоритму

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

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

Також блок-схеми зображуються відповідно до ГОСТ-19701-90 та ГОСТ-19.003-80.
Графічні фігури, що застосовуються в алгоритмі, поділяються на:

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

Допоміжні.Допоміжні зображення потрібні для позначення окремих, не найважливіших елементів вирішення задачі.

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

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

У правильної схеми алгоритму не повинно бути більше одного виходу з обробних блоків і менше двох виходів з блоків, що відповідають за перевірку виконання умов.

Як правильно побудувати алгоритм?

Структура алгоритму, як було сказано вище, повинна будуватися за ГОСТом, інакше вона не буде зрозуміла і доступна оточуючим.

Загальна методика запису включає наступні пункти:

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

У кожного алгоритму мають бути чітко позначені початок та кінець.

У алгоритмів мають бути чітко та ясно описані всі дані, як вхідні, так і вихідні.

При складанні алгоритму слід зазначити дії, які дозволять виконувати необхідні завдання завдання над вибраними даними. Зразковий вид алгоритму:

• Назва схеми.
• Дані
• Початок.
• Команди.
• Кінець.

Правильне побудова схеми значно полегшить обчислення алгоритмів.

Геометричні фігури, що відповідають за різні дії в алгоритмі

Горизонтально розташований овал – початок та кінець (знак завершення).

Горизонтально розташований прямокутник – обчислення чи інші дії (знак процесу).

Горизонтально розташований паралелограм - введення або виведення (знак даних).

Горизонтально розташований ромб – перевірка умови (знак рішення).

Витягнутий, горизонтально розташований шестикутник – модифікація (знак підготовки).

Моделі алгоритмів представлені нижче малюнку.

Формульно-словесний варіант побудови алгоритму.

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

Поняття алгоритму інформатики

У комп'ютерній сфері все ґрунтується на алгоритмах. Без чітких вказівок, введених у вигляді спеціального коду, не працюватиме жодна техніка чи програма. На уроках інформатики учням намагаються дати основні поняття алгоритмів, навчити користуватися ними та самостійно їх створювати.

Створення та використання алгоритмів в інформатиці - процес творчіший, ніж, наприклад, виконання вказівок до вирішення задачі в математиці.

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

З іншого боку, будь-яка програма – алгоритм. Але якщо алгоритм несе лише дії, які потрібно виконувати, вставляючи свої дані, то програма вже несе в собі готові дані. Ще одна відмінність - це те, що програма може бути запатентована і бути приватною власністю, а алгоритм ні. Алгоритм - поняття більш широке, ніж програма.

Висновок

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Машина Тюрінга

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

та інші.

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

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

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

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

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

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

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

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

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

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

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

За гіпотезою Річарда Мейса, «уникнення помилок краще усунення помилок». Відповідно до гіпотези Хоара, «доказ програм вирішує проблему коректності, документації та сумісності». Доказ коректності програм дозволяє виявляти їх властивості по відношенню до всього діапазону вхідних даних. Для цього поняття коректності було поділено на два типи:

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

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

P{Q} R

де P- це передумова, що має виконуватися перед запуском програми Q, а R- Постумова, правильна після завершення роботи програми.

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

Час роботи

Поширеним критерієм оцінки алгоритмів є час роботи та порядок зростання тривалості роботи залежно від обсягу вхідних даних.

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

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

Саме асимптотична складність визначає розмір завдань, які алгоритм здатний опрацювати. Наприклад, якщо алгоритм обробляє вхідні дані розміром за час cn², де c- деяка константа , то кажуть, що тимчасова складність такого алгоритму O(n²).

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

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

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

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

Наявність вихідних даних та деякого результату

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

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

Для розробки алгоритмів та програм використовується алгоритмізація- процес систематичного складання алгоритмів на вирішення поставлених прикладних завдань. Алгоритмізація вважається обов'язковим етапом у процесі розробки програм та вирішення завдань на ЕОМ. Саме для прикладних алгоритмів та програм принципово важливі детермінованість, результативність та масовість, а також правильність результатів вирішення поставлених завдань.

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

Подання алгоритмів

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

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

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

Ефективність алгоритмів

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

Для кожного завдання може існувати безліч алгоритмів, що призводять до мети. Збільшення ефективності алгоритмів становить одне із завдань сучасної інформатики. У 50-х роках. XX століття з'явилася навіть окрема її область - швидкі алгоритми. Зокрема, у відомому всім з дитинства задачі про множення десяткових чисел виявилася низка алгоритмів, що дозволяють суттєво (в асимптотичному сенсі) прискорити знаходження твору. швидке множення

Алгоритм Евкліда - ефективний методобчислення найбільшого загального дільника (НДД). Названо на честь грецького математика Евкліда; один із найдавніших алгоритмів, який використовують досі.

Описаний у «Початках» Евкліда (приблизно 300 е.), саме у книгах VII і X. У сьомий книзі описаний алгоритм для цілих чисел, а десятої - для довжин відрізків.

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

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

НОД чисел 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. (Ігошин, с. 317)
4. Basics: The Turing Machine (with an interpreter!). Good Math, Bad Math(9 лютого 2007 року). Архівовано з першоджерела 2 лютого 2012 року.
5. (Ігошин, розділ 33)
6. Енциклопедія кібернетики, т.е. 2 , с. 90-91.
7. (Ігошин, розділ 34)
8. «Probabilistic algorithms не може бути mistaken with methods (яких я маю на call algorithms), які викликає результат, який має високу probability of being correct. Це є важливим, що в будь-яких algoritms produces correct results (discounting human or computer errors), even if this happens after a long time.» Henri Cohen A Course in Computational Algebraic Number Theory. - Springer-Verlag, 1996. - P. 2. - ISBN 3-540-55640-0
9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives"t, Clifford Stein. - ISBN 0-262-03293-7
10. (Розділ 12, с. 12-22 в Atallah, 2010)
11. (Ігошин, розділ 36)
12. Peter Linz An Introduction to Formal Languages ​​and Automata. - Jones and Bartlett Publishers, 2000. - ISBN 0-7637-1422-4
13. "Computability and complexity", Encyclopedia of computer Science and Technology, Facts On File, 2009,

Зрозумілість - алгоритм повинен складатися з команд, "зрозумілих" виконавцю (що входять до системи команд виконавця).

Дискретність (перервність, роздільність) - алгоритм повинен представляти процес вирішення задачі як послідовне виконання простих (або раніше визначених) кроків.

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

Результативність (або кінцівка)- алгоритм повинен призводити до вирішення завдання (або відповіді, що рішення немає) за кінцеве число кроків.

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

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

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

Ці дії називаються допустимими діями виконавця. Тільки їх можна використовувати.

Виконавець обчислювальних алгоритмів називається обчислювачем. Обчислювач може мати справу з числами та змінними, що позначають числа. Отже, алгоритм - це організована послідовність дій, допустимих деякого виконавця. Один і той самий виконавець може бути симітований на ЕОМ багатьма способами.

Складність алгоритму

Складність алгоритму дозволяє оцінити, наскільки швидко зростає трудомісткість алгоритму зі збільшенням обсягу вхідних даних. Під трудомісткістю розуміється кількість елементарних операцій, які потрібно виконати на вирішення завдання з допомогою даного алгоритму. Зазвичай оцінка складності алгоритму представляється як O(f(N)), де O – функція складності, а N – число оброблюваних спостережень чи прикладів. Найменш витратними є алгоритми, котрим функція складності має вигляд f(N)=C і f(N)=C*N, де С – константа. У першому випадку обчислювальні витрати не залежать від кількості оброблюваних даних, а в другому – лінійно зростають. Найбільш витратними є алгоритми, складність яких має статечну і факторіальну залежність від кількості спостережень, що обробляються.

СОРТУВАННЯ

Сортування є процес упорядкування безлічі подібних інформаційних об'єктів у порядку зростання або зменшення їх значень. Наприклад, список i з n елементів буде відсортовано у порядку зростання значень елементів, якщо i<= i <= ... <= i.

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

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

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

МЕТОДИ ПОШУКУ

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

Елементи теорії алгоритмів

Алгоритм - поняття, що стосується фундаментальних основ інформатики. Воно виникло задовго до появи комп'ютерів і одна із основних понять математики.

Слово «алгоритм» походить від імені видатного середньовічного вченого Мухамеда ібн Муса Ал-Хорезмі(IX століття н.е.), скорочено Ал-Хорезмі. У латинському перекладі однієї з праць Ал-Хорезмі правила виконання дій починалися словами DIXIT ALGORIZMI (Алгоризм сказав), в інших латинських перекладах автор іменувався ALGORITHMUS (Алгорітмус).

Поняття «алгоритм» немає чіткого, однозначного визначення у математичному значенні. Можна дати лише опис (Пояснення) цього поняття. Для пояснення поняття «алгоритм» велике значення має визначення поняття "виконавець алгоритму" . Алгоритм формулюється для конкретного виконавця.

Алгоритм - Посібник до дії для виконавця, тому значення слова "алгоритм" близьке за змістом до значення слів "вказівка" або "припис".

Алгоритм - зрозуміле та точне припис(вказівка) виконавцю вчинити певну послідовність дій задля досягнення зазначеної мети або вирішення поставленого завдання.

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

Зрозуміло, що сказане перестав бути визначенням у математичному сенсі, лише відображає інтуїтивне розуміння алгоритму (в математиці немає поняття «припис», неясно, яка має бути точність, що таке «зрозумілість» тощо.).

Основні властивості алгоритму

Масовість.

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

Зрозумілість.

Щоб алгоритм можна було виконати, він має бути зрозумілим виконавцю. Зрозумілість алгоритму означає знання виконавця у тому, що треба робити виконання цього алгоритму.

Дискретність.

Алгоритм представляється як кінцевої послідовності кроків (алгоритм має дискретну структуру) та її виконання розчленовується виконання окремих кроків (виконання чергового кроку починається після завершення попереднього).

Кінцівка.

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

Визначеність.

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

Ефективність.

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

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

Побудова такого формального визначення розпочато з формалізації об'єктів (операндів) алгоритму, оскільки у інтуїтивному понятті алгоритму його об'єкти можуть мати довільну природу. Ними можуть бути, наприклад, числа, показання датчиків, що фіксують параметри виробничого процесу, шахові фігури та позиції тощо. Однак припускаючи, що алгоритм має справу не з реальними об'єктами, а з їх зображеннями, можна вважати, що операнди алгоритму - Слова у довільному алфавіті. Тоді виходить, що алгоритм перетворює слова у довільному алфавіті на слова того ж алфавіту. Подальша формалізація поняття алгоритму пов'язана з формалізацією дій над операндами та порядку цих дій. Одна з таких формалізації була запропонована в 1936 англійським математиком А. Тьюрингом, який формально описав конструкцію деякої абстрактної машини ( машини Тьюринга ) як виконавця алгоритму і висловив основну тезу про те, що будь-який алгоритм може бути реалізований відповідною машиною Тьюринга. Приблизно в цей же час американським математиком Е.Постом було запропоновано іншу алгоритмічну схему. машина Поста , а 1954 року радянським математиком А.А.Марковим була розроблена теорія класів алгоритмів, названих їм нормальними алгоритмами , і висловлено основну тезу у тому, що кожен алгоритм нормалізуємо.

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

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

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

Поняття алгоритму

Поняття алгоритму є центральним поняттям інформатики. Слово «алгоритм» походить від імені узбецького математика аль-Хорезмі, який ще в ІХ столітті сформулював правила виконання арифметичних дій. У сучасній математиці та інформатиці термін алгоритм має такі визначення:

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

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

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

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

У інформатиці універсальним виконавцем алгоритмів є комп'ютер.

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

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

Алгоритми залежно від мети, початкових умов завдання, шляхів її вирішення, визначення дій виконавця поділяються так:

• Ймовірнісний (стохастичний) алгоритмдає програму розв'язання задачі кількома шляхами чи способами, що призводять до можливого досягнення результату.
• Евристичний алгоритм(Від грецького слова «еврика») - це такий алгоритм, в якому досягнення кінцевого результату програми дій однозначно не зумовлено, так само як не позначено всю послідовність дій, не виявлено всі дії виконавця. До евристичних алгоритмів відносять, наприклад, інструкції та розпорядження. У цих алгоритмах використовуються універсальні логічні процедури та способи прийняття рішень, засновані на аналогіях, асоціаціях та минулому досвіді вирішення подібних завдань.
• Лінійний алгоритм- Набір команд (вказівок), що виконуються послідовно один за одним.
• Розгалужуваний алгоритм- Алгоритм, що містить хоча б одну умову, в результаті перевірки якого ЕОМ забезпечує перехід на один з двох можливих кроків.
• Циклічний алгоритм- алгоритм, що передбачає багаторазове повторення однієї й тієї ж дії (одних і тих самих операцій) Над новими вихідними даними. До циклічних алгоритмів зводиться більшість методів обчислень, перебору варіантів. Цикл програми – послідовність команд (серія, тіло циклу), яка може виконуватися багаторазово (для нових вихідних даних) до задоволення певної умови.
• Допоміжний (підлеглий) алгоритм (процедура)- Алгоритм, раніше розроблений і повністю використовуваний при алгоритмізації конкретної задачі. У деяких випадках, за наявності однакових послідовностей вказівок (команд) для різних даних з метою скорочення запису, також виділяють допоміжний алгоритм.

Алгоритм можна задати декількома способами:

• - словесним, тобто записом послідовності дій природною мовою;
• - графічним, За допомогою спеціальних графічних символів;
• - формульним, тобто за допомогою математичних формул, що визначають порядок обчислень;
• - табличним, та вигляді таблиці, в якій фіксуються етапи виконання алгоритму та результати виконання.

Блок-схема алгоритму

Завдання алгоритмів за допомогою блок-схем виявилося дуже зручним засобом зображення алгоритмів і набуло широкого поширення.

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

У таблиці наведені найчастіше вживані символи.

Символи блок-схеми
Назва символу	Позначення та приклад заповнення	Пояснення
Процес		Обчислювальна дія чи послідовність дій
Рішення		Перевірка умов
Модифікація		Початок циклу
Зумовлений процес		Обчислення за підпрограмою, стандартною підпрограмою
Ввід вивід		Введення-виведення у загальному вигляді
Пуск-зупинка		Початок, кінець алгоритму, вхід та вихід у підпрограму
Документ		Виведення результатів

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

Блок « Рішення» використовується для позначення переходів керування за умовою. У кожному блоці «рішення» мають бути зазначені питання, умова чи порівняння, що він визначає.

Блок « модифікаціявикористовується для організації циклічних конструкцій. (Слово «модифікація» означає «видозміну, перетворення»). Всередині блоку записується параметр циклу, для якого вказуються початкове значення, гранична умова і крок зміни значення параметра для кожного повторення.

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

Для прикладу наведемо блок-схеми алгоритму знаходження максимального із двох значень:

Правила побудови алгоритму

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

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

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

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

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

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

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

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

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

Результативність(Кінцівка) - алгоритм повинен призводити до вирішення задачі за кінцеве число кроків.

Масовість- алгоритм розв'язання задачі розробляється у загальному вигляді, тобто він має бути застосовним для деякого класу задач, що відрізняються лише вихідними даними. При цьому вихідні дані можуть вибиратися з деякої області, яка називається областю застосування алгоритму.