Процеси і потоки | управління пам'яттю | Організація вводу-виводу | драйвери пристроїв | файлові системи | Файлові системи Microsoft Windows | Операційна система Windows | службові програми |

загрузка...
загрузка...
На головну

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

  1. I. Загальні відомості про гідрології ВОДНИХ ОБ'ЄКТІВ, ХІМІЧНИХ І ФІЗИЧНИХ ВЛАСТИВОСТІ ПРИРОДНИХ ВОД
  2. N Технологічні системи мають властивості, які полегшують завдання забезпечення встановлених показників якості її функціонування.
  3. VI. Властивості циклічних вуглеводнів.
  4. А) Фізичні властивості.
  5. А) Квадратна матриця і її визначник. б) Особлива і неособлива квадратні матриці. в) Приєднана матриця. г) Матриця, зворотна даної, і алгоритм її обчислення.
  6. АКРЕЛ. Фторакса. СКЛАД. Властивості. ЗАСТОСУВАННЯ. РЕЖИМ ПОЛІМЕРИЗАЦІЇ
  7. Аксіоматика і деякі загальні властивості безлічі

5.1.1. Різні підходи до поняття "алгоритм".алгоритм - Одне з фундаментальних понять інформатики. Алгоритмізація поряд з моделюванням виступає в якості загального методу інформатики. Особливість положення полягає в тому, що при вирішенні практичних завдань, які передбачають розробку алгоритмів для реалізації на ЕОМ, майже завжди можна спирати високу формалізацію даного поняття. У таких випадках достатньо змістовного тлумачення поняття алгоритму і розгляду його основних властивостей. При такому підході алгоритмизация виступає як набір певних практичних прийомів, особливих навичок раціонального мислення в рамках заданих мовних засобів.

Поняття алгоритму в математики пройшло великий шлях розвитку. Загальне визначення алгоритму, що має інтуїтивний характер наступне.

Алгоритм - це загальний, однаковий, точно встановлений спосіб вирішення будь-якого завдання з даної масової проблеми. Таким чином, алгоритм завжди пов'язаний з рішенням масової проблеми. Завдання такого класу відрізняються один від одного значеннями входять до них параметрів. Приклади алгоритмів: витяг квадратного кореня, граничний перехід, знаходження похідної тощо. Наведене поняття алгоритму нестроге. У ньому зустрічаються слова, точний зміст яких не встановлено, наприклад, "спосіб". Проте, навіть при такому визначенні можна виділити деякі характерні риси алгоритму:

§) дискретність. Кожна наступна величина виходить із значень попередніх за певним законом. Всі величини виходять послідовно один за одним;

§ детермінованість. Між усіма величинами, одержуваними алгоритмом, існує жорстка причинний зв'язок. Наступні значення залежать від попередніх;

§ елементарність кроків алгоритму. Закон отримання подальшої системи величин з попередньої повинен бути простим;

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

§ результативність. Кінцевий результат завжди повинен бути отриманий.

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

В уточненні поняття алгоритму виділяються три напрямки:

q уточнення поняття ефективно обчислюваної функції. Цим займалися А. Черч * * і К. Гедель * * *. В результаті було виділено клас частково рекурсивних функцій, Що мають суворе математичне визначення;

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

q напрямок, пов'язаний з поняттям нормальних алгоритмів з робіт А. Маркова * * * *.

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

Перший напрямок уточнення - поняття алгоритму - пов'язане з точним описом спеціального класу функцій, які називаються рекурсивними. Числові функції, значення яких можна обчислити за допомогою алгоритму, називаються обчислюваної функції. Поняття алгоритму тут не визначено формально точно, тому поняття обчислюваної функції виявляється інтуїтивним. Однак сукупність обчислюваних функцій, що відповідають умовам 1-5, т. Е. Задовольняють характерних рис алгоритму для багатьох процесів, виявилася однією і тією ж, легко описуваної в математичних термінах. Ця точно описана сукупність числових функцій, що збігається із сукупністю всіх обчислюваних функцій при найширшому розумінні алгоритму, називається сукупністю рекурсивних функцій.

Рекурсивні функції вперше описані Геделем, потім в 1936 році Черч прийшов до такого ж класу функцій. Аналіз ідей, що лежать в основі визначення рекурсивних функцій, дозволив Чёрчу висловити гіпотезу про те, що клас рекурсивних функцій тотожний з класом всюди певних обчислюваних функцій. Ця гіпотеза відома під ім'ям тези Черча; довести її не можна, так як поняття обчислюваної функції точно не визначено. В силу тези Черча питання про обчислюваності функції рівносильний питання про її рекурсивності. Поняття рекурсивної функції суворе. Оскільки в алгоритмічних проблеми мова зазвичай йде не про алгоритми, а про обчислюваності деяких, спеціальним чином підібраних вирішують проблему функціях, то можна строго довести, що вирішальна конкретне завдання функція не може бути рекурсивної, а, отже, не існує і алгоритму вирішення цього завдання. Саме цим шляхом Черч довів нерозв'язність алгоритмічної проблеми логіки предикатів.

Якщо перший напрямок уточнює поняття алгоритму через клас рекурсивних функцій, то друге, пов'язане з машинної арифметикою, спочатку уточнює поняття алгоритму, а потім визначає клас обчислюваних функцій. Цей напрямок розвинене Е. Постом * і А. Тьюрингом * *. Основна ідея цього напрямку полягає в тому, що алгоритмічні процеси - це процеси, які можуть імітувати у відповідний побудованих машинах, які описуються в точних математичних термінах. В результаті виявляється, що складні процеси можна моделювати на простих пристроях. Всякий алгоритм може бути заданий деякою функціональною схемою і реалізований у відповідній машині Тьюринга. Ця гіпотеза називається тезою Тьюринга. Його також не можна довести, з тієї ж причини, що і теза Черча. Всі відомі досі алгоритми можуть бути задані за допомогою тьюрінгових функціональних схем.

Третій напрям - теорія нормальних алгоритмів Маркова.

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

Основне положення про "універсальності" нормальних алгоритмів - принцип нормалізації: будь-який алгоритм над кінцевим алфавітом еквівалентний щодо певного нормальному алгоритму над. Цей принцип подібний до тез Черча і Тьюринга і недоказуем через невизначеність формального поняття алгоритму. На практиці досить обмежитися алгоритмами, що діють на послідовностях натуральних чисел і видають як значення також послідовності натуральних чисел. Дії нормальних алгоритмів Маркова схожі на дії машин Тьюринга.

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

3.1.2. Графічне представлення алгоритмів. Алгоритм, складений для деякого виконавця, можна уявити різними способами: за допомогою графічного або словесного опису, у вигляді таблиці, послідовністю формул, записаним на алгоритмічній мові. Розглянемо наступні способи опису алгоритму: словесний опис, псевдокод, блок-схема, програма.

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

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

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

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

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

Доведено, що логічна структура будь-якої програми може бути виражена комбінацією трьох базових структур: слідування, розгалуження і циклу (теорема Бема - Якопіні *).

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

Розгалуження - це структура, що забезпечує вибір між двома альтернативами. Виконується перевірка, а потім вибирається один із шляхів (див. Рис. 3.2 б). Ця структура називається також ЯКЩО - ТО - ІНАКШЕ. Кожен з двох шляхів веде до спільної точки злиття, так що виконання програми триває незалежно від того, який шлях був обраний.

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

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

 



Прикладне програмне забезпечення | Принципи розробки алгоритмів і програм для вирішення прикладних завдань
загрузка...
© um.co.ua - учбові матеріали та реферати