Обробка інформації та алгоритми

З базового курсу вам відомо:
Обробка інформації, поряд із зберіганням і передачею, відноситься до основних видів інформаційних процесів.
Варіанти обробки інформації
Обробка інформації здійснюється якимось суб’єктом або об’єктом (наприклад, людиною або комп’ютером) у відповідності з певними правилами. Будемо його називати виконавцем обробки інформації. Інформація, яка піддається обробці, представляється у вигляді вихідних даних. На рис. 2.5 в узагальненому вигляді представлений процес обробки інформації.
Модель обробки інформації
Можна навести безліч прикладів, що ілюструють схему на рис. 2.5.
Перший приклад: учень (виконавець), вирішуючи завдання з математики, робить обробку інформації.
Вихідні дані містяться в умові завдання. Математичні правила, описані в підручнику, визначають послідовність обчислень. Результат – це отриманий відповідь.
Другий приклад: переклад тексту з однієї мови на іншу – це приклад обробки інформації, при якій не змінюється її зміст, але змінюється форма подання – інша мова. Переклад здійснює перекладач за певними правилами, в певній послідовності.
Третій приклад: працівник бібліотеки складає картотеку книжкового фонду. На кожну книгу заповнюється картка, на якій вказуються всі параметри книги: автор, назва, рік видання, обсяг та ін. З карток формується каталог бібліотеки, де ці картки розташовуються в строгому порядку. Наприклад, в алфавітному каталозі картки розташовуються в алфавітному порядку прізвищ авторів.
Четвертий приклад: в телефонній книзі ви шукаєте телефон потрібної вам організації, наприклад плавального басейну; або в тому ж бібліотечному каталозі розшукуєте відомості про потрібної вам книзі. В обох випадках вихідними даними є інформаційний масив – телефонний довідник або каталог бібліотеки, а також критерії пошуку – назва організації або прізвище автора і назву книги.
Наведені приклади ілюструють чотири різних види обробки інформації:
1) отримання нової інформації, нових відомостей;
2) зміна форми подання інформації;
3) систематизація, структурування даних;
4) пошук інформації.
Всі ці види обробки може виконувати як людина, так і комп’ютер. У чому полягає принципова відмінність між процесами обробки, виконуваними людиною і машиною?
Якщо виконавцем обробки інформації є людина, то правила обробки, за якими він діє, не завжди формальні і однозначні. Людина часто діє творчо, неформально. Навіть однотипні математичні завдання він може вирішувати різними способами. Робота журналіста, вченого, перекладача та інших фахівців – це творча робота з інформацією, яка виконується ними не по формальними правилами.
Про алгоритми
Для позначення формалізованих правил, що визначають послідовність кроків обробки інформації, в інформатиці використовується поняття алгоритму.
З базового курсу інформатики ви знаєте, що слово «алгоритм» походить від імені видатного математика середньовічного Сходу Мухаммеда аль-Хорезмі, який описав ще в IX столітті правила виконання обчислень з багатозначними десятковими числами. Правила додавання, віднімання, множення стовпчиком, ділення «куточком», яким вас вчили в молодших класах, – це алгоритми аль-Хорезмі.
З поняттям алгоритму в математиці асоціюється відомий спосіб обчислення найбільшого загального дільника (НОД) двох натуральних чисел, який називають алгоритмом Евкліда. У словесній формі його можна описати так:
1. Якщо числа не рівні, то більше з них замінити на різницю більшого і меншого з чисел.
2. Якщо два числа рівні, то за НСД прийняти будь-яке з них, інакше перейти до виконання пункту 1.
Першокласник, який не знає, що таке НОД, але вміє порівнювати цілі числа і виконувати віднімання, зможе виконати алгоритм. Діяти при цьому він буде формально.
Такий формалізований алгоритм легко запрограмувати для сучасного комп’ютера. Мрія створити машину – автоматичний пристрій, який зможе без втручання людини проводити розрахунки, з’явилася дуже давно. Для її реалізації потрібні не тільки технічні можливості, а й глибоке розуміння сутності алгоритмів обробки інформації та розробка формалізованого способу представлення таких алгоритмів.
Алгоритмічні машини і властивості алгоритмів
У 30-х роках XX століття виникає нова наука – теорія алгоритмів. Питання, на яке шукає відповідь ця наука: для всякої Чи завдання обробки інформації може бути побудовано алгоритм рішення? Але щоб відповісти на це питання, треба спочатку домовитися про виконавця, на якого повинен бути орієнтований алгоритм.
Англійський вчений Алан Тьюринг запропонував модель такого виконавця, що отримала назву «машина Тьюринга». За задумом Тьюринга, його «машина» є універсальним виконавцем обробки будь-яких символьних послідовностей в будь-якому алфавіті. Практично одночасно з Тьюрінгом (1936-1937 рр.) Іншу модель алгоритмічної машини описав Еміль Пост. Машина Поста працює з двійковим алфавітом і дещо простіше у своєму «устрій».
Можна сказати, що машина Посту є окремим випадком машини Тьюринга. Однак саме робота з двійковим алфавітом представляє найбільший інтерес, оскільки, як ви знаєте, сучасний комп’ютер теж працює з двійковим алфавітом. Детальніше з машиною Посту ви познайомитеся в наступному параграфі.
На підставі моделей Тьюринга, Посту і деяких інших вчені прийшли до висновку про існування алгоритмічно нерозв’язних завдань.
Мова програмування алгоритмічних машин являє собою опис кінцевого числа простих команд, які можуть бути реалізовані в автоматичному пристрої.
Сукупність усіх команд мови виконавця називається системою команд виконавця алгоритмів – СКІ.
Алгоритм управління роботою алгоритмічної машини являє собою кінцеву послідовність команд, за допомогою виконання якої машина вирішує задачу обробки інформації.
Алгоритм управління такою машиною має володіти наступними властивостями:
– Дискретністю (кожен крок алгоритму виконується окремо від інших);
– Зрозумілістю (в алгоритмі використовуються тільки команди з СКІ);
– Точністю (кожна команда визначає однозначне дію виконавця);
– Кінцівкою (за кінцеве число кроків алгоритму виходить шуканий результат).
Відзначимо різницю між поняттями «команда алгоритму» і «крок алгоритму». Команда – це окрема інструкція в описі алгоритму, а крок алгоритму – це окрема дія, яке виконавець виконує по команді. У циклічних алгоритмах число кроків при виконанні алгоритму може бути більше, ніж число команд в алгоритмі, за рахунок повторного виконання одних і тих же команд.

Посилання на основну публікацію