889

Теорія алгоритмів

Лекция

Информатика, кибернетика и программирование

Введення до теорії алгоритмів. Сучасний погляд на алгоритмізацію. Основні алгоритмічні конструкції. Модульна структура програмних продуктів.

Украинкский

2013-01-06

173.5 KB

143 чел.

Теорія алгоритмів

Лекція 1 (2 г.) 

Тема: Введення до теорії алгоритмів. Сучасний погляд на алгоритмізацію.Основні алгоритмічні конструкції. Модульна структура програмних продуктів.

План:

  1.  Поняття алгоритму
  2.  Способи запису алгоритмів
  3.  Основні алгоритмічні конструкції
  4.   Створення алгоритму
  5.   Математична модель, вибір структури даних
  6.  Алгоритмічні мови
  7.  Структурні принципи алгоритмізації
  8.  Модульне програмування. Модульна структура програмних продуктів
  9.  Сучасний погляд на алгоритмізацію

1. Поняття алгоритму

АЛГОРИТМ – система правил, сформульована на зрозумілому виконавцеві мові, яка визначає процес переходу від допустимих початкових даних до деякого результату і володіє властивостями масовості, кінцівки, визначеності, детермінованої.

Точне визначення поняття алгоритму дало можливість довести алгоритмічну нерозв'язність багатьох математичних проблем.

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

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

Сформулюємо основні особливості алгоритмів.

Наявність початкових даних і деякого результату. Алгоритм – це точно певна інструкція, послідовно застосовуючи яку до початкових даних, можна отримати рішення задачі.

Масовість, тобто можливість застосовувати багато разів один і той же алгоритм.

Детермінованість. При застосуванні алгоритму до одних і тих же початкових даних повинен виходити завжди один і той же результат.

Результативність. Виконання алгоритму повинне обов'язково приводити до його завершення.

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

2. Способи запису алгоритмів

На практиці найбільш поширеними є наступні форми запису алгоритмів:

1) графічний запис (блок-схеми);

2) словесний запис (псевдокоди);

3) мова програмування.

Словесна форма запису алгоритму є описом на природній мові послідовних етапів обробки даних.

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

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

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

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

Мова програмування - мова, використовувана для формального запису алгоритмів. Більшість мов програмування відносяться до алгоритмічних мов. Запис алгоритму на алгоритмічній мові називають програмою.

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

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

Синтаксис - это набор правил, определяющих возможные сочетания (конструкции) из букв алфавита. Для описания синтаксиса языка, как правило, используют другой язык (метаязык) или синтаксические диаграммы.

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

3. Основні алгоритмічні конструкції

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

Даний блок має один вхід і один вихід. З простих команд і перевірки умов утворюються складені команди, що мають складнішу структуру і теж один вхід і один вихід.

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

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

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

Команда галуження може бути повної і неповної форми. Неповна форма команди галуження використовується тоді, коли необхідно виконувати дію S тільки у разі дотримання умови P. Якщо умова P не дотримується, то команда галуження завершує свою роботу без виконання дії. Прикладом команди галуження неповної форми буде зменшення в два рази тільки парного числа.

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

Команда повторення з передумовою не є єдино можливою. Різновидом команди повторення з передумовою є команда повторення з параметром. Вона використовується тоді, коли відома кількість повторень дії. У блок-схемі команди повторення з параметром умова записується не в ромбі, а в шестикутнику. Прикладом циклічного алгоритму з параметром буде знаходження суми перших 20 натуральних чисел.

У команді повторення з умовою поста спочатку виконується дія S і лише потім, перевіряється умова P. Причому дія повторюється до тих пір, поки умова не дотримується. Прикладом команди повторення з умовою поста буде зменшення позитивного числа до тих пір, поки воно ненегативне. Як тільки число стає негативним, команда повторення закінчує свою роботу.
За допомогою з'єднання тільки цих елементарних конструкцій (послідовно або вкладенням) можна "зібрати" алгоритм будь-якого ступеня складності.

Лінійний алгоритм

Приведемо приклад запису алгоритму у вигляді блок-схеми, псевдокодів і на мові Паскаль. Ручне тестування і підбір системи тестів виконуються аналогічно попередньому завданню.

Алгоритм, що розгалужується

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

Циклічний алгоритм

Розглянемо алгоритм знаходження суми перших натуральних непарних чисел до n. Представимо запис алгоритму трьома способами: у вигляді блок-схеми, шкільної алгоритмічної мови і на мові програмування Pascal.

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

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

4. Створення алгоритму

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

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

Усі алгоритми поділяються на два великі класи. Це алгоритми з повторениями та рекурсивні алгоритми.

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

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

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

визначення моделі задачі, що розв'язується;

запис алгоритму мовою програмування;

тестування програми на комп'ютері;

отримання розв'язку поставленої задачі шляхом виконання завершеної програми.

5. Математична модель, вибір структури даних

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

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

6. Алгоритмічні мови

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

Для виконання програми на мові високого рівня її потрібно спочатку перекласти мовою машинних команд. Спеціальна програма, що виконує такий переклад, називається транслятором або компілятором. Програма, що відтранслює, потім виконується безпосередньо комп'ютером. Існує також можливість перекладу програми на проміжну мову, не залежну від архітектури конкретного комп'ютера, але проте максимально наближений до мови машинних команд. Потім програма на проміжній мові виконується спеціальною програмою, яка називається інтерпретатором. Можливий також варіант компіляції "на льоту" (Just In Time Compilation), коли виконуваний фрагмент програми перекладається з проміжної мови на мову машинних команд безпосередньо перед виконанням.

Найбільш поширені компільовані мови - це Сі, C++, Фортран, Паскаль. Історично однією з перших мов високого рівня був Фортран. Найуспішніша мова програмування - мова Сі і пов'язана з ним лінія об'єктно-орієнтованих мов: C++, Java, C#.

В даний час переважна частина програм пишеться на мовах Сі і C++. Інтерфейс будь-якої операційної системи (так званий API - Application Program Interface), тобто набором системних викликів, призначених для розробників прикладних програм, як правило, є набір функцій на мові Сі. Нарешті, сучасні об'єктно-орієнтовані мови також засновані на мові Сі. Це мова C++, що займає проміжне положення між традиційними і об'єктно-орієнтованими мовами, а також об'єктно-орієнтовані мови Java і C#.

7. Структурні принципи алгоритмізації 

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

Теорема про структуризацію: будь-яка проста програма може бути перетворена у функціонально їй еквівалентну програму, побудовану на основі 3 наступних структур:

  1.  Проходження.
  2.  Якщо-то-інакше.
  3.  Цикл з передумовою.

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

Цілі структурного програмування

  1.  Забезпечити дисципліну програмування
  2.  Поліпшити читабельність програми
  3.  Підвищити ефективність програми

Низхідне проектування

Метод низхідного проектування припускає послідовне розкладання загальної функції обробки даних на прості функціональні елементи ("зверху-вниз").

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

Послідовність дій з розробки функціональної структури алгоритму застосування:

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

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

Функції введення-виводу інформації рекомендується відокремлювати від функцій обчислювальної або логічної обробки даних.

По частоті використання функції діляться на:

  •  одноразово виконувані;
  •  що повторюються.

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

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

8. Модульне програмування

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

Модуль характеризують:

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

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

Властивості модулів: 

  •  функціональна цілісність і завершеність (кожен модуль реалізує одну функцію, але реалізує добре і повністю);
  •  автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);
  •  можливість розвитку;
  •  відвертість для користувачів і розробників (для модернізації і використання);
  •  коректність і надійність;
  •  посилання на тіло модуля відбувається тільки по імені модуля, тобто виклик і актуалізація модуля можливі тільки через його заголовок.

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

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

Модульна структура програмних продуктів

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

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

При визначенні набору модулів, що реалізовують функції конкретного алгоритму, необхідно враховувати наступне:

  •  кожен модуль викликається на виконання вищестоящим модулем і, закінчивши роботу, повертає управління модулю, що викликав його;
  •  ухвалення основних рішень в алгоритмі виноситься на максимально "високий" за ієрархією рівень;

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

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

Тестування алгоритму не може дати повної (100%-ой) гарантії правильності алгоритму для всіх можливих наборів вхідних даних, особливо для достатньо складних алгоритмів.

Контроль програмного модуля.

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

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

