D01.2. History of algorithms

[AndriyBosik]

D01.2. History of algorithms D01.2. Історія алгоритмів

[AndriyBosik]

This was discussed during the lecture:

• There always have been
• From the first computer program
• Implicitly solved problems
• Struggle for survival ☺
• Algorithm for building fire
• Agriculture, hunting, transport (from point A to point B)
• Algorithms in animals
• Binary code
• Mathematics, began to describe algorithms
• From the first computers
• 1944, Turing, enigma
• People began to think
• Light a fire
• How to kill a mammoth (pictures on the walls)
• DNA - encodes the entire system (biological)
• When mathematics was invented (Aristotle, the ancient Greeks)

Це було обговорено під час лекції:

• Завжди були
• З першої комп’ютерної програми
• Неявно вирішували задачі
• Боротьба за виживання ☺
• Алгоритм побудову вогню
• Сільське господарство, полювання, транспорт (з
• точки А в точку В)
• Алгоритми у тварин
• Двійковий код
• Математика, почали описувати алгоритми
• З перших ЕОМ
• 1944, Тьюрінг, енігма
• Люди почали думати
• Розпалити вогонь
• Як вбити мамонта (малюнки на стінах)
• ДНК – кодує всю систему (біологічну)
• Коли придумали математику (Арістотель, давні греки)

[AlyonaHaiova]

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

[AlyonaHaiova]

У 1843 році Ада Лавлейс описала алгоритм обчислення чисел Бернуллі на аналітичній машині Беббіджа. Цей алгоритм визнано першою програмою, спеціально реалізованою, щоб виконуватися на ЕОМ, і через це його розробницю вважають першим програмістом

[khilchuk-ol]

Посилання на досить цікаву статтю про деякі події історії розвитку теорії алгоритмів: https://www.digit.in/features/science-and-technology/the-origin-of-algorithms-30045.html

Хочеться виділити ось цей фрагмент:

... the establishment of Stephen Kleene’s ‘Algorithmic Theory’ in 1943. Kleene stated, “ In setting up a complete algorithmic theory, what we do is to describe a procedure, performable for each set of values of the independent variables, which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, "yes" or "no," to the question, "is the predicate value true?””

Kleene’s theory set up the rule that algorithms of today follow - independent, self-sustaining computational functions that would execute operations within a finite set of instructions. This made computing faster, and with the advent of personal computers from late 1960s, algorithms have seen improvements.

[Edward3635]

Вперше поняття алгоритму з'явилося в працях Е. Бореля (1912) та Г. Вейля (1921).

Першими формальними моделями алгоритмічно обчислюваних функцій були λ-означувані функції (Алонзо Черч, 1932) та загальнорекурсивні функції (Курт Гедель, 1934). Вказані класи визначались як функції, графіки яких породжуються відповідно численням λ-конверсій та численням Ербрана-Геделя. В 1936 році Стівен Коул Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, ввівши поняття частково рекурсивної функції, та описав клас таких функцій в чисто функціональних термінах. В 1943 році Еміль Пост запропонував модель обчислюваних функцій на основі введеного ним числення спеціального вигляду (канонічних систем).

Для формалізації самого поняття алгоритму були запропоновані точні математичні описи алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини була машина Тюрінга (Алан Тюрінг, Еміль Пост, 1936). Із пізніших моделей відзначимо нормальні алгоритми (А. Марков, 1952) та регістрові машини (Д. Шепердсон, Г. Стерджіс, 1963).

[ZinchenkoArtem1]

Algorithms have a long history and the word can be traced back to the 9th century. At this time the Persian scientist, astronomer and mathematician Abdullah Muhammad bin Musa al-Khwarizmi, often cited as “The father of Algebra”, was indirect responsible for the creation of the term “Algorithm”. (source) http://cs-exhibitions.uni-klu.ac.at/index.php?id=193#:~:text=Algorithms%20have%20a%20long%20history,of%20the%20term%20%E2%80%9CAlgorithm%E2%80%9D.

[YevgeniyBukur]

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

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

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

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