Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Навчально-методичний посібник Частина 1 основи алгоритмізації та програмування § Алгоритм І його властивості Поняття алгоритму

Навчально-методичний посібник Частина 1 основи алгоритмізації та програмування § Алгоритм І його властивості Поняття алгоритму




Сторінка1/7
Дата конвертації19.03.2017
Розмір0.98 Mb.
ТипНавчально-методичний посібник
  1   2   3   4   5   6   7

ОСНОВИ АЛГОРИТМІЗАЦІЇ ТА ПРОГРАМУВАННЯ

Навчально-методичний посібник

Частина 1

ОСНОВИ АЛГОРИТМІЗАЦІЇ ТА ПРОГРАМУВАННЯ



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

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

Слово алгоритм походить від algorithmi – латинської форми написання імені великого математика ІХ ст. Аль Хорезмі, який сформулював правила виконання арифметичних операцій.

Арифме́тика (дав.-гр. ἀριϑμητική - мистецтво лічби, вчення про числа, від дав.-гр. αριθμός - число) - наука про числа, їх властивості й операції над ними.
Арифметичні дії є двомісними операціями на множині чисел - на вході беруть два числа (операнда), і повертають одне число як результат.
Спочатку під алгоритмом розуміли лише правила виконання чотирьох арифметичних операцій над багатоцифровими числами. Надалі це поняття стали використовувати для позначення послідовності дій, що приводять до розв’язання поставленого завдання. Під час розв’язання будь-якого завдання ми дотримуємося певної послідовності дій, тобто виконуємо інструкції відповідно до деякого алгоритму.
Інструкція - правовий акт, який створюється органами державного управління для встановлення правил, що регулюють організаційні, науково-технічні, технологічні, фінансові та інші спеціальні сторони діяльності та відносин установ, закладів, підприємств, службових осіб.
Точне дотримання інструкцій сприяє досягненню зазначеної мети – розв’язання поставленого завдання.

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

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

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

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

Прикладами формульних алгоритмів можуть бути алгоритми для розв’язання різноманітних математичних задач.

Пра́ця - цілеспрямована діяльність людей зі створення матеріальних і духовних благ, необхідних для задоволення потреб кожного індивіда і суспільства в цілому.
Блок-схема (рос. блок-схема, англ. block scheme, flowchart, block diagram, flow diagram; нім. Block-schema) - Представлення задачі для її аналізу або розв'язування за допомогою спеціальних символів (геометричних образів), які позначають такі елементи, як операції, потік, дані тощо.
Матема́тика (грец. μάθημα - наука, знання, вивчення) - наука, яка первісно виникла як один з напрямків пошуку істини (у грецькій філософії) у сфері просторових відношень (землеміряння - геометрії) і обчислень (арифметики), для практичних потреб людини рахувати, обчислювати, вимірювати, досліджувати форми та рух фізичних тіл.

За типом розрізняють лінійні, розгалужені, циклічні та змішані алгоритми.



Лінійний алгоритм – це найпростіший тип алгоритму, що містить одну серію простих команд, які виконуються послідовно.




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




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

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

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

При́стрій (англ. device, appliance, нім. Vorrichtung f, Einrichtung f) - обладнання, конструктивно завершена технічна система, що має певне функціональне призначення і за допомогою якої виконується яка-небудь робота або спрощується, полегшується певний процес.
Те́хніка (від грец. techne - мистецтво, майстерність) - сукупність засобів, створених людством для обслуговування своїх потреб виробничого і невиробничого характеру. У техніці матеріалізовані знання і виробничий досвід, накопичені людством у процесі розвитку суспільного виробництва.
Отже, виконавцями алгоритмів є людина або машина.

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


1.2. Властивості алгоритму

Любий правильно складений алгоритм має такі властивості:



  • дискретність (розрив на порції). Порція – це одна закінчена дія (команда алгоритму);

  • результативність – виконання кожної команди алгоритму має приводити до певного результату;

  • скінченність (результативність). Алгоритм має містити кінцеву кількість команд і обов’язково давати результат;
    Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.
    Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.


  • зрозумілість (формальність). Алгоритм має бути зрозумілим для виконавця, для якого він складений;

  • визначеність. Кожна команда алгоритму має бути строго визначена для виконавця. Не повинно бути «недовизначеності» у тлумаченні команди;

  • масовість. За допомогою одного й того самого алгоритму можна розв’язувати однотипні задачі і робити це неодноразово.


1.3. Приклади алгоритмів

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

