Алгоритми і програми

1.

2.

План заняття
1. Інформаційна модель
2. Історична довідка
3. Поняття алгоритму
4. Приклади алгоритмів.
5. Виконавці алгоритмів
6. Що таке програма?.
7. Властивості алгоритмів.
8. Типи алгоритмів
9. Способи опису алгоритмів.
10. Основні блоки графічного опису алгоритмів
11. Приклади опису алгоритмів
12. Етапи розв’язування задач на комп’ютері.
Мови програмування

3.

Модель – це штучно створений людиною
абстрактний або матеріальний об’єкт.
Приклади моделей:
модель Сонячної системи
модель
Землі
модель атома
модель ядерної
реакції

4.

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

5.

КЛАСИФІКАЦІЯ
МОДЕЛЕЙ
ЗА ГАЛУЗЮ
ВИКОРИСТАННЯ
З УРАХУВАННЯМ
ФАКТОРА ЧАСУ
ЗА СПОСОБОМ
ПРЕДСТАВЛЕННЯ

6.

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

7.

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

8.

Матеріальні – це предметне
відображення об’єкта зі збереженням
Інформаційні
геометричних та фізичних властивостей Наприклад, іграшки,
географічні карти, глобус це матеріальні моделі реально існуючого
об’єкта
Інформаційні – це сукупність інформації, що характеризує
властивості та стан об’єкта, процесу, явища, а також взаємодію
із зовнішнім світом.
Вербальні – моделі, отримані
в результаті розумової
діяльності людини і
представлені в розумовій або
словесній форма
Знакові – моделі, що
виражені спеціальними
знаками (малюнками,
текстами, схемами,
графіками, формулами тощо)
Математичні- моделі, що дозволяють врахувати кількісні та
просторові параметри явищ і використовувати точні
математичні методи

9.

Історична довідка
Абу Абдулла Абу Джафар Мухаммад ібн
Муса аль-Хорезмі (біля 780 — біля 850) —
великий узбецький математик, географ,
історик та астроном; вперше
виділив алгебру як самостійну дисципліну
(термін походить від назви однієї з праць
Аль-Хорезмі); його ім'я дало назву
терміну алгоритм.
Аль-Хорезмі
(786—850 рр. н.е.) —

10.

АЛГОРИТМ
Поняття алгоритм одне із фундаментальних в інформатиці
Алгоритм — це сукупність правил виконання певних дій, що
забезпечує розв’язок задачі
У житті ми постійно виконуємо різні алгоритми
Складаємо розпорядок дня, щоб
багато встигнути.

11.

ПРИКЛАДИ АЛГОРИТМІВ
Дістаємо кулінарну книгу і чітко
слідуємо рецепту , що написаний в ній,
щоб страва вдалася і можна було
пригостити своїх друзів
Дотримуємося правил
дорожнього руху при
переході вулиці.

12.

ВИКОНАВЦІ АЛГОРИТМІВ
Алгоритм складається з урахуванням виконавця.
Виконавцем може бути людина, автомат, комп’ютер,
тварина.

13.

ПРОГРАММА
Кажний виконавець має свою систему команд (СКВ).
Програма — це алгоритм , записаний на мові
виконавця.
Розглянемо приклад: візьмемо навчального виконавця Черепашку.
Нехай цей виконавець має три команди: вперед(1см), напрово(900),
наліво (900).
Початковий стан виконавця:
Який код програми необхідно написати,
щоб Черепашка накреслила букву Г ?
Код програми буде мати вигляд:
наліво (900)
вперед(1 см)
вперед 1 см
направо(900)
вперед(1см)

14.

ВЛАСТИВОСТІ АЛГОРИТМУ
(Вимоги до складання алгоритму)
дискретність: складається з окремих кроків
(команд)
зрозумілість: повинен включати тільки команди
відомі для виконавця (які містяться в СКВ)
визначеність: кожен крок алгоритму має бути
чітко й однозначно визначений,щоб не
допустити двоякого трактування виконавцем.
скінченність: закінчується за скінчену кількість
кроків
масовість: може застосовуватися багатократно
при різних вихідних даних
результативність: видає правильне рішення
при будь-яких допустимих вихідних даних

