Поняття алгоритму. Типи, властивості та структура алгоритмів. Побудова алгоритмів.

Первомайський ЦНТТУМ

Гурток «Сучасні технології програмування»

Керівник гуртка Семенова Олена Анатоліївна

Розробка заняття на тему:

Тема: «Поняття алгоритму. Типи, властивості та структура алгоритмів. Побудова алгоритмів.»

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

Обладнання: ПК, ПЗ — текстовий редактор.

Хід заняття

1. Організаційний момент та розминка.

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

 Для початку знайдіть на клавіатурі букви О та А  - на них ви можете відчути рисочки. Це так звані «сліпі» літери. Покладіть на них вказівні пальці відповідно: лівої руки на букву А, правої руки — на букву О. Тепер розташуйте інші.. Чотири пальці правої руки від вказівного займають позицію: О, Л, Д, Ж. Відповідно, пальці лівої руки від вказівного займають позиції А, В, І, Ф. Великі пальці обох рук знаходяться над пробілом. Запам“ятайте цю позицію і ось вам перша порада: якщо ви хочете засвоїти техніку сліпого набору, то починаючи з цього момента старайтесь не дивитись на клавіатуру.

 Зараз приберіть руки з клавіатури і не дивлячись на неї, покладіть пальці у початкову позицію  А, В, І, Ф    О, Л, Д, Ж. Потренуйтесь так 2-3 рази, руки та пальці з часом самі запам“ятають її.

 Для розминки сірих клітинок мозку давайте складемо 12 слів  із цими  літерами початкової позиції: «ф, і, в, а, о, л, д, ж». Слова мають бути зі змістом, бажано, щоб це не були власні імена. Звичайно, букви можуть повторюватись.

 Складайте та називайте їх по черзі, а я буду записувати їх на дошці:

ліво віл лід вода овал жало вада влада лад діва  віола (молодці!) вілла

 Чудово!

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

 Вийшло? Добре. Тепер натисніть пробіл  великим пальцем лівої або правої руки, як вам зручніше. І далі запишіть так само останні 11 слів — через пробіли, у рядок. Нагадую — не дивлячись на клавіатуру.

 Для кращого запам“ятовування наберіть ще два таких рядка.

 Перевіряємо правильність набору та ставимо оцінки своїй роботі. Пам“ятаємо, що ми чесні :).

2.  Основна частина. Розгляд нової теми.

 Так само, як в школі ви спочатку писали палички та гачечки, почнемо ми теж  знайомитись із основами програмування від самих простих речей. Одразу скажу, що немає в програмуванні незрозумілих або нелогічних термінів. Будь-які нові для вас слова завжди намагайтесь розглядати із точки зору логіки. Знаєте, чим відрізняються поняття «запам“ятати» та «зрозуміти»? Окрім звучання, звичайно :). Чудово, що ви розумієте різницю :). Вони відрізняються тим, що у слова «запам“ятав» є дуже активно діюче з часом протилежне - «забув».  :) Тобто, якщо ви просто «запам“ятали» щось, з часом ви можете це забути. Але якщо ви «зрозуміли» це «щось» — ви не зможете це забути. Наприклад, ви можете забути суму чисел 121+227 :) . Але якщо ви розумієте, як вона отримується, ви завжди зможете її назвати, так? :)

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

 А походження слова «алгоритм» пов“язують з іменем арабського математика ІХ сторіччя Абу Абдулла Абу Джафар Мухаммад ібн Муса аль-Хорезмі. Його ім“я свідчить про те, що він був родом із стародавньої держави Хорезм, яка була розташована в Середній Азії приблизно на територіях нинішніх Узбекістану та Туркменістану. Аль-Хорезмі був дуже освіченою людиною, він очолював в Багдаді бібліотеку «Будинку мудрості», свого роду Академію тих часів. Саме він вперше виділив алгебру як самостійну дисципліну і взагалі, був великим не лише математиком, а й географом, істориком, астрономом та написав багато книг, що вважались підручниками тих часів. Погляньте на фото:

 Отаку картинку показує нам Вікіпедія як зразок рукописної сторінки Алгебри Аль-Хорезмі. Книга мала назву «Кітаб аль-джебр валь-мукабала», що в перекладі означає «Коротка книга доповнення і протиставлення». Але скорочено її стали називати «Алгеброю». І хоча справжній арабський текст цього рукопису втрачено, зміст відомий у латинському перекладі, а єдиний рукопис зберігається в Кембріджі. Переклад починається словами «Dixit Algorizmi» (сказав Алгорізмі), тому оскільки цей твір став дуже популярним у Європі, ім“я Алгорізмі поступово стало прозивним.

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

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

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