Алгоритм побудови має вигляд:

1.Встановити ніжку циркуля у вершину кута А.

2.Провести коло довільного радіуса.

3.Позначити точки перетину В і С із сторонами кута.

4.Провести коло з точки В тим самим радіусом.

5.Провести коло з точки С тим самим радіусом.

6.Позначити точку D їх перетину (що не збігається з вершиною кута).

7.Провести пряму AD. Бісектрису кута побудовано.


Приклад 2. Розв’язати лінійне рівняння ax b=0.
Лінійне рівняння - рівняння, обидві частини якого визначаються лінійними функціями. Найпростіший випадок має вигляд

Пригадаємо, як ми розв’язували такі рівняння. Якщо , то маємо єдиний розв’язок якщо , то будь-які значення х є розв’язком даного рівняння; якщо тоді таке рівняння не має розв’язку.



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

1.Перевірити, чи a дорівнює нулю. Якщо так перейти до пункту 5, якщо ні – продовжити обчислення.

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

2.Розділити b на а.

3.Видати результат: «х= ».

4.Закінчити роботу.

5.Перевірити, чи дорівнює b нулю. Якщо так, перейти до пункту 8, якщо ні – продовжити обчислення.

6.Видати результат: «х – будь-яке число».

7.Закінчити роботу.

8.Видати результат: «Рівняння не має розв’язку».

9.Закінчити роботу.

Залежно від значень а і b в алгоритмі будуть виконуватися або команди 1, 2, 3, 4 (якщо ), або 1, 5, 6, 7 (якщо ), або 1, 5, 8, 9 (якщо ).

У наведеному прикладі в алгоритмі передбачено випадок, коли а=0. Якщо не досліджувати чи а і b дорівнюють нулю, то алгоритм буде значно коротшим:

1.Розділити b на a.

2.Видати результат: «х=».

3.Закінчити роботу.

Але в тому випадку, коли виявиться, що а=0, виконавець перерве роботу, тому що виконувати ділення на нуль неможливе, і не буде відомо, який з двох випадків мав місце: «рівняння не має розв’язку», або «має нескінченну множину розв’язків».

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

Логари́фм (від грец. λόγος - «слово», «відношення» і грец. ἀριθμός - «число») - математична операція, обернена піднесенню до степеня.
Причи́нність, також причи́нно-наслідко́вий зв’язо́к, причи́новість, причи́ново-наслідко́вий зв’язо́к, кауза́льність - (неформально, нестрого розуміючи) зв’язок між подією А («причиною») й іншою подією Б («наслідком»), яка необхідно настає за першою чи витікає з неї.
У цьому випадку алгоритм не має властивості масовості, тоді як у першому випадку ця властивість виконується.

Отже, під час складання алгоритмів необхідно пам’ятати про властивості алгоритмів.


Приклад 3. Виконати операцію ділення двох натуральних чисел (а:b) шляхом віднімання.
Ді́лення (також діління́)- в математиці, бінарна операція, що обернена множенню.
Необхідність - система зв'язків і відносин, що зумовлює зміну, поступальний рух, розвиток у жорстко визначеному напрямку з жорстко визначеними результатами. Іншими словами, необхідність - це такий зв'язок, що обов'язково призводить до певної події.
Склада́ння (ви́робу) - технологічний процес утворення з'єднань складових виробу (поєднання, координування і фіксація деталей у вузли, а вузлів у готовий виріб).
Відніма́ння - двомісна математична операція, обернена додаванню.
Натура́льні чи́сла - числа, що виникають природним чином при лічбі. Це числа: 1, 2, 3, 4, … Множину натуральних чисел прийнято позначати знаком N . .}
Результат ділення подати у вигляді цілої частини і залишку.

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

1.Комірку для зберігання цілої частини частки «обнулити» (k:=0).

Зберіга́ння - дія за значенням зберігати; технологічний процес.

2.Порівняти числа а і b (a=b) і якщо умова істинна, то перейти до пункту 3, інакше перейти до пункту 6.

3.Лічильник цілої частини збільшити на одиницю (k:=k 1).

4.Від а відняти b і результат помістити в комірку а (a:=ab).

5.Перейти до пункту 2.

6.Видати результат: «у комірці k значення цілої частини числа, а в комірці а – залишок від ділення».
Отже, ми розглянули приклади лінійного, розгалуженого та циклічного алгоритмів. Обмежимося цими прикладами, а ви спробуйте самі згадати відомі вам алгоритми.
1.4. Формальне виконання алгоритмів

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

Особливість, або сингулярність в математиці - це точка, в якій математичний об'єкт (зазвичай функція) не визначений або має нерегулярну поведінку (наприклад, точка, в якій функція недиференційована).
Побудова алгоритму для розв’язування завдання з будь-якої галузі потребує від людини глибоких знань у цій галузі, буває пов’язана з ретельним аналізом поставленого завдання, складними, іноді громіздкими міркуваннями.
Ана́ліз (від грец. αναλυσις - «розклад») - розчленування предмету пізнання, абстрагування його окремих сторін чи аспектів. Метод дослідження, який вивчає предмет, уявно чи реально розчленовуючи його на складові елементи, як-от частини об'єкта, його ознаки, властивості, відношення, відтак розглядає кожен з виділених елементів окремо в межах єдиного цілого; протилежний метод - синтез.
На пошуки алгоритму розв’язання деяких завдань вчені витравчають дуже багато років.

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

Міркування - зіставлення думок, пов’язання їх задля відповідних висновків, логічне мислення. Можна розглядати міркування як аналіз і синтез даних, та їхню оцінку. Хоча знання фактів і є точкою відліку у вивченні суспільних наук, людина також повинна мати здатність до логічного мислення-міркування, адже саме міркування наповнює факти, проблеми і поняття змістом: міркуючи над засвоєним знанням, людина приходить до повнішого розуміння предмета. Міркування є також предметом логіки, яка вказує нам правила, закони або норми, яким повинне підкорятися наше мислення для того, щоб бути істинним.
Найпростіші (лат. Protozoa, від дав.-гр. πρῶτος «перший» і ζῷα, форми множини ζῷον - «жива істота») - парафілетична або поліфілетична група одноклітинних або колоніальних еукаріотів, які мають гетеротрофний тип живлення.
На цьому положенні й грунтується робота автоматичних пристроїв.
Отже, наведемо приклади неформального і формального виконання алгоритму.

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

1.Помножити задумане число на 5.

2.Додати 8.

3.Суму помножити на 2.

За отриманим результатом необхідно вгадати задумане число. Розв’язання цього завдання виконується за допомогою рівняння (х*5 8)*2=а,

де х – задумане число, а – отриманий результат.



Приклад 2. «Угадування» х можна доручити виконавцеві, який зовсім не знає умови задачі. Але йому достатньо дати такий алгоритм:

1.Відняти від результату 16.

2.В отриманій різниці відкинути крайню праву цифру. Отримане число й буде шуканим.

Як бачимо, у другому випадку (приклад 2) виконання алгоритму є формальним.

Наведемо ще один приклад формального виконання алгоритму.

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

1*9=9 (0 9=9)

2*9=18 (1 8=9)

3*9=27 (2 7=9)

4*9=36 (3 6=9)

5*9=45 (4 5=9)

6*9=54 (5 4=9)

7*9=63 (6 3=9)

8*9=72 (7 2=9)

9*9=81 (8 1=9)


Отже, першокласник має пам’ятати, що сума цифр у результуючому числі завжди має дорівнювати 9.
Додавання - бінарна арифметична операція, суть якої полягає в об'єднанні математичних об'єктів.
При цьому цифра десятків змінюється від 0 до 8, а цифра одиниць – від 9 до 1.
Контрольні запитання

1.Що таке алгоритм? Наведіть власні приклади алгоритмів.

2.Назвіть форми запису алгоритмів і їх типи.

3.Назвіть властивості, які повинен мати алгоритм, і поясніть їх.

4.Що ви розумієте під формальним виконанням алгоритму? Наведіть приклад формального виконання алгоритму.
Вправи

1.Складіть алгоритм вашого розпорядку дня.

2.Складіть алгоритм приготування якої-небудь страви.

3.Складіть алгоритм знаходження більшого з двох чисел.

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

Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних цілих чисел - найбільше натуральне число, на яке ці числа діляться без остачі.


§2. Алгоритмічна мова
2.1. Поняття алгоритмічної мови

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