15.

ТИПИ АЛГОРИТМІВ
Линійний. Команди такого алгоритму виконуються послідовно в часі одна
за одною.
Розгалужений.Такий алгоритм містить хоча б
одну умову, врезультаті перевірки якої
здійснюється перехід до одного з можливих
кроків.
Прикладами можуть бути: знаходження
коренів квадратного рівняння, або богатир
на роздоріжжі із казок, який має вибрати собі
шлях.
Циклічнйи. Це алгоритм, в якому певна
послідовність команд повторюється кілька
разів з новими вхідними даними.
Наприклад, при вивченні вірша вам необхідно
перечитувати і повторювати одні і ті самі
стрічки .
наліво
направо
прямо

16.

СПОСОБИ ПРЕДСТАВЛЕННЯ АЛГОРИТМУ
Часто буває так, що алгоритм складає одна людина, а програму
пише інша людина. Алгоритми бувають дуже складними і великими за
об’ємом. Буває, що над алгоритмом працюють відразу кілька людей.
Враховуючи всі ці причини і ще ряд інших, алгоритми записуються
або описуються на паперових або електронних носіях.
Як можна описати (представити) алгоритм?
1. Словами. Наприклад, распорядок дня.
2. Графічно (блок-схемою). Так роблять
програмісти.
3. Алгоритмічною мовою(псевдокод) – це
навчальна мова. Вона застосовується у
багатьох тестах з інформатики.
4. Таблицею.
5. Мовою програмування.

17.

ОСНОВНІ БЛОКИ
ГРАФІЧНОГО ОПИСУ АЛГОРИТМУ
Блоки
Що ними позначають
Початок/кінець алгоритму
Введення/виведення даних
Опрацювання даних

18.

ОСНОВНІ БЛОКИ
ГРАФІЧНОГО ОПИСУ АЛГОРИТМУ
Блоки
Що ними позначають
Перевірка умови
Початок і кінець циклу
Підпрограма

19.

Алгоритм описаний словесно
A x2 + B x + C = 0
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Почати.
Введення A, B, C.
D = B2 - 4 A C.
Якщо D < 0, то перейти до п. 6.
Якщо D > 0, то перейти к п. 8.
Дійсних коренів нема.
Перейти до пункту 10.
X1 = (- B - D ) / 2 A ; X2 = (- B + D ) / 2 A .
Вивести значення X1 и X2.
Закінчити.

20.

Алгоритм у вигляді
блок-схеми
Начало
початок
A, B, C
D = B2 - 4 A C
D<0
X1 = (- B -
X2 = (- B +
D) / 2 A
Дійсних
коренів
нема
D) / 2 A
X1, X2
кінець

21.

Алгоритм мовою Паскаль
program example;
var a,b,c: integer;d,x1,x2:real;
begin
writeln ('a,b,c');
readln (a,b,c);
d:=sqr(b)-4*a*c;
if d<0 then
begin
writeln ('no korny');
end
else
begin
x1:=(-b-sqrt(d))/2*a;
x2:=(-b+sqrt(d))/2*a;
writeln ('x1=',x1,' x2=',x2);
end;
readln;
end.

22.

Всі існуючі мови програмування можна
поділити на дві групи: мови високого і
низького рівня
Програми написані мовами програмування високого
рівня , комп’ютер “не розуміє”. Для того щоб він міг
виконувати програму, її потрібно перекласти на
машинну мову.
Для перекладу використовують спеціальні програми,
що мають назву транслятори
Розрізняють два види трансляторів: компілятори
та інтерпретатори

23.

