Основи алгоритмізації

Зміст

1. Поняття алгоритму. Історична довідка

2. Формалізація рішення задачі. Машина Тьюринга

3. Історія розвитку ЕОМ.

4. Архітектура сучасних ПК.

• Структурна схема ПК

• Загальні принципи роботи комп’ютера

• Позиційні системи числення

5. Графічне відображення алгоритмів за правилами ГОСТ 19.701-90 (ISO 5807-85). Приклад.

6. Загальні принципи програмування

   • Вимоги до професії

   • Мови програмування та програмне середовище

   • Структура програмних комплексів

   • Структура програми

   • Технологія програмування на МВР та налагодження програм

   • Техніка обчислень

   • Типи обчислювальних процесів

   • Цикли в обчислювальному процесі

   • Загальна структура прикладної програми

7. Сучасні таблиці кодування символів

• ASCII-таблиця

Поняття алгоритму. Історична довідка

Алгоритм (від імені перського математика, 9 ст. аль-Хорезмі, Algorithmi)- послідовність правил виконання обчислювального процесу, що приводить до рішення певного класу задач після кінцевого числа операцій. При написанні програм алгоритм задає логічну послідовність операцій. Для візуального відображення алгоритмів використовують блок-схеми, що оформлюються згідно з ГОСТ 19.701-90 (ISO 5807-85).

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

У 825 р.н.е. аль_Хорезмі написав трактат, де розглянув винайдену в Індії позиційну десяткову систему числення і вивів правила підрахунків в позиційних системах. У 12 столітті перекладена на латину книга потрапила до Європи під назвою “Algorithmi de numero Indorum”. Невдала латинізація перетворила ім’я вченого в іменник –‘алгоритм’.

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

З 1930-х років починається бурхливий розвиток області дослідження алгоритмів і становлення інформатики в сучасному вигляді. В 1936 р. англієць Тьюринг та американець Пост ввели формалізацію алгоритма як кінцевої сукупності дій простої гіпотетичної машини Тьюринга. Якщо машина Тьюринга спроможна вірішити задачу, то така задача формалізуєма і може бути описана АЛГОРИТМОМ, інакше – ця задача не має алгоритму. Прикладом задачі, що не формалізується є здобуття екстрасенсами інформації з потойбічного світу, процес творчості художників-реалістів.

Коротко зупинимося на описі машини Тьюринга.

Машина Тьюринга (мт)

МТ працює з безкінечною стрічкою комірок. Кожна комірка містить один символ із кінцевого набору S₀, S₁,… S_n, що зветься алфавітом машини.

Машина має кінцеву множину своїх внутрішніх станів q₀,q₁,…,q_m. В кожен момент часу МТ знаходиться в одному з цих станів.

Є головка зчитування/запису, яка в кожен момент знаходиться над однією із комірок. Нехай в момент t машина знаходиться в стані q_j над коміркою, що містить символ S_i, то наступною дією МТ може бути:

1. Головка стирає S_i і натомість записує інший символ S_k

2. Головка зміщується в сусідню ліву комірку

3. Головка зміщується в сусідню праву комірку

4. Машина зупиняється.

В ситуаціях 1-3 машина із стану q_j переходить у новий внутрішній стан q_r і готова до роботи в наступний момент. Дії машини можуть бути описані четвірками:

1. S_i q_j -> S_k q_r

2. S_i q_j -> S_k q_r (перехід до сусідньої лівої комірки)

3. S_i q_j -> S_k q_r (перехід до сусідньої правої комірки)

Якщо стрічку вкласти в МТ, встановити головку на комірку з символом S_i та задати машині внутрішній стан q_j, то МТ починає працювати над стрічкою, весь час змінюючи свій стан – читає і пише символи та пересувається до сусідніх комірок.

Якщо МТ колись зупиняється, то підсумкова стрічка, яка знаходиться в ній, зветься результатом застосування, а алгоритм - коректним.