алгоритми

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

Виконавець алгоритму – жива чи нежива істота, яка спроможна виконати алгоритм.

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

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

Масовість

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

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

кожна команда алгоритму визначаються і тлумачиться однозначно.

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

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

Результативність

кожна дія приводить до певного результату.

Формальність

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

Скінченність

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

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

Використовуючи дані блоки, можна подати, наприклад, алгоритм чищення картоплі в такому вигляді:

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

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

Поняття алгоритму формувалося з найдавніших часів і до тридцятих років  ХХ ст., у науковому колі склалось інтуїтивне уявлення про цей об’єкт.         Одним із найдавніших алгоритмів,  у його інтуїтивному розумінні, як скінченної послідовності елементарних дій, що вирішують поставлене завдання, вважається алгоритм знаходження найбільшого спільного дільника двох чисел (алгоритм Евкліда). Відзначимо, що протягом тривалого часу, аж до початку XX століття, термін “алгоритм“ вживався лише в стійкому сполученні “алгоритм Евкліда“, хоча історично встановлено, що задовго до Евкліда цей алгоритм був уже відомий, наприклад, Аристотелю. Змістовні явища, що привели до утворення поняття “алгоритм“, простежуються в математиці впродовж усього часу її існування. Саме слово “алгоритм“, як стверджують історики та математики, з’явилося декілька століть тому й означало не термін, а ім’я. Узбецький математик Аль–Хорезмі, вчений, якому математика й людство зобов’язані багатьма відкриттями, був відомий європейським математикам у латинській транскрипції як Алгоризмі. А повне його ім’я – Абу Абдулла Абу Джафар Мухаммад ібн Муса аль-Хорезмі (близько 780 р. — близько 850 р. ) – у перекладі буквально – батько Абдулли, Мухаммед, син Муси, уродженець Хорезмі. Його книга – “Хисаб аль-джабр у аль-мукабаля“ . Саме із трактату Аль-Хорезмі з арифметики почалося знайомство Європи з алгоритмами – строгими процедурами для виконання арифметичних операцій. Тобто алгоритм, точніше алгоризм, розуміли як керівництво для вирішення завдань.

Подальший розвиток математики затвердив ту думку, що вирішення будь-якої проблеми повинне бути алгоритмічним. Р. Декарт, Г. Ф. Лейбніц,

Д. Гільберт стимулювали алгоритмічні дослідження. В 1900 на Другому міжнародному конгресі математиків (Париж) Давид Гільберт сформулював 23 важливі математичні проблеми, знаходження алгоритму розв’язування яких, на його думку, сприяло б подальшому розвитку математики.

Саме в ті часи були поширені дві точки зору :

1.    Усі проблеми є алгоритмічно розв’язними. Просто ще не існують знання для побудови алгоритму.

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

Для доведення не існування алгоритму потрібно було мати його точне математичне визначення, тому  після сформування поняття алгоритму як нової та окремої сутності першочерговою постала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. Формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції. Вперше алгоритм як термін з’явився у працях Е. Бореля (1912) та Г. Вейля (1921).

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

Перші фундаментальні праці з теорії алгоритмів були опубліковані незалежно в 1935-37 роках А. Тюрінгом, А. Черчем, С. Кліні, К. Гьоделем і

Е. Постом.

Запропоновані ними машина Тюрінга, машина Поста, частково рекурсивні функції й лямбда-вирахування Черча були еквівалентними формалізмами алгоритму. Сформульовані ними тези (Поста й Черча-Тюрінга) постулювали еквівалентність запропонованих ними формальних систем та інтуїтивного поняття алгоритму. Важливим розвитком цих праць стало формулювання й доведення алгоритмічно нерозв’язних проблем. У 1950-ті – роки істотний внесок у теорію алгоритмів зробили праці

А. М. Колмогорова та А. А. Маркова (молодшого), а в 1970-х роках у теорії алгоритмів плідно працював Ю. В. Матіясевич, зокрема над розв’язанням проблем Гільберта.

Запропоноване А. Марковим поняття “нормального алгоритму“ є величезним внеском у світову науку, а А. Колмогорову належить пріоритет у визначенні загального поняття алгоритму та  створення теорії складності конструктивних об’єктів.

У 1960-70-ті роки сформулювалися такі напрямки в теорії алгоритмів:

•  Класична теорія алгоритмів (викладення завдання у термінах формальних мов, поняття задачі вирішення, введення класів складності, формулювання в 1965 році Едмондсом проблеми P=NP, відкриття класу NP-повних задач і його дослідження)[1].
•  Теорія асимптотичного аналізу алгоритмів (поняття складності й трудомісткості алгоритму, критерії оцінки алгоритмів, методи одержання асимптотичних оцінок, зокрема для рекурсивних алгоритмів, асимптотичний аналіз трудомісткості або часу виконання), у розвиток якої зробили істотний внесок Кнут, Ахо, Хопкрофт, Ульман [2,4].
• Теорія практичного аналізу обчислювальних алгоритмів (одержання явних функцій трудомісткості,  практичні критерії якості алгоритмів, методика вибору раціональних алгоритмів), основними роботами в цьому напрямку, мабуть, потрібно вважати фундаментальні праці [1,2].
• 

ЯК ЦЕ ПРАЦЮЄ НА ПРАКТИЦІ?

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

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

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