1. Словесна. Який приклад ви можете навести? Спробуйте скласти алгоритм «Ранкові дії до виходу у школу» :)

2. Псевдокод. Або його ще називають «програмний». Це запис алгоритму на мові програмування. Ми будемо використовувати цю форму постійно :).

3. Схемна або «графічна». Ця форма застосовується для кращої візуалізації алгоритму. Ми їх дуже часто бачимо у повсякденному житті. Приклади  можете навести? Ні, схема станцій метрополітена не є алгоритмом. Можете відповісти, чому? Тому що не містить чіткої послідовності дій, власне, там взагалі немає дій. Лише показана будова ліній руху. Так, схема виходу із будинку при пожежі є інструкцією:  вона містить чітку послідовність дій, що ведуть до розв“язання конкретної цілі, тому може вважатись алгоритмом.

 До речі, для зручності та більшої наочності графічного запису блоки прийнято позначувати різними геометричними фігурами:

      Початок

      Кінець

      Введення даних

      Виведення результату

      Обчислення

      Умова    

      З“єднання блоків

 Думаю, що ви зустрічали подібні схеми.

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

 Давайте розглянемо та познайомимось із кожним поближче.

 Лінійний — це алгоритм, всі етапи якого виконуються одноразово, у суворій послідовності. Прикладом може бути, наприклад, класичний: заварювання чаю :), або інший: прання білизни в пральній машині. В кожного дома є пральна машина? Знаєте, як випрати купу своїх шкарпеток? Ну, то спробуйте зараз скласти лінійний алгоритм цього процесу:). Форма запису? Обирайте зручнішу для вас.

 Ідемо далі….  В інтернеті я знайшла ось таку схему:

 Подивіться на неї та скажіть, якого типу, на вашу думку, цей алгоритм? На ваш погляд, чи правильно він складений?

 Із формальної точки зору цей лінійний алгоритм складено без помилок. А як з точки зору правильного розв“язання поставленої задачі? Що є правильним результатом розв“язання даної задачі? Так, живий та неушкоджений пішохід на іншому боці дороги :). Тому даний алгоритм можна вважати правильним лише у частковому випадку умов задачі: немає перешкод.

 А що може заважати? Небезпека — тобто автомобіль, що швидко наближується.

 Отже, у нашої схеми розв“язання з“являється що? Правильно, умова. І щоб алгоритм розв“язання задачі став більш точним, він має додати в себе розгалудження згідно умовам. Спробуйте покращити цей алгоритм. Дивимось, що вийшло…

     Початок

     Подивитись наліво

     Є автомобіль

  так       ні

 Чекаємо      Переходимо до середини

     Подивитись направо

     Є автомобіль

  так       ні

 Чекаємо      Переходимо дорогу

     Кінець

 Отакі алгоритми, де порядок виконання дій залежить від певної умови називаються алгоритмами із розгалудженням.

 Тепер поглянемо знову на нашого пішохода та його перехід дороги. :) Давайте перейдемо дорогу разом із ним за вашим алгоритмом. Так, чекаємо і йдемо...

 А якщо за автомобілем їде ще один? :) Ваші дії? Так, стоїмо та чекаємо :). Тоді дивимось ще раз.. Здогадались, до чого я веду? На жаль, і цей алгоритм виявився недосконалим для повного та щасливого результату розв“язання задачі. Спробуєте зробити алгоритм бездоганним? :) Чудово! Алгоритм тепер бездоганний. Будь-який пішохід, який ним скористається, перейде дорогу живим та здоровим :).

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

 Отак із простого лінійного алгоритму в нас вийшов… Змішаний. Звичайно, як і в реальному житті, все змішується. І форми та типи алгоритмів не є виключенням.

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

 Дякую Вам за активність і увагу. Бажаю успіхів і до зустрічі на наступному занятті!