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

Алгоритми і способи їх опису

ІІІ. Вивчення нового матеріалу.

ІІ. Активізація базових знань.

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

Хід уроку

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

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

2. Що розуміється під знаковою моделлю?

3. Що таке математична та інформаційна модель? У чому різниця між ними?

4. Що таке комп'ютерна модель?

5. Які унікальні можливості дає комп'ютерне моделювання?

6. Назвіть основні етапи створення комп'ютерної моделі.

7. Що таке комп'ютерні експерименти?

8. Назвіть тип програмного забезпечення, яке використовується для реалізації ком­п'ютерних моделей.

Термін «алгоритм» походить від назви середньоазіатського міста Хорезм. У цьому місті в IX ст. жив математик і астроном Мухамед, який сформулював правила чотирьох арифметичних дій. Арабський варіант його імені Аль-Хорезмі, що в Європі записувався латиною як Algorithmi, і став основою терміна "алгоритм". Однак пізніше під словом алгоритм стали розуміти правила зна­ходження найбільшого спільного дільника, які були викладені ще в працях вели­кого давньогрецького математика Евкліда (III ст. до н.е.). За наших часів понят­тя алгоритму було узагальнено, і словом "алгоритм" стали позначати опис будь-якої послідовності дій. Поняття алгоритму є одним із фундаментальних у сучасній математиці й інформатиці.

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

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

До слова «алгоритм» близькі за значенням слова: спосіб, рецепт. Однак алгоритми в інформатиці - це не тільки рецепти розв'язання задач. Алгоритми розробляються, насамперед, із метою автоматизації дій виконавця (див. наступ­ний пункт).

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

Розглянемо як приклад алгоритм Евкліда, вигаданий ним для знаходження найбільшого спільного дільника (НСД) двох натуральних чисел m і n. Відомо, що НСД може бути отриманий шляхом послідовного ділення спочатку більшого числа на менше, потім меншого числа на отриманий залишок, першого залишку на другий залишок і т.д. Ділення триває доти, доки у залишку не утвориться нуль. Останній дільник і є НСД. Наведемо приклад знаходження НСД для пари чисел - 66 і 18:

66:18 = 3 +(12)

18:12 = 1 + (6)

12:6 = 2

Тут у дужках записаний залишок від ділення. В останній рівності залишок відсутній, тому НСД дорівнює дільнику, тобто 6.

Алгоритм розв'язання задачі про НСД для пари чисел т і п записується у такий спосіб:

1. Якщо m > n, то перейти до 3., інакше перейти до 2.

2. Якщо n > m, то перейти до 4., інакше перейти до 5.

3. Від m відняти n і вважати цю різницю новим значенням m. Перейти до 1.

4. Від n відняти m і вважати цю різницю новим значенням n. Перейти до 1.

5. Вважати, що НСД дорівнює m. Кінець.

Зверніть увагу, що пункти 3, 4 цього алгоритму виконуються лише тоді, коли m > n або у випадку n > m, тобто коли m не дорівнює n. Останній пункт 5 виконується лише тоді, коли n = m (залишок дорівнює нулю).

Дата добавления: 2014-01-04