3.Вибрати правильне твердження
Мовою програмування називається фіксована система
позначень для опису структур даних і алгоритмів,
призначених для виконання обчислювальними машинами
Компілятор – системна програма, яка здійснює
переведення всього початкового тексту програми в
машинний код.
Лінійним називається такий алгоритм , що містить хоча
б одну умову.
Алгоритм , в якому певна послідовність команд
повторюється кілька разів з новими вхідними даними
називається, розгалуженим.
Алгоритмом називається наперед задана скінченна
послідовність чітких дій, виконання яких приводить до
досягнення поставленої мети.
Розпочати
Відповісти

24.

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

25.

Етапи розв’язування задач
1. Постановка задачи.
2. Побудова математичної
моделі.
3. Побудова алгоритму.
4.
5.
6.
7.
8.
Работа
використаня
комп’ютера
Вибір мови програмування.
Складання програми.
Работа з
використанням
Компіляція програми.
комп’ютера
Налагодження програми.
Експлуатація програми

26.

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

27.

Етапи розв’язування задачі
I етап
Аналіз вихідних даних:
1. Що дано? Швидкість автобуса – 60 км/год;
час – 30 хв.
2. Що необхідно знайти? Відстань від от А до В.
3. Які дані допустимі?
швидкість (км/год)
час (хв) ➾ 30 хв : 60 = 0,5 год.
Присвоєння імен змінним:
V – швидкість
t – час
S - відстань

28.

II этап
Побудова матиматичної моделі:
замінимо опис задачі відомою з фізики
формулою :
S= V· t

29.

III этап
Побудова алгоритму розв’язання задачі.
АЛГ Відстань
дійсн: V, t, S
Початок
ПОЧ
Ввести: швидкість автобуса,
Ввести : час,
V, t
S=Vt
Обчислити : відстань S = V · t
Вивести : результат S
КІН
S
Кінець

30.

IV этап V этап -
VІ этап VІІ этап -
VIІІ этап – результат одне число :
S = 30
Відповідь: 30 км.

31.

1
м
а
2
п
3
5
к
о
м п
і
л
л
г
о
с
р
я
о
и
т
м
м у
в
а
4
г
р
а
в
о
і
д
с
е
т
о
р
1
Властивість алгоритму
3
Складання програми
н
н
я
Старт
л
ь
5
р
ь
2
4
Чітко задана послідовність дій, що дає
результат
Штучно створений людиною
абстрактний або матеріальний об’єкт
Програма для переведення тексту програми в
машинний код

32.

1.Правильно розмістіть етапи розв’язання задач на комп’ютері
1
2
3
4
5
6
7
8
2.Встановити відповідність між позначенням на схемах і назвою операції алгоритму
3. Виберіть зі списку
властивості алгоритму
Як називається спрощене уявлення про
реальний об’єкт, процес чи явище?
масовість
алгоритм
програма
актуальність
модель
визначеність
CТАРТ
Перевірка
компілятор
Кількість балів
Правильні відповіді

33.

Завдання додому
1. За заданою блок-схемою
виконати обчислення, якщо
х=25 і якщо х= -100.
Дати відповіді на наступні
питання:
1.1. Як описаний алгоритм?
1.2.Якого типу алгоритм?
1.3.Хто може бути виконавцем
такого алгоритму?
Описати даний алгоритм
словесно.
2. Навести по 2 приклади
алгоритмів, які містять
циклічну і розгалужену
структуру.

34.

Використані інформаційні ресурси
• Караванова Т.П. Інформатика: основи алгоритмізації
та програмування.:777 задач з рек. Та прикл.:
Навч.посіб. Для 8-9 кл. із поглибл.вивч. Інф-ки/за заг.
Ред. М.З. Згурського –К.: Генеза, 2009. -286 с.: іл. –
Бібліограф. С. 286.
• Забарна А.П. Основи алгоритмізації та
програмування. Інтерактивні технології навчання на
уроках. –Тернопіль:Мандрівець, 2007.-96с.
• http://ukped.com/ - Українська педагогіка освітній
портал
• http://wiki.fizmat.tnpu.edu.ua/index.php - Фізмат
Вікіпедія