Правила побудови алгоритмів

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

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

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

Це правило дозволяє відразу відокремити алгоритми від "методів" і "способів". Поки ми не маємо формалізованих вхідних даних, ми не можемо побудувати алгоритм.

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

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

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

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

4. Види алгоритмів і їх реалізація

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

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

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

2. Гнучкі алгоритми:

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

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

3. Лінійний алгоритм - набір команд (вказівок), що виконуються послідовно в часі одна за одною.

Приклад. Алгоритм Ранок

1. Встати о 6.30 годині.

2. Виконати гімнастичні вправи.

3. Умитися.

4. Поснідати.

5. Вийти з дому о 7.30 годині.

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

Приклад. Алгоритм Вечір

1. Повернутися після занять в університеті додому.

2. Пообідати.

3. Якщо погода хороша, то попрацювати в саду, інакше піти в бібліотеку,
взяти книжку, повернутися додому.

4. Зробити домашнє завдання.

5. Повечеряти.

6. Якщо є цікава телепередача, то подивитися телевізор, інакше почитати
книжку.

7. Лягти спати.

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

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

Приклад. Алгоритм Університет

1. Іти на першу пару.

2. Доки не закінчилися заняття іти на наступну пару.

3. Іти додому.

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

5. Методи представлення алгоритмів

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

Так само алгоритм є абстракцією і відрізняється від свого конкретного представлення. Існує багато способів представлення одного і того ж алгоритму. Наприклад, алгоритм для перекладу показників температури за шкалою Цельсія в показники за шкалою Фаренгейта традиційно представляється у вигляді формули:

F = (9/5)3 + 32.

Проте його можна представити і у вигляді інструкції: Помножити значення температури в градусах Цельсія на 9/5, а потім до отриманого результату додати 32.

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

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

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

• словесно-формульна(на природній мові з використанням математичних формул);

• графічна (зображення з графічних символів);

• псевдокоди (напівформалізовані описи алгоритмів на умовній алгоритмічній мові, що включають як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення і ін.);

• програмна (тексти на мовах програмування).

С ловесно-формульний опис алгоритму

Даний спосіб запису алгоритму складається з переліку дій (кроків), кожний з яких має порядковий номер. Алгоритм повинен виконуватися послідовно крок за кроком. Якщо в тексті алгоритму написано «перейти до кроку з номером L», то це означає, що виконання алгоритму продовжиться з вказаного кроку з номером L.

Приклад. Алгоритмі знаходження максимального з двох значень:

• визначимо формати змінних X, Y, М, де X і Y - значення для порівняння, М - змінна для зберігання максимального значення;

• отримаємо два значення чисел X і Y для порівняння;

• порівняємо X і Y.

• якщо X менше Y, значить більше число Y.

• помістимо в змінну М значення Y.

• якщо X не менше (більше) Y, значить більше число X.

• помістимо в змінну М значення X.

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

• такі описи строго не формалізуються;

• страждають багатослівністю записів;

• допускають неоднозначність тлумачення окремих розпоряджень.

Графічний опис у вигляді блок-схеми алгоритму

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

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

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

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

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

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

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

У таблиці 1 приведені найбільш часто вживані символи.

Табл. 1

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

Приклад. Блок-схема лінійного алгоритму.

де , де а, в, с - довжини сторін трикутника.

Псевдокод

При розробці алгоритму розробник повинен зберегти в пам'яті безліч взаємозв'язаних понять, об'єм яких в деяких випадках просто перевершує можливості людського мислення. (У своїй статті в журналі Psychological Review за 1956 рік Джордж Міллер (George A. Miller) описує дослідження, результати яких свідчать про те, що людське мислення здатне одночасно оперувати лише приблизно сімома деталями. Тому розробник складних алгоритмів потребує засобів запису, які дозволять йому при необхідності пригадати особливості будь-якої частини алгоритму, що розробляється ним. Впродовж 1950-1960-х рр. самим довершеним інструментом проектування були блок-схеми. Проте часто вони перетворювалися на заплутану павутину пересічних стрілок, що утрудняло розуміння структури алгоритму, що розроблявся. Тому з часом блок-схеми поступилися своїм місцем іншим методам представлення.

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

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

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

Приклад. Запис алгоритму на шкільній алгоритмічній мові:

алг Сума квадратів (арг цілий n, рез цілий S)

дано |n > 0

треба |S = 1*1+ 2*2 + 3*3 +... + n*n

поч цілий i

введення n; S:=0

пц для i від 1 до n

S:=S+i*i

кц

виведення "S=", S

Кін

Програмне представлення алгоритму

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

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

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

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

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

Процес перекладу алгоритму в машинну програму називається трансляцією. Першим кроком на шляху «олюднення» машинної мови стало створення програм, що переводять символічні імена в машинні коди. Потім були створені програми, що транслюють арифметичні вирази і, нарешті, в 1958 році вступив до ладу транслятор Фортрану, – першої широко використовуваної мови програмування. З того часу почався бурхливий розвиток мов програмування.

6. Порядок розробки ієрархічної схеми реалізації алгоритмів

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

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

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

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

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

2. Умовна конструкція. Цей блок включає перевірку деякої логічної умови (Р), залежно від якої виконується або один (S1), або інший (S2) оператори:

4. Блок узагальненого циклу. Цей блок забезпечує багатократне повторення виконання оператора S поки виконана логічна умова Р:

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

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

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

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

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

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

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

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

Нехай треба запрограмувати запис на відеомагнітофоні - на 4 каналі з 10.00 ранку до 11.25. Ця програма в голові у людини кодується приблизно так:

ПОКИ НЕ 10.00 - НІЧОГО НЕ РОБИТИ

ВСТАНОВИТИ КАНАЛ НОМЕР 4

ВКЛЮЧИТИ ЗАПИС

ПОКИ НЕ 11.25 - НІЧОГО НЕ РОБИТИ

ВИМКНУТИ ЗАПИС

Далі ця програма повинна бути перекодована на мову відеомагнітофона:

ВИБРАТИ ВІЛЬНЕ МІСЦЕ

ВСТАНОВИТИ "ДАТА ЗАПИСУ" = СЬОГОДНІ

ВСТАНОВИТИ "ПОЧАТОК ЗАПИСУ" = 10:00

ВСТАНОВИТИ "ЗАКІНЧЕННЯ ЗАПИСУ" = 11:25

ВСТАНОВИТИ "НОМЕР ТЕЛЕКАНАЛУ" = 4

Завантаження даної програми у відеомагнітофон полягає в натисненні на пульті відеомагнітофона відповідних кнопок для кожного рядка програми.

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

Поиск по сайту: