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

1 Алгоритм

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

3 У своїй практичній діяльності люди постійно мають справу із алгоритмами (послідовностями вказівок, інструкціями, правилами тощо). Для прикладу можна назвати приготування кулінарної страви згідно з рецептом, користування міжміським телефоном-автоматом, пошук слова у словнику, розвязування квадратного рівняння.

4 Властивості алгоритмів Скінченність. Виконання кожного алгоритму повинно завершуватись за скінченне число кроків. Результативність. Виконання алгоритму завжди повинно призводити до певного результату. Воно не може закінчуватись невизначеною ситуацією або ж не закінчуватися взагалі.

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

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

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

8 Для того, щоб краще зрозуміти, що таке алгоритм, опишемо процес приготування бутерброду, або іншими словами – алгоритм приготування бутерброду: Відріж хліб Намасти маслом Смачного

9 Спроба 2 Відріж 1 шматочок хліба Намасти маслом одну сторону Смачного

10 Спеціально для *… компютера 1) В праву руку візьми за ручку ніж, в лівій руці тримай хліб. 2) Гострою стороною ножа відріж від хліба шматочок товщиною 1см, а довжиною 10 см. Все відклади в сторону. 3) Візьми масло. 4) Гострою стороною ножа намасти шматочок хліба маслом з однієї сторони. 5) Кінець роботи.

11 Бургомістр і алгоритм В одному німецькому місті бургомістр вночі зіштовхнувся з перехожим і набив собі гулю. Вранці він написав наказ: «Всім мешканцям міста вночі ходити з ліхтарями». Ввечері він пішов перевірити, як виконується його наказ. І знову набив гулю. «Чому ти без ліхтаря?» «Ось він». «Чому він без свічки?» «Наказу не було».

12 Наступного дня з'явився наказ: «У ліхтарях повинна бути свічка». Знову бургомістр пішов перевіряти виконання свого наказу і знову набив гулю. «Чому без ліхтаря?» «Ось він». «Чому ліхтар без свіч­ки?» «Ось вона». «Чому вона не запалена?» «Не було наказу».

13 І тільки на третій день вийшов вичерпний наказ: перехожі в темну пору доби повинні ходити з ліхтарями, у ліхтарях повинна бути свічка, свічка повинна бути запалена.

14 Базові алгоритмічні структури Слідування Розгалуження Повтор

15 Слідування Операція слідування подається у вигляді послідовності двох (або більше) простих операцій, що виконуються одна за одною. Якщо алгоритм складається лише з послідовності простих операцій, його називають простим або лінійним алгоритмом.

16 Розгалуження (вибір) Операція розгалуження – це вказівка виконати одну з двох команд: команду1 або команду2, залежно від істинності чи хибності деякого твердження Р. Якщо твердження Р істинне, то виконується команда1. Якщо твердження Р хибне, то виконується команда2. Окремим випадком розгалуження є неповне розгалуження, коли у разі хибності твердження Р ніякі операції взагалі не виконуються. такні умова

17 Повторення (цикл) Повторення команди або групи команд певну кількість разів або до виконання певної умови За допомогою комбінацій цих трьох базових структур можна подати будь- який алгоритм. дії

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

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

20 «Обчислити шлях за швидкістю і часом руху» Словесний запис алгоритму задачі буде таким: 1. Ввести швидкість v і час руху t. 2. Обчислити шлях за формулою S = v·t. 3. Вивести шлях S.

21 Алгоритм «Відгадай число»: 1. Задумай будь-яке число. 2. Додай до нього Від результату відніми Відніми від результату задумане число. 5. Одержано число 5.

22 «Як перевезти по одному через річку без втрат вовка, козу і капусту»: 1. Переправити на той берег козу, вовка залишити з капустою; 2. Повернутись, взяти вовка, переправитись з ним до кози; 3. Забрати козу і повернутись назад до капусти; 4. Залишити козу, забрати і перевезти капусту до вовка; 5. Повернутись і забрати козу.

23 Алгоритм «Користування телефоном»: 1. зняти трубку; 2. почувши гудок, набрати номер; 3. якщо з'єднання відбулось говорити; 4. якщо з'єднання не відбулось покласти трубку і перейти до п.1.

24 Алгоритм знаходження найбільшого спільного дільника (НСД) двох натуральних чисел вперше описав Евклід: 1. Порівняй числа а і b. 2. Якщо а = b, то а найбільший спільний дільник. 3. Якщо а > b, то замінити а на a – b. 4. Якщо а < b, то замінити b на b – a. 5. Перейти до п. 1.

25 Домашнє завдання: блок-схема Візьми лопату Постав лопату Візьми відро Постав відро Візьми саджанець Постав саджанець Викопай ямку Засип ямку Постав у ямку Полий водою Пройди вперед Є кілька умов Є кілька умов: В руках у садівника може бути лише 1 предмет Перед засипанням ямки із саджанцем потрібно полити його водою Після засипання ямки із саджанцем потрібно полити його водою – щоб він розквітнув Перед тим, як перейти до наступного саджанця – не забути лопату!

26 Для компютера мова складається з нулів та одиниць. Використання такої мови для складання програм є неефективним. Тому використовуються спеціальні мови – мови програмування.

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

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

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

30 Наприклад, службовими словами для мови Паскаль є: and, or, not, program, label,const, type,var, procedure, function, array, record, set, file, begin, end, if, then, else, for, to, downto, do, repeat, until, while, case, goto тощо.

31 Ідентифікатор - це послідовність латинських літер, цифр і знаку підкреслення, яка розпочинається з латинської літери. У мові Паскаль максимальна довжина ідентифікатора становить 127 символів. У ідентифікаторах не можна використовувати знак пробілу.

32 Структура програми на мові Паскаль Program назва; Var розділ опису змінних; Begin команди; End.

33 Найпростіша програма Program simple; Begin Write (hello); End.

34 Презентацію підготувала вчитель інформатики гімназії Сихівська Пасічник Оксана Використано матеріали підручника Алгоритми та програми Є.А. Шестопалова