9. Сучасний погляд на алгоритмізацію

У теоретичних підходах до побудови строгого визначення поняття алгоритму історично виділилися три основні напрями.

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

Другий напрям пов'язаний з машинною математикою. Третій напрям пов'язаний з поняттям нормальних алгоритмів, введеним і розробленим російським математиком А.А.Марковим на початку 50-х рр. XX в.

Контрольні питання:

  1.  Дати визначення алгоритма.
  2.  Форми представлення алгоритмів.
  3.  Які існують способи запису алгоритмів.
  4.  Цілі структурного програмування.
  5.  В чому полягає тестування алгоритму.
  6.  Контроль програмного модуля.

Література:

  1.  Ахи А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.: Пер. с англ. М.: Издат. дом «Вильямс», 2000.  С. 183–225
  2.  Кормен Т., Лейзерсон Ч., Ривест Р.., Алгоритмы: построение и анализ: Пер. с англ., М.: МЦНМО, 2001. С. 8891, 435523
  3.  Седжвик Р. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах: Пер. с англ. СПб.: «ДиаСофтЮП», 2003. С. 673–1000


 

А также другие работы, которые могут Вас заинтересовать

69457. Разработка трехмерной графической модели проводящей системы сердца 2.04 MB
  В работе приводится подробное описание модели и использованного средства разработки. Это позволяет использовать работу в учебных целях, а также она может использоваться специалистами при моделировании как нормальных, так и патологических работах сердца.
69458. Духовная ситуация времени и правовая подготовка студента педагогического Вуза 55 KB
  Так в курсе Основы права в институтах народного хозяйства делался упор на уголовно-правовую ответственность хозяйственных работников в технических Вузах на соблюдении норм техники безопасности и т.
69459. Присоединение Прибалтики к России, Эстляндия и Лифляндия в составе России 33.5 KB
  Прибалтика состоящая из Эстляндии Курляндии и Лифляндии была как известно присоединена к России в ходе Северной войны 1700-1721 которую вела Россия со Швецией за выход к Балтийскому морю. В результате победы России по Ништадтскому мирному договору 1721 г.
69460. Присоединение Северного Кавказа к России. Кавказская война 25.5 KB
  С присоединением к России территорий Закавказья территория Северного Кавказа была как бы независимым анклавом внутри Российского государства. госств заставлял обезопасить свои тылы тем более что многие народы в надежде избавиться от притязаний Турок стремились...
69461. Продажа Аляски. Явный и скрытый механизм сделки 28 KB
  Явный и скрытый механизм сделки Причины продажи Аляски: 1 опасность применения силы со стны США в целях присоединения этой территории; 2 убыточность РАК; 3 желание сохранить дружественные отношения с США; 4 Опасность распространения республиканских идей...
69462. Лирика А. С. Пушкина: особенности мироотношения поэта, жанровая динамика 37.12 KB
  Лицейский период 1811-1817 осваивает жанры и стили. Ода, элегия, политические стихи, эпиграммы, пародии. Основной – жанр дружеского послания. – пограничный между прозой и поэзией. «К товарищам». Поэт - ленивец, отказывающийся от социальных обязанностей, свободный, профессиональный литератор.
69463. Рассказ в русской литературе 18.27 KB
  Человек испытывает универсальные чувства понятные всем. Все о чем пишет Казаков предельно просто: универсальные чувства страха обиды восторга отчаяния и др. Движение человека от жизни дневной к жизни ночной где дневная жизнь расценивается как инерция ночь же позволяет...
69464. Розанов. Легенда о Великом Инквизиторе 17.84 KB
  Религия нечто высокое и сделать ей возможно другого человека способность войти в ее миросозерцание высшая цель. Здесь надломленность человеческих сил неспособность их продолжать тот путь по который от скрытого начала к скрытому же концу ведет человека провидение.
69465. Сатира в литературе 1920-х годов 18.38 KB
  В 1920-ые годы возникла необходимость в так называемом «отдыхе». Человек на протяжении последних лет был погружен в атмосферу революций, гражданских войн – «кровавых» событий. Пьесы, которые ставились на сцене театра, имели «лечебное» воздействие; театр – это место, где собирается масса народа; происходящее на сцене...