Свойства на алгоритмите. Видове алгоритми Изготвил: Ралица Иванова Андреева



Дата31.12.2017
Размер106.94 Kb.
#38428


Свойства на алгоритмите. Видове алгоритми

Изготвил: Ралица Иванова Андреева

СОУ „Черноризец Храбър” – Велики Преслав

Вид на урока: За нови знания
Продължителност на урока: 90 минути
Предмет: Информатика
Клас: 9
Понятия и термини за темата:

алгоритъм, линеен алгоритъм, разклонен алгоритъм, цикличен алгоритъм, подалгоритъм, константа, променлива, блок-схема, език за програмиране, транслатор, интерпретатор, компилатор, оператор (команда), програма, логическо условие, цикъл, масив, списък, поле, запис, файл.



Понятия и термини за урока:

Стари понятия и термини:

Понятие

Изясняващо определение

Въведено за първи път

Използвано за последен път

Алгоритъм

Всяка точно описана последователност от действия, чрез прилагането на които един изпълнител може да реши конкретна задача от разглеждан клас задачи.

Алгоритми

Алгоритми

Блок-схема

Описание на алгоритъм, чрез свързани със стрелки геометрични фигури с определен смисъл.

Алгоритми

Алгоритми

Нови понятия и термини:

Термин

Изясняващо определение

Дискретност

Свойство на алгоритмите – всеки алгоритъм се състои от краен брой последователни указания.

Яснота

Свойство на алгоритмите – всяка текуща стъпка е разбираема за изпълнителя и той може да я изпълни, както и еднозначно да определи коя е следващата стъпка.

Формалност

Свойство на алгоритмите – изпълнителят трябва да работи формално, да изпълнява указанията, докато стигне до указание за край на алгоритъма.

Определеност

Свойство на алгоритмите – при всяко изпълнение на алгоритъма с едни и същи данни се получава един и същи резултат.

Масовост

Свойство на алгоритмите – даден алгоритъм може да се прилага за решаване на коя да е задача от клас еднотипни задачи

Крайност

Свойство на алгоритмите – изпълнението на алгоритъма трябва да завърши след краен брой стъпки.

Линеен алгоритъм

Алгоритми, при които действията се изпълняват последователно по реда, в който са зададени, се наричат линейни

Разклонен алгоритъм

Алгоритъм, чието изпълнение се разделя на различни последователности от действия в зависимост от верността на дадено условие, се нарича разклонен

Цикличен алгоритъм

Алгоритъм, в който дадена група от действия се изпълнява необходимия брой пъти, в зависимост от верността на дадено условие, се нарича цикличен

Очаквани резултати за темата:

Ученикът знае какво е алгоритъм, какви са неговите характеристики и как могат да бъдат представяни. Познава елементи на езика за програмиране Паскал.

Ученикът може да преведе на езика за програмиране формално специфициран алгоритъм;


  • Използва оператори за присвояване, вход, изход, разклоняване, цикъл;

  • Структурира програмата.

Ученикът работи с конкретна среда за програмиране – въвежда, настройва и изпълнява програми, като реагира адекватно на съобщенията на средата.

Ученикът съставя програми на език за програмиране, реализиращи прости алгоритми за обработка на данни – линейни, разклонени и циклични алгоритми.

Ученикът познава структурата масив и основните алгоритми за обработката й.

Ученикът реализира чрез програма алгоритми за: въвеждане и извеждане на елемент, минимален и максимален елемент, сума от елементи.

Ученикът знае основните етапи при решаването на задачи с компютър.

Очаквани резултати за урока:

Ученикът знае свойствата на алгоритмите.

Ученикът познава различните видове алгоритми – линеен, разклонен, цикличен.

Ученикът може да съставя алгоритми



Междупредметни връзки: математика, логика


Използвана литература:

1. П. Асенова, Емил Келеведжиев, Информатика 9 клас, Регалия 6, София, 2001

2. П. Бърнев, Г. Тотков, Р. Донева, Вл. Шкуртов, К. Гъров, Информатика 9 клас, Летера, Пловдив, 2001

3. Л. Иванова, В. Вазова, Б. Танева, И. Стоянов, Информатика 9 клас – Първа част, Коала Прес, Пловдив, 2006.


С този урок ще се запознаем със свойствата на алгоритмите и различните видове алгоритми. Ще се научим да съставяне алгоритми.


В наши дни значението на алгоритмите непрекъснато нараства и те се прилагат буквално навсякъде. Най-нови примери за навлизането им в съвременния живот са приетите напоследък в някои държави закони за цифровия подпис (включително и в България от 2001 г.). Освен това познаването на алгоритмите стимулира и развива абстрактно, логическо и алгоритмично мислене и дисциплинира мисълта.
Алгоритъма на Евклид за намиране на най-голям общ делител:

Да се намери НОД на числата 32 и 56 и да се направи словесно описание на алгоритъма.

Решение:56 > 32  56 – 32 = 24;

32 > 24  32 – 24 = 8;

24 > 8  24 – 8 = 16;

16 > 8  16 – 8 = 8;

8 = 8  НОД на 32 и 56 е 8.
Вход – числата a, b. Изход – НОД на a, b.

Последователността от действия е следната:



  1. Въведете и запомнете числата a и b;

  2. Ако a b, изпълнете стъпка 3, в противен случай – стъпка 5.

  3. Ако a > b, то намалете стойността на a с b, в противен случай намалете стойността на b с a.

  4. Изпълнете стъпка 2.

  5. Съобщете стойността на a като резултат.

  6. Прекратете работа.




  1. Свойства на алгоритмите;

