- •Основи алгоритмізації
- •Машина Тьюринга (мт)
- •Перші еом
- •Частина 1. Основи програмування Розділ 1. Архітектура сучасних пк
- •1.1. Структурна схема пк
- •1.2. Загальні|загальні| принципи роботи комп'ютера
- •1.3. Позиційні системи числення
- •Завдання для самостійної роботи
- •Розділ 2. Історія розвитку мов|язиків| програмування високого рівня
- •Розділ 3. Загальні|загальні| принципи програмування
- •3.1. Вимоги до професії
- •3.2. Мови|язики| програмування і програмне|програмова| середовище|середовище|
- •3.3. Структура програмних комплексів
- •3.4. Структура програми
- •3.5. Технологія програмування і налагодження програм на мвр
- •3.6. Техніка обчислень|підрахунків|
- •3.7. Типи обчислювальних процесів
- •3.8. Цикли в обчислювальному процесі
- •3.9. Загальна структура прикладної програми
- •3.10. Типи підпрограм
- •Завдання для самостійної роботи
- •Кодування Windows-1251 (синоним cp1251)
- •Двобайтне кодування стандарту unicode – utf-8,utf-16
Основи алгоритмізації
Зміст
Поняття алгоритму. Історична довідка
Формалізація рішення задачі. Машина Тьюринга
Історія розвитку ЕОМ.
Архітектура сучасних ПК.
Структурна схема ПК
Загальні принципи роботи комп’ютера
Позиційні системи числення
Графічне відображення алгоритмів за правилами ГОСТ 19.701-90 (ISO 5807-85). Приклад.
Загальні принципи програмування
Вимоги до професії
Мови програмування та програмне середовище
Структура програмних комплексів
Структура програми
Технологія програмування на МВР та налагодження програм
Техніка обчислень
Типи обчислювальних процесів
Цикли в обчислювальному процесі
Загальна структура прикладної програми
Сучасні таблиці кодування символів
ASCII-таблиця
Поняття алгоритму. Історична довідка
Алгоритм (від імені перського математика, 9 ст. аль-Хорезмі, Algorithmi)- послідовність правил виконання обчислювального процесу, що приводить до рішення певного класу задач після кінцевого числа операцій. При написанні програм алгоритм задає логічну послідовність операцій. Для візуального відображення алгоритмів використовують блок-схеми, що оформлюються згідно з ГОСТ 19.701-90 (ISO 5807-85).
Наведемо коротку історичну довідку про розвиток поняття алгоритму.
У 825 р.н.е. аль_Хорезмі написав трактат, де розглянув винайдену в Індії позиційну десяткову систему числення і вивів правила підрахунків в позиційних системах. У 12 столітті перекладена на латину книга потрапила до Європи під назвою “Algorithmi de numero Indorum”. Невдала латинізація перетворила ім’я вченого в іменник –‘алгоритм’.
Перший алгоритм, призначений для виконання на автоматичному обчислювальному пристрої, застосувала Ада Лавлейс у 1843 році для опису обчислення чисел Бернуллі на механічній машині Беббіджа.
З 1930-х років починається бурхливий розвиток області дослідження алгоритмів і становлення інформатики в сучасному вигляді. В 1936 р. англієць Тьюринг та американець Пост ввели формалізацію алгоритма як кінцевої сукупності дій простої гіпотетичної машини Тьюринга. Якщо машина Тьюринга спроможна вірішити задачу, то така задача формалізуєма і може бути описана АЛГОРИТМОМ, інакше – ця задача не має алгоритму. Прикладом задачі, що не формалізується є здобуття екстрасенсами інформації з потойбічного світу, процес творчості художників-реалістів.
Коротко зупинимося на описі машини Тьюринга.
Машина Тьюринга (мт)
МТ працює з безкінечною стрічкою комірок. Кожна комірка містить один символ із кінцевого набору S0, S1,… Sn, що зветься алфавітом машини.
Машина має кінцеву множину своїх внутрішніх станів q0,q1,…,qm. В кожен момент часу МТ знаходиться в одному з цих станів.
Є головка зчитування/запису, яка в кожен момент знаходиться над однією із комірок. Нехай в момент t машина знаходиться в стані qj над коміркою, що містить символ Si, то наступною дією МТ може бути:
Головка стирає Si і натомість записує інший символ Sk
Головка зміщується в сусідню ліву комірку
Головка зміщується в сусідню праву комірку
Машина зупиняється.
В ситуаціях 1-3 машина із стану qj переходить у новий внутрішній стан qr і готова до роботи в наступний момент. Дії машини можуть бути описані четвірками:
Si qj -> Sk qr
Si qj -> Sk qr (перехід до сусідньої лівої комірки)
Si qj -> Sk qr (перехід до сусідньої правої комірки)
Якщо стрічку вкласти в МТ, встановити головку на комірку з символом Si та задати машині внутрішній стан qj, то МТ починає працювати над стрічкою, весь час змінюючи свій стан – читає і пише символи та пересувається до сусідніх комірок.
Якщо МТ колись зупиняється, то підсумкова стрічка, яка знаходиться в ній, зветься результатом застосування, а алгоритм - коректним.