Конструктор уроків
Цілі:
навчальна: Поняття двовимірного масиву
розвивальна: розвивати логічне мислення; формувати вміння діяти за інструкцією, планувати свою діяльність, аналізувати i робити висновки;
виховна: виховувати інформаційну культуру учнів, уважність, акуратність, дисциплінованість.
2
3
4
Надіслати скріншот першого сертифікату
.png)
5
6
Алгоритм - це послідовність інструкцій, які виконуються за скінченну кількість кроків та приводять до результату.
Види алгоритмів:
лінійний
розгалужений
циклічний
Приклади алгоритмів сортування масивів (сайт)
7
Складність алгоритму
Часова складність - це час виконання алгоритму
Ємнісна складність - це обсяг одиниць пам'яті, необхідних для роботи алгоритму.
Алгоритм | Складність алгоритму |
| Ємнісна складність - розмір масиву b Часова складність - кількість повторень у циклі for |
8
Оцінка складності
Передумови обчислення складності алгоритму
Уявляють модель комп'ютера, на якому можна виконати будь-який алгоритм.
Обирають множину елементарних операцій, які виконує модель комп'ютера за одиницю часу (наприклад, арифметичні операції, команду розгалуження, порівняння і т.д.)
Позначають кількість вхідних даних, наприклад, n
Моделювання роботи алгоритму
Обчислюють кількості виконань елементарних операцій. Отримують відповідні оцінки складності алгоритму.
Позначення результату моделювання
f(n) - формула, за якою можна розрахувати складність алгоритму, яка залежить від кількості даних n (кількість виконаних елементарних операцій)
O(f(n)) - максимальна складність алгоритму
f(n) | Вид складності алгоритму | O(f(n)) |
5 операцій | незалежна від кількості даних | O(1) |
2 * n - 3 | лінійна (лінійно залежить від n) | O(n) |
4 * n2 -5* n +100 | квадратична (залежить від n2) | O(n2) |
3 * n3 + 120 * n2 -3 * n +230 | кубічна (залежить від n3) | O(n3) |
9
Приклад. Оцінити часову складність алгоритму
Алгоритм обчислення кількості додатних чисел в таблиці | Вид операції | Час виконання |
for i in range(m): | повторити дії m раз | |
____k = 0 | елементарна операція | 1 * m |
____for j in range(n): | повторити дії n раз | |
________if tabl[i][j]>0: | елементарна операція | 1 * n * m |
____________k = k+1 | елементарна операція | 1 * n* m |
____print(k) | елементарна операція | 1 * m |
Час виконання окремих кроків алгоритму додати та знайти найбільший доданок - він визначатиме часову складність алгоритму:
1 * m + 1 * n * m + 1 * n * m + 1 * m = 2 * n * m + 2 * m = O(n * m)
Якщо n=m, тоді O(n2) - складність пропорційна n2, тому алгоритм є квадратичним.
10
Завдання. Намалювати в зошиті перший та третій стовпці таблиці. Заповнити за зразком (вище) третій стовпчик - час виконання кожного кроку алгоритму. Обчислити під таблицею) складність алгоритму та визначити його тип (лінійний, квадратичний чи кубічний). Надіслати скріншот записів.
Алгоритм обчислення суми додатних чисел в таблиці | Вид операції | Час виконання |
for i in range(n): | повторити дії m раз | |
____s = 0 | елементарна операція | |
____for item in range(n): | повторити дії n раз | |
________if lst[ item ] > 0: | елементарна операція | |
____________s = s + lst[ item ] | елементарна операція | |
____print(s) | елементарна операція |
11
Тест складається з шести питань. Час тестування 4 хв.
12
Kahoot "Інформатика і не тільки (8ч2)"
Рефлексія від 0 учнів
Сподобався:
Так: 0
Ні: 0
Зрозумілий:
Так: 0
Ні: 0
Потрібні роз'яснення:
Ні: 0
Так: 0
