ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНФРАСТРУКТУРИ ТА ТЕХНОЛОГІЙ
ІНСТИТУТ УПРАВЛІННЯ, ТЕХНОЛОГІЙ ТА ПРАВА
імені гетьмана Петра Конашевича-Сагайдачного
ФАКУЛЬТЕТ УПРАВЛІННЯ ТА ТЕХНОЛОГІЙ
Кафедра інформаційних технологій
Реферат на тему
“ Основи алгоритмізації”
Студента групи КН 1622
Шматка Максима Миколайовича
Прийняв :
_________ Шикула О. М.
(підпис)
Київ – 2019
План
Поняття алгоритму
Блок-схема алгоритму
1. Поняття алгоритму
Одним з фундаментальних понять в інформатиці є поняття алгоритму. Походження самого терміна "алгоритм" пов'язане з математикою. Це слово походить від Algorіthmі - латинського написання імені Мухаммеда аль-хорезми (787 - 850) видатного математика середньовічного Сходу. У своїй книзі "Про індійський рахунок" він сформулював правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними стовпчиком. Надалі алгоритмом стали називати точне приписання, що визначає послідовність дій, що забезпечує одержання необхідного результату з вихідних даних. Алгоритм може бути призначений для виконання його людиною або автоматичним пристроєм. Створення алгоритму, нехай навіть найпростішого, - процес творчий. Він доступний винятково живим істотам, а довгий час уважався, що тільки людині. В XІІ в. був виконаний латинський переклад його математичного трактату, з якого європейці довідалися про десяткову позиційну систему числення й правилах арифметики багатозначних чисел. Саме ці правила в той час називали алгоритмами.
Дане вище визначення алгоритму не можна вважати строгим - не цілком ясно, що таке "точне приписання" або "послідовність дій, що забезпечує одержання необхідного результату". Тому звичайно формулюють кілька загальних властивостей алгоритмів, що дозволяють відрізняти алгоритми від інших інструкцій.
Такими властивостями є:
- Дискретність (перервність, роздільність) - алгоритм повинен представляти процес рішення завдання як послідовне виконання простих (або раніше певних) кроків. Кожна дія, передбачена алгоритмом, виконується тільки після того, як закінчилося виконання попередні.
- Визначеність - кожне правило алгоритму повинне бути чітким, однозначним і не залишати місця для сваволі. Завдяки цій властивості виконання алгоритму носить механічний характер і не вимагає ніяких додаткових вказівок або відомостей про розв'язуване завдання.
- Результативність (кінцівка) - алгоритм повинен приводити до рішення завдання за кінцеве число кроків.
- Масовість - алгоритм рішення завдання розробляється в загальному виді, тобто, він повинен бути застосуємо для деякого класу завдань, що розрізняються тільки вихідними даними. При цьому вихідні дані можуть вибиратися з деякої області, що називається областю застосовності алгоритму.
На підставі цих властивостей іноді дається визначення алгоритму, наприклад: "Алгоритм - це послідовність математичних, логічних або разом узятих операцій, що відрізняються детерменированностью, масовістю, спрямованістю й, що приводить до рішення всіх завдань даного класу за кінцеве число кроків". Таке трактування поняття "алгоритм" є неповною й неточною. По-перше, невірно зв'язувати алгоритм із рішенням якого-небудь завдання. Алгоритм взагалі може не вирішувати ніякого завдання. По-друге, поняття "масовість" ставиться не до алгоритмів як до таким, а до математичних методів у цілому. Рішення поставлених практикою завдань математичними методами засновано на абстрагуванні - ми виділяємо ряд істотних ознак, характерних для деякого кола явищ, і будуємо на підставі цих ознак математичну модель, відкидаючи несуттєві ознаки кожного конкретного явища. У цьому змісті будь-яка математична модель має властивість масовості. Якщо в рамках побудованої моделі ми вирішуємо завдання й рішення представляємо у вигляді алгоритму, то рішення буде "масовим" завдяки природі математичних методів, а не завдяки "масовості" алгоритму.
Роз'ясняючи поняття алгоритму, часто приводять приклади "побутових алгоритмів": скип'ятити воду, відкрити двері ключем, перейти вулицю й т.д. : рецепти готування яких-небудь ліків або кулінарних рецептів є алгоритмами. Але для того, щоб приготувати ліки по рецепті, необхідно знати фармакологію, а для готування блюда по кулінарному рецепті потрібно вміти варити. Тим часом виконання алгоритму - це бездумне, автоматичне виконання приписань, що у принципі не вимагає ніяких знань. Якби кулінарні рецепти являли собою алгоритмы, то в нас просто не було б такої спеціальності - кухар.
Правила виконання арифметичних операцій або геометричних побудов являють собою алгоритми. При цьому залишається без відповіді питання, чим же відрізняється поняття алгоритму від таких понять, як "метод", "з", "правило". Можна навіть зустріти твердження, що слова "алгоритм", "спосіб", "правило" виражають те саме (тобто є синонімами), хоча таке твердження, мабуть, суперечить "властивостям алгоритму".
Саме вираження "властивості алгоритму" некоректно. Властивостями володіють об'єктивно існуючі реальності. Можна говорити, наприклад, про властивості якої-небудь речовини. Алгоритм - штучна конструкція, що ми споруджуємо для досягнення своїх цілей. Щоб алгоритм виконав своє призначення, його необхідно будувати за певними правилами. Тому потрібно говорити не про властивості алгоритму, а про правила побудови алгоритму, або про вимоги, пропонованих до алгоритму.
Перше правило - при побудові алгоритму насамперед необхідно задати безліч об'єктів, з якими буде працювати алгоритм. Формалізоване (закодоване) подання цих об'єктів зветься даних. Алгоритм приступає до роботи з деяким набором даних, які називаються вхідними, і в результаті своєї роботи видає дані, які називаються вихідними. Таким чином, алгоритм перетворить вхідні дані у вихідні.
Це правило дозволяє відразу відокремити алгоритми від "методів" й "способів". Поки ми не маємо формалізованих вхідних даних, ми не можемо побудувати алгоритм.
Друге правило - для роботи алгоритму потрібна пам'ять. У пам'яті розміщаються вхідні дані, з якими алгоритм починає працювати, проміжні дані й вихідні дані, які є результатом роботи алгоритму. Пам'ять є дискретної, тобто складається з окремих осередків. Пойменована комірка пам'яті зветься змінної. У теорії алгоритмів розміри пам'яті не обмежуються, тобто вважається, що ми можемо надати алгоритму будь-який необхідний для роботи обсяг пам'яті.
У шкільній "теорії алгоритмів" ці два правила не розглядаються. У той же час практична робота з алгоритмами (з) починається саме з реалізації цих правил. У мовах програмування розподіл пам'яті здійснюється декларативними операторами (з опису змінних). У мові Бейсик не всі змінні описуються, звичайно з тільки масиви. Але однаково при запуску програми транслятор мови аналізує всі ідентифікатори в тексті програми й відводить пам'ять під відповідні змінні.
Третє правило - дискретність. Алгоритм будується з окремих кроків (дій, операцій, команд). Безліч кроків, з яких складений алгоритм, звичайно.
Четверте правило - детерменированность. Після кожного кроку необхідно вказувати, який крок виконується наступної, або давати команду зупинки.
П'яте правило - збіжність (результативність). Алгоритм повинен завершувати роботу після кінцевого числа кроків. При цьому необхідно вказати, що вважати результатом роботи алгоритму.
Отже, алгоритм - невизначуване поняття теорії алгоритмів. Алгоритм кожному певному набору вхідних даних ставить у відповідність деякий набір вихідних даних, тобто обчислює (реалізує) функцію. При розгляді конкретних питань у теорії алгоритмів завжди мається на увазі якась конкретна модель алгоритму.
Будь-яка робота на комп'ютері - це є обробка інформації. Роботу комп'ютера можна схематично зобразити в такий спосіб (рис.1):
Рис. 1. Схема роботи комп'ютера
"Інформація" ліворуч й "інформація" праворуч - це різні інформації. Комп'ютер сприймає інформацію ззовні і як результат своєї роботи видає нову інформацію. Інформація, з якої працює компьютер, зветься "дані".
Комп'ютер перетворить інформацію з певних правил. Ці правила (операції, команди) заздалегідь занесені на згадку комп'ютера. У совокупности ці правила перетворення інформації називаються алгоритмом. Дані, які надходять у комп'ютер, називаються вхідними дан-ными. Результат роботи комп'ютера - вихідні дані. Таким чином, алгоритм перетворить вхідні дані у вихідні (рис. 2) :
Рис. 2. Схема роботи алгоритму
Тепер можна поставити питання: а чи може людина обробляти інформацію? Звичайно, може. Як приклад можна привести звичайний шкільний урок: учитель ставить запитання (вхідні дані), учень відповідає (вихідні дані). Найпростіший приклад: учитель дає завдання - помножити 6 на 3 і результат написати на дошці. Тут числа 6 й 3 - вхідні дані, операція множення - алгоритм, результат множення - вихідні дані (рис. 3):
Рис. 3. Схема множення цифр
Висновок: рішення математичних завдань - окремий випадок перетворення інформації. Комп'ютер (по-англійському означає обчислювач, російською мовою - ЕОМ, електронна обчислювальна машина) був створений саме для виконання математичних розрахунків.
При рішенні будь-якого математичного завдання ми становимо алгоритм рішення. Але колись ми самі й виконували цей алгоритм, тобто доводили рішення до відповіді. Тепер же ми будемо тільки писати, що потрібно зробити, але обчислення проводити не будемо. Обчислювати буде комп'ютер. Наш алгоритм буде являти собою набір вказівок (команд) комп'ютеру.
Коли ми обчислюємо яку-небудь величину, ми записуємо результат на папері. Комп'ютер записує результат своєї роботи на згадку у вигляді змінної. Тому кожна команда алгоритму повинна включати вказівку, у яку змінну записується результат.
Трактування роботи алгоритму як перетворення вхідних даних у вихідні природно підводить нас до розгляду поняття "постановка завдання". Для того щоб скласти алгоритм рішення завдання, необхідно з умови виділити ті величини, які будуть вхідними даними й чітко сформулювати, які саме величини потрібно знайти. Інакше кажучи, умова завдання потрібно сформулювати у вигляді "Дано ... Потрібно" - це і є постановка завдання.
Алгоритм стосовно до обчислювальної машини - точне приписання, тобто набір операцій і правил їхнього чергування, за допомогою якого, починаючи з деяких вихідних даних, можна вирішити будь-яке завдання фіксованого типу.
Види алгоритмів як логіко-математичних засобів відбивають зазначені компоненти людської діяльності й тенденції, а самі алгоритми залежно від мети, початкових умов завдання, шляхів її рішення, визначення дій виконавця підрозділяються в такий спосіб:
Механічні алгоритми,або інакше детерміновані,тверді (наприклад,алгоритм роботи машини, двигуна й т.п.);
Гнучкі алгоритми, наприклад стохастические, тобто імовірнісні й евристичні.
Механічний алгоритм задає певні дії, позначаючи їх у єдиній і достовірній послідовності, забезпечуючи тим самим однозначний необхідний або шуканий результат, якщо виконуються ті умови процесу, завдання, для яких розроблений алгоритм.
Імовірнісний (стохастический) алгоритм дає програму рішення завдання декількома шляхами або способами, що приводять до ймовірного досягнення результату.
Евристичний алгоритм (від грецького слова "эврика") - це такий алгоритм, у якому досягнення кінцевого результату програми дій однозначно не визначено, так само як не позначена вся послідовність дій, не виявлені всі дії виконавця. До евристичних алгоритмів відносять, наприклад, інструкції й приписання. У цих алгоритмах використаються універсальні логічні процедури й способи прийняття рішень, засновані на аналогіях, асоціаціях і минулому досвіді рішення схожих завдань.
Лінійний алгоритм - набір команд (вказівок), виконуваних послідовно в часі один за одним.
алгоритм, Що Розгалужується, - алгоритм, що містить хоча б одна умова, у результаті перевірки якого ЕОМ забезпечує перехід на один із двох можливих кроків.
Циклічний алгоритм - алгоритм, що передбачає багаторазове повторення того самого дії (тих самих операцій) над новими вихідними даними. До циклічних алгоритмів зводиться більшість методів обчислень, перебору варіантів.
Цикл програми - послідовність команд (серія, тіло циклу), що може виконуватися багаторазово (для нових вихідних даних) до задоволення деякої умови.
Допоміжний (підлеглий) алгоритм (процедура) - алгоритм, раніше розроблений і цілком використовуваний при алгоритмізації конкретного завдання. У деяких випадках при наявності однакових послідовностей вказівок (команд) для різних даних з метою скорочення запису також виділяють допоміжний алгоритм.
На всіх етапах підготовки до алгоритмізації завдання широко використається структурне подання алгоритму.
Структурна (блок-, граф-) схема алгоритму - графічне зображення алгоритму у вигляді схеми зв'язаних між собою за допомогою стрілок (ліній переходу) блоків - графічних символів, кожний з яких відповідає одному кроку алгоритму. Усередині блоку дається опис відповідної дії.
Графічне зображення алгоритму широко використається перед програмуванням завдання внаслідок його наочності, тому що зорове сприйняття звичайно полегшує процес написання програми, її коректування при можливих помилках, осмислювання процесу обробки інформації.
Можна зустріти навіть таке твердження: "Зовні алгоритм являє собою схему - набір прямокутників й інших символів, усередині яких записується, що обчислюється, що вводиться в машину й що видається на печатку й інші засоби відображення інформації ". Тут форма подання алгоритму змішується із самим алгоритмом.
Принцип програмування "зверху вниз" вимагає, щоб блок-схема поетапно конкретизувалася й кожен блок "розписувався" до елементарних операцій. Але такий підхід можна здійснити при рішенні нескладних завдань. При рішенні скільки-небудь серйозного завдання блок-схема "розповзеться" настільки , що її неможливо буде охопити одним поглядом.
Блок-схеми алгоритмів зручно використати для пояснення роботи вже готового алгоритму, при цьому як блоки беруться дійсно блоки алгоритму, робота яких не вимагає пояснень. Блок-схема алгоритму повинна служити для спрощення зображення алгоритму, а не для ускладнення.
При рішенні завдань на комп'ютері необхідно не стільки вміння становити алгоритми, скільки знання методів рішення завдань (як і взагалі в математику). Тому вивчати потрібно не програмування як таке (і не алгоритмізацію), а методи рішення математичних завдань на комп'ютері. Завдання варто класифікувати не по типах даних, як це звичайно робиться (завдання на масиви, на символьні змінні й т.д. ), а по розділі "Потрібно".
В інформатиці процес рішення завдання розподіляється між двома суб'єктами: програмістом і комп'ютером. Програміст становить алгоритм (програму), комп'ютер його виконує. У традиційній математиці такого поділу ні, завдання вирішує одна людина, що становить алгоритм рішення завдання й сам виконує його. Сутність алгоритмізації не в тім, що рішення завдання представляється у вигляді набору елементарних операцій, а в тім, що процес рішення завдання з на два етапи: творчий (програмування) і не творчий (виконання програми). І виконують ці етапи різні суб'єкти - програміст і виконавець
У підручниках по інформатиці звичайно пишуть, що виконавцем алгоритму може бути й людина. Насправді алгоритми для людей ніхто не становить (не будемо забувати, що не всякий набір дискретних операцій є алгоритмом). Людина в принципі не може діяти по алгоритму. Виконання алгоритму - це автоматичне, бездумне виконання операцій. Людина завжди діє осмислено. Для того щоб людина могла виконувати якийсь набір операцій, йому потрібно пояснити, як це робиться. Будь-яку роботу людин зможе виконувати тільки тоді, коли він розуміє, як вона виконується.
От у цьому - "пояснення й розуміння" - і криється розходження між поняттями "алгоритм" й "спосіб", "метод", "правило". Правила виконання арифметичних операцій - це саме правила (або способи), а не алгоритми. Звичайно, ці правила можна викласти у вигляді алгоритмів, але користі від цього не буде. Для того щоб людина змогла вважати за правилами арифметики, його потрібно навчити. А якщо є процес навчання, виходить, ми маємо справу не з алгоритмом, а з методом.
При складанні алгоритму програміст нікому нічого не пояснює, а виконавець не намагається нічого зрозуміти. Алгоритм розміщається в пам'яті комп'ютера, що витягає команди по однієї й виконує їх. Людина діє по-іншому. Щоб вирішити завдання, людині потрібно тримати в пам'яті метод рішення завдання в цілому, а втілює цей метод кожен по-своєму.
Дуже яскраво ця особливість людської психології - неалгоритмичность мислення - виявилася в методичному посібнику А. Г. Гейна й В. Ф. Шолоховича. У посібнику викладаються рішення завдань із відомого підручника. Рішення завдань повинні бути представлені у вигляді алгоритмів. Однак автори посібника розуміють, що якщо просто написати алгоритм рішення завдання, то розібратися в самому рішенні буде важко. Тому вони спочатку приводять "нечіткий виклад алгоритму" (тобто пояснюють рішення завдання), а потім пишуть сам алгоритм.
2. Блок-схема алгоритму
Виконавець алгоритмів - це пристрій, що виконує алгоритми. Одним з найбільш гнучких й універсальних виконавців алгоритмів, поряд з людиною, є комп'ютер.
Коли програміст становить алгоритм, то при цьому він є першим його виконавцем.
Самі основні частини комп'ютера з погляду проектування алгоритмів - це процесор й оперативна пам'ять.
Процесор є активною частиною комп'ютера й виконує дії з даними.
Оперативна пам'ять необхідна для зберігання даних й алгоритмів, з якими комп'ютер працює в цей момент.
Для успішного створення програм потрібно використати технологію програмування. Технологія складається з набору правил, які необхідно строго дотримувати.
Одним із правил є проектування програми, що полягає в попередній побудові її алгоритму. Алгоритм будується й записується на папері, досвідчені програмісти можуть тримати прості алгоритми в розумі.
Наочним зображенням алгоритмів є блок-схема. Блок-схема, або діаграма, кодує алгоритм наочними графічними засобами. Вона складається з наступних графічних елементів:
1) кружків, що кодують початок і кінець, вхід і вихід з алгоритму;
2) паралелограмів, що описують уведення й висновок даних;
3) прямокутників, у яких описується дія з даними;
4) ромбів, що визначають перевіряють алгоритмом умови.
Ці фігури з'єднуються лініями зі стрілками, що вказують послідовність дій.
Блок-схеми, як й алгоритми, також мають ієрархічну структуру. У блок-схемі, що описує алгоритм рішення якого-небудь завдання, на місце прямокутників підставляються блок-схеми алгоритмів, що описують рішення подзадач цього завдання.
При виконанні алгоритму по його схемі рухається виконавець, що перебуває в кожен момент у якімсь місці алгоритму, називаному активною крапкою. Для перевірки правильності простого алгоритму досить його протестувати, тобто пройти алгоритм, моделюючи виконавця.
При тестуванні алгоритму беруть прості вхідні дані й по них розраховують результат. Потім вручну проходять алгоритм й одержують його вихідні дані. Якщо отримані вихідні дані збіглися з розрахованим результатом, то алгоритм, може бути, побудований правильно.
Елементарний алгоритм проходження - послідовне, лінійне виконання дій. Цей елементарний алгоритм можна зобразити у вигляді блок-схеми із двох прямокутників (рис. 4). Оскільки замість прямокутника можна підставити знову цю же блок-схему, і т.д. , те послідовність прямокутників може бути як завгодно великий.
Рис. 4. Блок-схема елементарного алгоритму "проходження":
а) у найпростішому виді із двох прямокутників 1 й 2; б) замість прямокутника 2 підставлені два прямокутники 3 й 4
Елементарний алгоритм вибір — це вибір по умові однієї дії з двох. Коли виконавець доходить до ромба з умовою, то він вибирає серед двох дій. Якщо умова виконується, виконавець здійснює перехід до прямокутника дії по стрілці з позначкою «так», інакше — до дії «ні». Після виконання дії, визначеної умовою, виконавець продовжує рух далі по алгоритму.
Цей елементарний алгоритм зображається у вигляді блок-схеми з двох прямокутників і одного ромба (рис. 5). Слід мати на увазі, що замість прямокутників можна підставляти будь-які елементарні алгоритми.
Рис 5. Блок-схема елементарного алгоритму «вибір»: якщо умова виконується, то виконавець вибирає дію 1, якщо ні — то 2
Елементарний алгоритмцикл — це повторення однієї і тієї ж дії, поки виконується умова. Коли виконавець доходить до ромба з умовою, то вирішує, виконати дію або пройти мимо і більше сюди не повертатися. Якщо умова виконується, виконавець виконує дію і повертається назад на ромб з умовою. Природно, що дія винна, крім іншого, змінювати умову. Коли умова перестає виконуватися, виконавець продовжує рух далі по алгоритму.
Цей елементарний алгоритм зображається у вигляді блок-схеми з одного прямокутника і одного ромба (рис. 6). Слід мати на увазі, що замість прямокутника можна підставляти будь-які елементарні алгоритми.
Рис. 6. Блок-схема елементарного алгоритму «вибір»: поки умова виконується, дія виконується