Реферат Алгоритм і його властивості

Поняття алгоритму - одне з фундаментальних понять інформатики. Алгоритмізація поряд з моделюванням виступає в якості загального методу інформатики. До реалізації певних алгоритмів зводяться процеси управління в різних системах, що робить поняття алгоритму близьким і кібернетиці.

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

Особливість становища полягає в тому, що при вирішенні практичних завдань, що припускають розробку алгоритмів для реалізації на ЕОМ, і тим більше при використанні на практиці інформаційних технологій, можна, як правило, не спиратися на високу формалізацію даного поняття. Тому представляється доцільним познайомитися з алгоритмами і алгоритмізацією на основі змістовного тлумачення сутності поняття алгоритму та розгляду основних його властивостей. При такому підході алгоритмізація більш виступає як набір певних практичних прийомів, особливих специфічних навичок раціонального мислення в рамках заданих мовних засобів. Можна провести аналогію між цією обставиною і розглянутим вище підходом до вимірювання інформації: тонкі математичні побудови при В«кібернетичномуВ» підході не дуже потрібні при використанні набагато більш простого В«об'ємногоВ» підходу при практичній роботі з комп'ютером.

Саме слово В«алгоритмВ» походить від algorithmi - латинської форми написання імені великого математика IX століття аль-Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмами і розуміли тільки правила виконання чотирьох арифметичних дій над багатозначними числами.

Поняття виконавця неможливо визначити за допомогою небудь формалізації. Виконавцем може бути людина, група людей, робот, верстат, комп'ютер, мова програмування і т.д. Найважливішою властивістю, характеризує будь-якого з цих виконавців, є те, що виконавець уміє виконувати деякі команди. Так, виконавець-людина вміє виконувати такі команди як В«встатиВ», В«сістиВ», В«включити комп'ютерВ» і т.д., а виконавець-мову програмування Бейсік - команди PRINT, END, LIST та інші аналогічні. Вся сукупність команд, які даний виконавець уміє виконувати, називається системою команд виконавця (СКІ).

В якості прикладу (ріс.1.11) розглянемо виконавця-робота, робота якого полягає у власному переміщення по робочому полю (квадрату довільного розміру, розділеному на клітини) і переміщенні об'єктів, в початковий момент часу знаходяться на В«складіВ» (права верхня клітка).

Ріс.1.11. Виконавець-робот

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

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

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

Алгоритм

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

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

2. Використовувані на практиці алгоритми складаються з орієнтацією на певного виконавця. Щоб скласти для нього алгоритм, потрібно знати, які команди цей виконавець може зрозуміти і виконати, а які - не може. Ми знаємо, що у кожного виконавця є своя система команд. Очевидно, складаючи запис алгоритму для певного виконавця, можна використовувати лише ті команди, які є в його СКІ. Це властивість алгоритмів будемо називати зрозумілістю.

3. Будучи зрозумілим, алгоритм не повинен містити приписів, зміст яких може сприйматися неоднозначно, тобто одна і та ж команда, будучи зрозуміла різним виконавцям, після виконання кожним з них повинна давати однаковий результат.

Запис алгоритму повинна бути настільки чіткою, повною і продуманої в деталях, щоб у виконавця не могло виникнути потреби в прийнятті рішень, не передбачених укладачем алгоритму. Говорячи інакше, алгоритм не повинен залишати місця для сваволі виконавця. Крім того, в алгоритмах неприпустимі також ситуації, коли після виконання чергової команди алгоритму виконавцю незрозуміло, яка з команд алгоритму повинна виконуватися на наступному кроці.

Зазначене властивості алгоритмів називають визначеністю або детерминированностью.

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

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

Досить поширеним способом представлення алгоритму є його запис на алгоритмічній мові, що представляє в загальному випадку систему позначень і правил для однакової і точного запису алгоритмів та виконання їх. Відзначимо, що між поняттями В«алгоритмічну мовуВ» і В«мови програмування В»є розходження; перш за все, під виконавцем у алгоритмічній мові може матися на увазі не тільки комп'ютер, але й пристрій для роботи В«в обстановціВ». Програма, записана на алгоритмічній мовою, не обов'язково призначена комп'ютера. Практична ж реалізація алгоритмічної мови - окреме питання в кожному конкретному випадку.

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