Си́нтаксис (дав.-гр. σύνταξις - "побудова, порядок, складання", від σύν - "з, разом" і ταξις - "впорядкування") - розділ граматики, що вивчає граматичну будову словосполучень та речень у мові.
Алгоритмі́чна мо́ва 1. формальна мова, призначена для записування алгоритмів. Використання алгоритмічної мови базується на можливості формального визначення правил конструювання алгоритмів. При формальному описанні алгортимів істотна роль належить вибору способу запису (кодування) оброблюваної інформації та задання алгоритмічних приписів - елементарних кроків алгоритму, із яких він конструюється. 2. Довга назва мови програмування АЛГОЛ
Мо́ва програмува́ння (англ. Programming language) - це штучна мова, створена для передачі команд машинам, зокрема комп'ютерам. Мови програмування використовуються для створення програм, котрі контролюють поведінку машин, та запису алгоритмів.
У курсі середньої школи введено навчальну алгоритмічну мову. І це невипадково, бо вона увібрала в себе все те спільне, що властиве будь-якій мові програмування. Після її вивчення легко опанувати будь-яку мову програмування високого рівня. Дехто вважає, що вивчати навчальну мову – це гаяти час, однак з цим можна не погодитися й на це є причини. По-перше, вона україномовна, по-друге, вона структурна, а це привчає програміста-початківця до культури програмування, по-третє, мова легко вивчається і є своєрідним трампліном до вивчення будь-якої мови програмування, наприклад, Бейсик, Паскаль, Сі тощо.
Трамплін (фр. tremplin, від іт. trampolino, від trampolo - ходулі), спортивна споруда (пристрій) для збільшення дороги польоту тіла спортсмена при стрибках на лижах, у воду та у гімнастиці.
Дамо визначення алгоритмічній мові.



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


2.2. Алфавіт мови

Алфавіт мовице символи, які дозволено до використання в мові.

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



  • 33 літери українського алфавіту;

  • 26 латинських літер (від A до Z );

  • 10 арабських цифр;
    Користува́ння - добування з речей їхніх корисних властивостей (наприклад, збирати врожай, вживати продукти харчування, носити одяг і взуття). Одна з трьох класичних правомочностей власника (нарівні з володінням і розпорядженням).
    Ара́бська мо́ва (اللغة العربية‎‎; al-luġa 'l-ʿarabiyya) - найпоширеніша семітська мова семіто-хамітської родини мов, якою розмовляють у західній Азії і північній Африці близько 240 мільйонів (як рідною) та ще 50 мільйонів (як другою) осіб.
    Озна́чення, ви́значення чи дефіні́ція (від лат. definitio) - роз'яснення чи витлумачення значення (сенсу) терміну чи поняття. Слід зауважити, що означення завжди стосується символів, оскільки тільки символи мають сенс що його покликане роз'яснити означення.
    І́ндо-ара́бська' або інді́йська систе́ма чи́слення' є позиційною десятковою системою числення розроблена у 1-4 століттях індійськими математиками. Цифри виникли в Індії і в 10-13 ст. були занесені в Європу арабами, через що часто згадуються як «ара́бські».


  • 28 спеціальних знаків (?, !, #, $, % тощо).

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


2.3. Синтаксис мови

Синтаксис мовице правила написання команд, службових слів, розділових знаків.
Розділо́ві зна́ки, або зна́ки пунктуа́ції - сукупність графічних знаків, що не належать до алфавіту даної мови, а служать засобом відображення тих ознак (сторін) писемної мови, які не можуть бути передані літерами та іншими писемними позначеннями - цифрами, знаками рівності, подібності тощо.
Набі́р си́мволів, кодува́ння си́мволів, табли́ця си́мволів (англ. character set, character encoding) - певна таблиця кодування скінченної множини символів. Така таблиця зіставляє кожному символу послідовність довжиною в один або більше байт.
Службові слова, неповнозначні (систематичні слова - вільні морфеми, що інтонаційно об'єднуються зі словом, словосполученням чи реченням і виражають, подібно до словотвірних і словозмінних (флексійних)) зв'язаних морфем, різні стосунки між повнозначними словами й реченнями, об'єднуючи їх або надаючи їм різних значеннєвих відтінків.

Розділовими знаками можуть бути такі символи:



  1. Каталог: book
    book -> Реферат з інформатики Об’єктно-орієнтоване програмування у порівнянні з традиційними способами програмування ооп має ряд переваг. Головна з них полягає в тому, що ця концепція найбільшою мірою
    book -> “Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010
    book -> Е. М. Пройдаков, Л. А. Теплицький
    book -> Десять кроків до професійної українізації програм
    book -> Програма Microsoft Office Publisher 2007 Пригадайте!
    book -> Програма Microsoft Office Publisher 2007 Пригадайте!
    book -> Методичні вказівки до лабораторної роботи №3 з дисципліни «Веб проектування»
    book -> Людина. Комп’ютер. Комунікація
  1   2   3   4   5   6   7