НОУ ІНТУЇТ | лекція | Обробка даних

1. Опис процесу обробки даних. Поняття алгоритму та його властивості. Способи формальної записи алгоритмів

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

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

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

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

Опис процесу обробки даних. Поняття алгоритму та його властивості. Способи формальної записи алгоритмів

У повсякденному житті часто зустрічаються різного роду приписи, інструкції та інші подібні документи, що визначають порядок дій, які необхідно виконати для досягнення певного результату. Прикладами таких документів є інструкції по використанню різних пристроїв (побутових приладів, банкоматів, торговельних автоматів і т.п.), правила виконання робіт в промисловості і будівництві, регламенти здійснення різних дій (банківських операцій, операцій на фондових валютних і товарних біржах, перевірок технічного стану обладнання та об'єктів і т.п.). Ці приписи можуть відрізнятися різним ступенем точності і детальності опису дій. Якщо передбачається, що виконавцем припускає-саній буде деякий пристрій (агрегат, верстат, транспортний засіб або ЕОМ), то припис буде написано на деякій формальній мові. Типовим прикладом такого розпорядження є комп'ютерна програма, написана на деякій мові програмування. Узагальненням різного роду інструкцій і приписів є поняття алгоритму [27] , [35] .

Алгоритм - це точне, т. Е. Сформульоване певною мовою, кінцеве опис того чи іншого загального методу, заснованого на застосуванні здійсненних елементарних тактів обробки.

Розглянемо більш докладно окремі аспекти даного визначення. По-перше, у визначенні говориться, що опис має бути точним. Точність опису необхідна для того, щоб забезпечити однозначність розуміння дій, які потрібно виконувати, і послідовності їх виконання. Залежно від того, для кого призначений алгоритм, точність його опису може бути різною. Якщо алгоритм призначений для виконання людиною, то він може бути описаний на природній мові, наприклад, російською. В цьому випадку однозначного розуміння алгоритму не заважають деякі орфографічні помилки або нешкідливі помилки. Якщо алгоритм повинен виконуватися автоматичним пристроєм, то опис алгоритму виконується на деякій формальній мові (див. П. 6.3), наприклад, на мові інструкцій обчислювальної системи або мовою програмування високого рівня. Важливо також, щоб опис був кінцевим, щоб його можна було завантажити (прочитати) за кінцевий час.

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

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

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

Алгоритм називається детерміністичним, якщо в процесі його виконання немає ніякої свободи у виборі чергового кроку обробки.

Алгоритм називається детермінованим або однозначним, якщо результат алгоритму визначено однозначно (навіть якщо деякі кроки алгоритму не визначені однозначно).

Розглянемо приклади алгоритмів.

Алгоритм обчислення значення дробу . Спочатку обчислюються (використовуючи алгоритми додавання і віднімання) значення виразів і (В будь-якій послідовності), потім знаходиться частка від ділення отриманих результатів (використовуючи алгоритм розподілу).

Цей приклад демонструє ієрархічну структуру алгоритмів. Алгоритм обчислення дробу заснований на алгоритмах додавання, віднімання і ділення чисел. З того, що операції і можуть виконуватися в будь-якій послідовності, слід, що цей алго-ритм не детерминистический, але детермінований. Очевидно, що алгоритм завершується (достатньо всього трьох елементарних дій: додавання, віднімання і ділення).

Алгоритм вставки картки в впорядковану картотеку. Постановка завдання. Є колода карт. Нехай на кожній карті зафіксовано одне натуральне число. Потрібно вставити картку в картотеку, не порушивши впорядкованості картотеки.

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

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

Алгоритм для обчислення найбільшого загального дільника (НСД) двох натуральних чисел. Постановка задачі. Нехай дано два натуральних числа , де і ; треба знайти найбільший спільний дільник НСД чисел і .

Ще в III столітті до нашої ери математик Евклід, відомий автор першого дійшов до нас теоретичного трактату з математики "Почала", в геометричній формі виклав правило отримання найбільшого загального дільника двох натуральних чисел. Ідея цього правила (обгрунтування його коректності) полягає в тому, що якщо НОД - найбільший спільний дільник двох натуральних чисел і , То в разі рівності цих чисел він збігається з будь-яким з них, а в разі їх нерівності різниця між більшим і меншим разом з меншим має той же самий найбільший спільний дільник. Назвемо число, рівне тому з двох чисел , Яка не менше іншого, їх верхньою межею і позначимо , А друге позначимо . Після вирахування одного числа з іншого отримаємо нову пару чисел і , Верхня межа яких строго менше . Нові числа мають той же найбільший спільний дільник НСД . Значить, ми звели задачу до знаходження найбільшого загального дільника натуральних чисел, верхня межа яких менше первісної.

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

Сам алгоритм знаходження найбільшого спільного дільника НСД двох натуральних чисел і (Алгоритм Евкліда) можна викласти так:

1. якщо , То перейти до п. 4, інакше перейти до п. 2;
2. якщо , То перейти до п. 5, інакше перейти до п. 3;
3. вважати, що НОД . кінець;
4. від відняти і надалі вважати, що ця різниця є значенням . Повернутися до п. 1;
5. від відняти і надалі вважати цю різницю значенням . Повер-тися до п. 1.

Для алгоритму Евкліда арифметична операція "-" і перевірка виконання відносин "<" і "=" вважаються ефективними елементарними кроками обробки. Очевидно, що даний алгоритм є завер-шує. Однак якщо в постановці завдання опустити обмеження і , То виходить алгоритм, який для нерівних негативних чисел не переривається, тобто не є завершальним. Крім того, даний алгоритм є детерміністичним, тобто для кожних вихідних даних послідовність окремих кроків точно визначена.

Для розглянутих досить простих алгоритмів їх властивості (детерміністичного, детермінованість, завершаемості) легко встановлюються. Однак в загальному випадку різні властивості алгоритми-мов необхідно доводити. Доказ властивостей алгоритмів відноситься до проблематики теорії алгоритмів. Одним з найважливіших питань, яким займається теорія алгоритмів, є з'ясування того факту, що алгоритм вирішує сформульовану задачу для заданої множини вихідних даних. Цікавим є також знаходження безлічі вихідних даних, на якому алгоритм вирішує сформульовану задачу.

У наведених вище прикладах описів алгоритмів весь час зустрічалися деякі схожі один на одного фрагменти. Так, деякі кроки алгоритму можуть виконуватися лише за певної умови, або виконання деяких кроків виконується неодноразово. Часто також поставлена ​​задача вирішується за допомогою рішення того ж самого завдання, але з іншими вихідними даними (простішими). У цих випадках говорять про розгалуженні, повторенні і рекурсії.

Класичні елементи, які зустрічаються в описах алгоритмів, - це:

• виконання елементарних кроків;
• розгалуження за умовами;
• повторення;
• рекурсії.

У прикладі з обчисленням дробу ми маємо найбільш простий випадок: кількість елементарних тактів обробки постійно і не залежить від чисел a, b. Інша залежить від інших прикладах: у разі алгоритму Евкліда число кроків обробки залежить від величин чисел a, b, в разі алгоритму картки число кроків залежить від розміру картотеки. Хоча опис алгоритму звичайно і постійно, кількість фактично виконуваних тактів - величина змінна; це часто є наслідком використання прийому, зводить загальну задачу до більш простого завдання того ж класу. Цей прийом називають рекурсією. В алгоритмі Евкліда і алгоритмі вставки картки в впорядковану картотеку наявність рекурсії очевидно з алгоритму. В алгоритмах часто використовується спеціальний випадок рекурсії - чисто повторительная рекурсія. При описі алгоритму її часто записують у формі ітерації: "Поки виконано певну умову, повторювати ...".

Поряд з рекурсією і повторенням в алгоритмах зустрічається також аналіз можливих випадків. Без аналізу окремих випадків і виявлення умов завершення було б неможливо закінчення рекурсивних алгоритмів.

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

Розглянемо трохи детальніше спеціальний запис алгоритмів перетворення послідовностей знаків [27] , [35] . Такий запис пред-ставлять собою один із способів уточнення яку він розумів досі інтуїтивно поняття алгоритму.

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

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

Далі, якщо дано кінцеве безліч таких продукцій, перерахованих в певному порядку, то текстова заміна повинна проводитися за допомогою застосування найпершої (щодо цього порядку) з застосовних продукцій. Все це повторюється до тих пір, поки можливо, або ж до застосування особливим чином зазначеної продукції ( "зупиняє"). З огляду на, що одне зі слів у продукції може бути порожнім словом (див. 2.1.3), текстова заміна включає в себе вставку і приєднання знаків, а також викреслення знаків.

Такого роду алгоритми називають алгоритмами Маркова по імені радянського математика А. А. Маркова, який вперше описав їх в 1951 р Сам Марков називав їх "нормальними алгоритмами". Їх можна вважати уточненням поняття алгоритму, що досягається за рахунок використання спеціальної форми опису. Існують і інші підходи до уточнення (формалізації) поняття алгоритму, що використовуються, в основному, для теоретичних досліджень.

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

Деякі стандартні блоки, їх призначення та короткий опис наведено в таблиці.

Найменування Позначення Функція Процес Рятувальна операція або групи операцій, в результаті яких змінюється значення, форма подання або розташування даних Рішення Вибір напрямку виконання алгоритму в залежності від деяких змінних умов Введення-виведення Перетворення даних у форму, придатну для обробки (введення) або відображення результатів обробки (висновок) зумовлений процес Використання раніше створених і окремо написаних програм (підпрограм) Пуск-останов Початок, кінець, переривання процесу обробки і даних міжсторінкових з'єднувач Вказівка ​​зв'язку між перерваними лініями, які з'єднують блоки, розташовані на різних аркушах

Блоки з'єднуються лініями переходів, визначальними черговість виконання дій. Таке графічне представлення називається схемою алгоритму або блок-схемою. Набір символів, використовуваних в блок-схемах, і правила зображення блок-схем в даний час визначаються ГОСТ 19.701 - 90 (ІСО 5807 - 85) "Єдина система програмної документації. Схеми алгоритмів, програм, даних і систем. Умовні позначення і правила виконання" .