Алгоритмите имат редица характерни свойства. Ще разгледаме най-важните.

    1. Дискретност

Всеки алгоритъм се състои от краен брой указания, а изпълнението му става в последователни различими една от друга стъпки..

    1. Яснота;

Яснотата (разбираемост) на алгоритъма означава, че всяка текуща стъпка е разбираема за изпълнителя и той може да я изпълни, както и еднозначно да определи коя е следващата стъпка от алгоритъма, която трябва да изпълни.

    1. Формалност;

От изпълнителя не се изисква да знае каква цел се преследва с изпълнението на алгоритъма – той трябва да работи формално, да изпълнява указанията, докато стигне до указание за край. Свойството формалност позволява изпълнителят на един алгоритъм да бъде и автомат (лишен от разум и от възможността да осъзнава извършената от него работа).

    1. Определеност;

Определеност на алгоритъма означава, че при всяко изпълнение на алгоритъма с едни и същи данни се получава един и същи резултат.

    1. Масовост;

Даден алгоритъм може да се прилага за решаване на коя да е задача от клас еднотипни задачи.

    1. Крайност;

Изпълнението на алгоритъма трябва да завърши след краен брой стъпки. Алгоритми, изпълнението на които продължава неопределено (например броене, без да е определено кога ще завърши) не представляват практически интерес.
2. Видове алгоритми;

В зависимост от последователността на действията, които се изпълняват, алгоритмите биват три вида.



2.1. Линейни алгоритми;

Алгоритми, при които действията се изпълняват последователно по реда, в който са зададени, се наричат линейни.

Задача 1 „Да се направи словесно описание и блок-схема на алгоритъм, по който се намира лицето на кръг S по зададен радиус R”.

Решението започва с математически модел да задачата (S = π R2), определя се входа и изхода на алгоритъма, след което се прави словесното описание. Тази задача се реализира чрез линеен алгоритъм.
Математически модел: S = π R 2

Словесно описание:

Вход: R Изход: S


  1. Въведете и запомнете радиуса R;

  2. Пресметнете лицето по формулата S = π R 2;

  3. Изведете лицето S като резултат;

  4. Прекратете работа.

Блок-схема:

2.2. Разклонени алгоритми.

В практиката често се сблъскваме със ситуации, при които трябва да се вземе решение и да се изпълни едно или друго действие. Такива ситуации се описват чрез разклонени алгоритми.



Алгоритъм, чието изпълнение се разделя на различни последователности от действия в зависимост от верността на дадено условие, се нарича разклонен.

Задача 2 „Да се направи словесно описание и блок схема на алгоритъм, по който се намира лицето на кръг по зададен радиус. Да се изведе подходящо съобщение в случай, че въведената стойност за радиуса R не е положително число.”

Определя се входа, изхода и условието, което ще разклонява процеса.
Математически модел: S = π R 2

Словесно описание:

Вход: R Изход: S или съобщение за грешка


  1. Въведете и запомнете радиуса R;

  2. Ако R ≤ 0, изведете съобщение

„Некоректни данни” и преминете към стъпка 5;

  1. Пресметнете лицето

по формулата S = π R 2;

  1. Изведете лицето

S като резултат;

  1. Прекратете работа.



не


да


2.3. Циклични алгоритми

Много често се налага някои действия да се изпълняват многократно. Когато тези повторения трябва да се зададат едно след друго, този многократен запис може да се рационализира, като се използва алгоритъм за цикличен (повтарящ се) процес



Алгоритъм, в който дадена група от действия се изпълнява необходимия брой пъти, в зависимост от верността на дадено условие, се нарича цикличен.

Алгоритъм на Евклид за намиране на най-голям общ делител.

Този алгоритъм е цикличен защото има повторение на определени действия.


Задача 3

Вход – числата a, b. Изход – НОД на a, b.



  1. Въведете и запомнете числата a и b;

  2. Ако a b, изпълнете стъпка 3, в противен случай – стъпка 5.

  3. Ако a > b, то намалете стойността на a с b, в противен случай намалете стойността на b с a.

  4. Изпълнете стъпка 2.

  5. Съобщете стойността на a като резултат.

  6. Прекратете работа.

Блок-схема:



да да


не не


Въпрос

Очакван отговор

Кои са основните свойства на алгоритмите?

Дискретност, яснота, формалност, определеност, масовост, крайност.

С какви видове алгоритми се запознахме?

Линеен алгоритъм, разклонен алгоритъм, цикличен алгоритъм.

Кой алгоритъм е разклонен?

Алгоритъм, чието изпълнение се разделя на различни последователности от действия в зависимост от верността на дадено условие, се нарича разклонен

Кой алгоритъм е цикличен?

Алгоритъм, в който дадена група от действия се изпълнява необходимия брой пъти, в зависимост от верността на дадено условие, се нарича цикличен



Свойства на алгоритмите. Видове алгоритми


  1. Свойства на алгоритмите:

    1. Дискретност,

    2. Яснота;

    3. Формалност;

    4. Определеност;

    5. Масовост;

    6. Крайност.

  2. Видове алгоритми:

    1. Линеен алгоритъм;

    2. Разклонен алгоритъм;

    3. Цикличен алгоритъм.




Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница