31.01.2022-06.02.2022
Тема: Алгоритми та їх
властивості. Форми подання алгоритмів. Середовища програмування
Теортетична частина
Властивості
алгоритмів
Алгоритм – це скінчена однозначно визначена послідовність операцій(команд, вказівок),
формальне виконання яких приводить до розв’язання певної задачі на кінцеве
число кроків.
Виконавець
алгоритму – це жив чи нежива
істота, яка може виконати всі вказівки заданого алгоритму.
Припустимі команди – це команди, які можуть бути виконані
виконавцем.
Неприпустимі команди – це команди, які не можуть бути виконані
виконавцем.
Система команд виконавця – це
сукупність припустимих команд.
Властивості алгоритмів
Дискретність – це
означає процес розв’язування задачі,
який складається з окремих кроків або подій. Алгоритм складається із сукупності
відокремлених одна від одної команд(вказівок), кожна з яких виконується за
скінчений час. Тільки закінчивши виконання однієї команди, виконавець
переходить до виконання другої команди.
Визначеність(однозначність) - це
означає, що кожна команда алгоритму одназначно визначає дії виконавця і не
припускає подвійного тлумачення. Суворо визначеним є й порядок виконання
операцій.
Формальність
– це означає, що будь-який виконавець, який володіє заданою системою команд
виконавця, може виконати даний алгоритм, не вдаючись до суті цієї задачі.
Масовість
– це означає, що алгоритм передбачає можливість зміни початкових даних або
вхідних даних у деяких припустимих межах(універсальність алгоритму.
Результативність – це означає, що виконання алгоритму
не може закінчуватися невизначною ситуацією або зовсім не закінчуватися.
Будь-який алгоритм передбачає, що його виконання при допустимих початкових
даних за скінчене число кроків приведе до очікуваного результату.
Базові
структури алгоритмів
Базові структури алгоритмів – це структури, за допомогою яких створюється
алгоритм для розв’язання певної задачі.
Основна особливість
базових структур алгоритмів – це їх повнота, тобто цих структур достатньо для
створення найскладнішого алгоритму.
Лінійний алгоритм – це послідовне виконання усіх команд один лише
раз.
Розгалужений алгоритм – це перевірка умови і вибір певної операцій із
заданої множини операцій.
Циклічний алгоритм – це повторення певної кількості команд декілька
раз.
Способи
запису алгоритмів
Словесний спосіб - це письмова форма запису команд природньою мовою.
Формульно-словесний спосіб – це мова математичних формул, мова хімічних
процесів, навчальна алгоритмічна мова.
Графічний спосіб – це спосіб запису команд у вигляді блок-схем, структур.
Програмний спосіб – це запис алгоритму мовою програмування.
Наводимо окремі приклади використання алгоритмічних дій в
різних предметних областях.
Подумайте, хто може стати виконавцем
таких алгоритмічних
дій:
Алгоритми в математиці:
Порядок дій у числовому виразі.
Порядок дій під час розв'язування рівняння.
Порядок дій під час розв'язування задачі.
Порядок дій під час креслення геометричної фігури.
Алгоритми в мові:
Порядок дій під час морфологічного аналізу будови слова.
Порядок дій під час синтаксичного аналізу речення.
Порядок пунктів під час створення плану учнівського відгуку на художній твір.
Алгоритми в історії:
Порядок подій на хронологічній прямій.
Порядок висновків під час аналізу дій влади в революційний період.
Порядок дій під час розкопок артефактів.
Порядок подій під час утворення імперій.
Алгоритми в медицині:
Протоколи процесів вилікування від вірусного зараження.
Протоколи підготовки до складних операцій.
Порядок маніпуляцій під час операції.
Алгоритми в освіті:
Розклади уроків для деяких учнів або класів.
Календарні плани учителів для вивчення предметів або курсів.
Розклад дзвінків для уроків в закладі.
Алгоритми в побуті:
Режим дня для дітей в сім'ї.
Порядок дій під прибирання в кімнаті.
Кулінарний рецепт для приготування страви.
Порядок дій під час вимикання смартфону.
Алгоритми в транспорті:
Графік руху поїздів на вокзалі.
Порядок дій під час посадки в літак.
Маршрути руху громадського транспорту у місті.
Алгоритми в інформатиці:
Порядок дій під час вимикання комп'ютера.
Порядок під час реєстрації персонального акаунту в деякому хмарному середовищі.
Порядок дій під час створення презентації.
Порядок дій для впорядкування статистичних даних в таблиці.
Порядок дій під час автоматизованого створення веб-ресурсу.
Об'єктно-орієнтоване
програмування. SOLID-принципи
Об'єктно-орієнтоване програмування(ООП) - це парадигма програмування,
в якій основними концепціями є поняття об'єктів і класів.
Об'є́ктно-орієнто́ване
програмува́ння (ООП; іноді об'єктозорієнто́ване програмува́ння,
об'єктоорієнто́ване програмува́ння) -
одна з парадигм програмування, яка розглядає програму як множину
«об'єктів», що взаємодіють між собою. Основу ООП складають чотири основні
концепції:
·
інкапсуляція(вбудовування логіки в середовище),
·
поліморфізм(багато разів застосовуванність до
об’єктів)
·
успадкування(повторюваність властивостей та
параметрів)
·
абстракція(відхід
від конкретних реалізацій, виділення вагомих властивостей у множині об’ктів і
створення відповідних класів з відповідними операціями у цьому класів
об’єктів).
На
відміну від традиційних поглядів, коли програму розглядали як набір підпрограм, або як перелік інструкцій комп'ютеру, ООП-програми можна вважати
сукупністю об'єктів. Відповідно до парадигми об'єктно-орієнтованого
програмування, кожен об'єкт здатний:
·
отримувати повідомлення,
·
обробляти
дані(числа, масиви, текст, списки, тощо)
·
надсилати
повідомлення іншим об'єктам.
Кожен
об'єкт – це своєрідний незалежний автомат з окремим призначенням та
відповідальністю.
У Python3 – все є
об’єкт. Для цього і створили бібліотеку мови програмування: https://docs.python.org/3/library/index.html
SOLID -принципи. 5 принципів ООП.
Раніше
Об'єктно-орієнтоване програмування (ООП) включало 3 принципи:
інкапсуляція(вбудовування логіки в середовище),
поліморфізм(багато разів застосовуванність до об’єктів)
успадкування(повторюваність властивостей та параметрів)
Тепер є 5 принципів об'єктно-орієнтоване
програмування(ООП)
·
S (single responsibility) Принцип єдиної
відповідальності
·
О(open-closed) Принцип відкритості / закритості
·
L (Liskov substitution) Принцип підстановки
Лісков
(не варто заглиблюватися в успадкування)
·
I (interface segregation) Принцип поділу
інтерфейсу
·
D (dependency inversion) Принцип інверсії
залежностей
ООП не надає ніяких нових алгоритмів
Об'єктно-орієнтоване програмування — це метод
програмування, заснований на поданні програми як сукупності взаємодіючих
об'єктів, кожен з яких є примірником певного класу, а класи є членами певної
ієрархії наслідування[6]. Програмісти спочатку пишуть клас, а на
його основі під час виконання програми створюються конкретні об'єкти
(екземпляри класів). На основі класів можна створювати нові, які розширюють
базовий клас і таким чином створюється ієрархія класів.
На думку Алана Кея, розробника мови Smalltalk, якого вважають одним з
«батьків-засновників» ООП, об'єктно-орієнтований підхід полягає в наступному
наборі основних принципів:
·
Все є об'єктами.
·
Всі дії та розрахунки виконуються шляхом взаємодії
(обміну даними) між об'єктами, під час якої один об'єкт потребує, щоб інший
об'єкт виконав деяку дію. Об'єкти взаємодіють, надсилаючи і отримуючи
повідомлення. Повідомлення — це запит на виконання дії, доповнений набором
аргументів, які можуть знадобитися під час виконання дії.
·
Кожен об'єкт має незалежну пам'ять, яка складається з
інших об'єктів.
·
Кожен об'єкт є представником (екземпляром,
примірником) класу, який виражає загальні властивості об'єктів.
·
У класі задається поведінка (функціональність)
об'єкта. Таким чином усі об'єкти, які є екземплярами одного класу, можуть виконувати
одні й ті ж самі дії.
·
Класи організовані у єдину деревоподібну структуру з
загальним корінням, яка називається ієрархією успадкування. Пам'ять та поведінка, зв'язані з
екземплярами деякого класу, автоматично доступні будь-якому класу,
розташованому нижче в ієрархічному дереві.
Таким чином, програма є набором об'єктів, що мають
стан та поведінку. Об'єкти взаємодіють використовуючи повідомлення. Будується
ієрархія об'єктів: програма в цілому — це об'єкт, для виконання своїх
функцій вона звертається до об'єктів що містяться у ньому, які у свою чергу
виконують запит шляхом звернення до інших об'єктів програми. Звісно, щоб
уникнути нескінченної рекурсії у зверненнях, на якомусь етапі об'єкт
трансформує запит у повідомлення до стандартних системних об'єктів, що даються
мовою та середовищем програмування. Стійкість та керованість системи
забезпечуються за рахунок чіткого розподілу відповідальності об'єктів (за кожну
дію відповідає певний об'єкт), однозначного означення інтерфейсів міжоб'єктної
взаємодії та повної ізольованості внутрішньої структури об'єкта від зовнішнього
середовища (інкапсуляції).
Створення графічних
об’єктів мовою програмування Python3
Зайти в середовище онлайн-Python https://www.programiz.com/python-programming/online-compiler/
і виконати:
Завдання 1. Створити
алгоритм для креслення квадрату мовою програмування Python3 в
середовищі Thonny.
Реалізація.
import
turtle #викликається графічний модуль turtle
print("Kвадрат
від черепахи")
t=turtle.Pen() #задається змінна в графічному модулі turtle
t.up()
#задається вказіка підняти
пензлик
t.goto(-150, -150) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка опустити пензлик
t.width(7) #вказівка товщини пензлика на 7
пікселі
t.color(0.9, 0.3, 0.7) #вказівка кольору пензлика
for i in
range(1,5): #створюємо цикл з лічильником від 1 до 4
t.forward(270) #команда креслення відрізка довжиною 270 пікселів
t.left(90) #команда повороту олівця на 90 градусів
Завдання 2. Створити алгоритм для креслення рівностороннього трикутника мовою
програмування Python3 в середовищі Thonny.
Реалізація.
import
turtle #викликається графічний модуль turtle
print("Рівносторонній
трикутник від черепахи")
t=turtle.Pen() #створюємо цикл з лічильником від 1 до 4
t.up()
#задається вказіка
підняти пензлик
t.goto(-180, -180) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка опустити пензлик
t.width(6) #вказівка товщини пензлика на 6
пікселі
t.color(0.3, 0.9, 0.3) #вказівка кольору пензлика
for m in
range(1,4): #створюємо цикл з лічильником
t.forward(280) #команда креслення відрізка довжиною 280 пікселів
t.left(120) #команда поворотуолівця на 120 градусів
Завдання 3. Створити алгоритм для креслення рівностороннього 5-кутника мовою
програмування Python3 в середовищі Thonny.
import
turtle #викликається графічний модуль turtle
print("Рівносторонній
5-кутник від черепахи")
t=turtle.Pen() #створюємо цикл з лічильником від 1 до 4
t.up()
#задається вказіка
підняти пензлик
t.goto(-150, -150) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка
товщини пензлика
t.width(5) #вказівка товщини пензлика на 5
пікселі
t.color(0.5, 0.5, 0.7) #вказівка кольору пензлика
for k in
range(1,6): #створюємо
цикл з лічильником від1 до 5
t.forward(50) #команда
креслення відрізка довжиною 180 пікселів
t.left(72) #команда повороту олівця на 120 градусів
Завдання 4. Створити алгоритм для креслення рівностороннього зіркового 8-кутника мовою
програмування Python3 в середовищі Thonny.
import
turtle #викликається графічний модуль turtle
print("Зірковий
8-кутник від черепахи")
t=turtle.Pen() #створюємо цикл з лічильником від 1 до 4
t.up()
#задається вказіка
підняти пензлик
t.goto(-150, -150) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка опустити пензлик
t.width(4) #вказівка товщини пензлика на 4
пікселі
t.color(0.9, 0.9, 0.1) #вказівка кольору пензлика
for i in
range(1,9): #створюємо
цикл з лічильником від1 до 6
t.forward(80) #команда креслення відрізка довжиною 180 пікселів
t.left(225) #команда повороту олівця на 120 градусів
Завдання 5. Створити алгоритм для креслення рівностороннього зіркового 36-кутника мовою
програмування Python3 в середовищі Thonny.
import turtle
print("Зірковий
36-кутник від черепахи")
t=turtle.Pen()
t.up()
#задається вказіка
підняти пензлик
t.goto(0, -150) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка опустити пензлик
t.width(3) #вказівка товщини пензлика на 3
пікселі
t.color(0.9, 0.5, 0.7) #вказівка кольору пензлика
for i in range(1,37):
t.forward(80)
t.left(244)
Завдання 6. Створити алгоритм для креслення рівностороннього зіркового 37-кутника мовою
програмування Python3 в середовищі Thonny.
import turtle
print("Зірковий
36-кутник від черепахи")
t=turtle.Pen()
t.up()
#задається вказіка
підняти пензлик
t.goto(-10, -10) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка опустити пензлик
t.width(4) #вказівка товщини пензлика на 4
пікселі
t.color(0.6, 0.6, 0.7) #вказівка кольору пензлика
for i in
range(1,38):
t.forward(100)
t.left(175)
Завдання 7. Створити алгоритм для креслення паралелограма мовою
програмування Python3 в середовищі Thonny.
import turtle
print("Паралелограм
від черепахи")
t=turtle.Pen()
t.up()
#задається вказіка
підняти пензлик
t.goto(-190, -150) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка опустити пензлик
t.width(3) #вказівка товщини пензлика на 3
пікселі
t.color(0.9, 0.3, 0.7) #вказівка кольору пензлика
for i in
range(1,3):
t.forward(80)
t.left(60)
t.forward(180)
t.left(120)
Завдання 8. Створити алгоритм для креслення трапеції мовою програмування Python3 в
середовищі Thonny.
import turtle
print("Рівнобічна
трапеція від черепахи")
t=turtle.Pen()
t.up()
#задається вказіка
підняти пензлик
t.goto(-150, -150) #вказіка опустити пензлик в точці
(х, у)
t.down() #задається вказіка опустити пензлик
t.width(7) #вказівка товщини пензлика на 7
пікселі
t.color(0.4, 0.8, 0.7) #вказівка кольору пензлика
t.forward(180)
t.left(120)
t.forward(80)
t.left(60)
t.forward(100)
t.left(60)
t.forward(80)
t.left(60)
Завдання 9. Створити алгоритм для креслення кола мовою програмування Python3 в
середовищі Thonny.
import turtle
print("Коло
від черепахи")
t=turtle.Pen()
t.up()
t.forward(100)
t.down()
t.begin_fill()
t.circle(100)
t.t.end_fill()
Завдання 10. Створити алгоритм для креслення клітинкового квадрату 5х5 мовою
програмування Python3 в середовищі Thonny.
import turtle
print("Квадрат розміром 5х5 від
черепахи")
a=20
#викликається графічний модуль turtle
print(" 5 квадратів 1 від черепахи")
t=turtle.Pen()
t.up()
t.forward(100)
t.down() #задається змінна
в графічному модулі turtle
for j in range(1,6):
for i in
range(1,5): #створюємо цикл з лічильником
від 1 до 4
t.forward(a)
#команда креслення відрізка 170 пікселів
t.left(90)
#команда повороту олівця на 90 градусів
a=a+20
t.forward(100)
t.left(90)
print("Kвадрат 2 від черепахи")
t=turtle.Pen()
t.up()
t.forward(100)
t.down()
t.forward(100)
t.right(90)#задається змінна в графічному модулі
turtle
a=20
t.setheading(180)
t.right(-270)
t.forward(100)
t.left(90)
for j in range(1,6):
for i in
range(1,5): #створюємо цикл з лічильником
від 1 до 4
t.forward(a)
#команда креслення відрізка 170 пікселів
t.left(90)
#команда повороту олівця на 90 градусів
a=a+20
Завдання 11. Створити клітиноковий квадрат розміром
5х5 мовою програмування Python3 в середовищі програмування Thonny.
Реалізація.
import
turtle
# викликається графічних модуль turtle
print(" Клітинковий квадрат розміром 5х5 від черепахи")
a=50
#задається розмір клітинки в 20
пікселів
print("Перші 5 квадратів 1 від черепахи")
t=turtle.Pen()
#задається об’єкт Реn(пезлик),
якому даємо вказіки
t.width(2)
#задається вказіка товщини
пензлика
t.goto(-250,-80) #вказівка перемістити пензлик в точку (х, у)
t.up()
#задається вказіка підняти
пензлик
t.forward(250)
#задається вказіка накреслити
відрізок на 100 пікселів
t.down()
#задається вказіка
опустити пензлик
for j in range(1,6): #вказівка циклу (повторення дій)
з лічильником від 1 до 5 разів
for i in
range(1,5): #вказівка вкладений цикл
(повторення дій) з лічильником від 1 до 4 разів
t.forward(a) #команда креслення відрізка
а пікселів
t.left(90)
#команда повороту олівця на 90 градусів вліво
a=a+50 #команда збільшення сторони
квадрату на 20 пікселів
t.forward(250)
t.left(90)
print("Другі 5 квадратів 2 від черепахи")
t.shape('arrow') #задається змінна в
графічному модулі turtle
t=turtle.Pen() #задається об’єкт Реn(пезлик),
якому даємо вказіки
t.up()
#задається вказіка підняти
пензлик
t.goto(250,170) #вказіка опустити пензлик в точці (х, у)
t.down() #задається вказіка товщини
пензлика
t.right(180)
#команда повороту олівця на
180 градусів вправо
a=50 #задається розмір клітинки в 20
пікселів
for j in range(1,6): #вказівка циклу з
лічильником від 1 до 5
for i in range(1,5): #вказівка циклу з
лічильником від 1 до 4
t.forward(a)
#команда креслення відрізка а
пікселів
t.left(90)
#команда повороту олівця на
90 градусів
a=a+50 #задається розмір клітинки ще на
20 пікселів більше
Протестуйте
цей алгоритм
Завдання 12. Створити алгоритм креслення куба
та вписаної піраміди в цей куб мовою програмування Python3 в середовищі програмування Thonny.
Реалізація.
import turtle
print("Алгоритм виконання куба та вписаної піраміди")
t=turtle.Pen()
t.up() #вказівка не залишати слід від
пензлика
t.goto(-100,-100) #вказівка перемістити пензлик в
точку (х, у)
t.down() #вказівка залишати слід від пензлика
t.width(5) #вказівка товщини пензлика на 5
пікселі
t.color(0.0, 0.3, 0.1) #вказівка кольору пензлика
for k in range(1, 3): #вказівка повторення(цикл) дій від 1 до 2
for j in range(1, 5): #вказівка
повторення(цикл) дій від 1 до 4
t.shape('arrow') #викликається новий виконавець вказівок в
модулі turtle
t.forward(200) #вказіка руху вперед
пензлика на 200 пікселів
t.left(90) #вказіка повороту пензлика
вліво на 90 градусів
t.width(5) #зміна товщини пензлика на 3
пікселі
t.goto(20,10) #вказівка перемістити пензлик в
точку (х, у)
t.down() #вказівка залишати слід від пензлика
t.color(0.0, 0.3, 0.1)
t.goto(-100, 100) #вказівка перемістити пензлик в
точку (х, у)
t.goto(220,210) #вказівка перемістити пензлик в
точку (х, у)
t.goto(100,100) #вказівка перемістити пензлик в точку (х, у)
t.goto(100,-100) #вказівка перемістити пензлик в точку (х, у)
t.goto(-100,100) #вказівка перемістити пензлик в точку (х, у)
t.goto(-100,100) #вказівка перемістити пензлик в точку (х, у)
t.goto(220,210) #вказівка перемістити пензлик в точку (х, у)
t.goto(20,210) #вказівка перемістити пензлик в точку (х, у)
t.goto(-100,100) #вказівка перемістити пензлик в точку (х, у)
t.goto(220,210) #вказівка перемістити пензлик в точку (х, у)
t.goto(100,-100) #вказівка перемістити пензлик в точку (х, у)
t.goto(220,10) #вказівка перемістити пензлик в точку (х, у)
t.goto(20,10) #вказівка перемістити пензлик в точку (х, у)
t.color(0.7, 0.3, 0.5)
t.goto(220,210) #вказівка перемістити пензлик в точку (х, у)
t.goto(100,-100) #вказівка перемістити пензлик в точку (х, у)
t.goto(20,10) #вказівка перемістити пензлик в точку (х, у)
t.goto(-100,100) #вказівка перемістити пензлик в точку (х, у)
t.goto(100,-100) #вказівка перемістити пензлик в точку (х, у)
t.goto(220,210) #вказівка перемістити пензлик в точку (х, у)
t.goto(20,10) #вказівка перемістити пензлик в точку (х, у)
t.up() #вказівка не залишати слід від
пензлика
t.goto(20,10) #вказівка перемістити пензлик в точку (х, у)
t.goto(-100,100) #вказівка перемістити пензлик в точку (х, у)
t.down() #вказівка залишати слід від пензлика
t.goto(220,210) #вказівка перемістити пензлик в точку (х, у)
Протестуйте
цей алгоритм
Завдання 13. Створити алгоритм креслення тривимірного тіла: 4-кутної піраміди мовою програмування Python3 в середовищі програмування Thonny.
Реалізація.
import turtle
print("Алгоритм зміни позиції для виконавця
піраміди")
t=turtle.Pen()
t.up() #вказівка не залишати слід від
пензлика
t.goto(-100,-100) #вказівка перемістити пензлик в точку (х, у)
t.down() #вказівка залишати слід від пензлика
t.width(2) #вказівка товщини пензлика на 2 пікселі
t.color(0.4, 0.6, 0.1) #вказівка кольору пензлика
t.goto(100, -100) #вказівка перемістити пензлик в точку (х, у)
t.goto(130,-60) #вказівка перемістити пензлик в точку (х, у)
t.goto(-70,-60) #вказівка перемістити пензлик в точку (х, у)
t.goto(-100,-100) #вказівка перемістити пензлик в точку (х, у)
t.up() #вказівка не залишати слід від пензлика
t.goto(15,-80) #вказівка перемістити пензлик в точку (х, у)
t.down() #вказівка залишати слід від пензлика
t.goto(15,220) #вказівка перемістити пензлик в точку (х, у)
t.goto(-70,-60) #вказівка перемістити пензлик в точку (х, у)
t.goto(130,-60) #вказівка перемістити пензлик в точку (х, у)
t.goto(15,220) #вказівка перемістити пензлик в точку (х, у)
t.goto(100, -100) #вказівка перемістити пензлик в точку (х, у)
t.goto(-100, -100) #вказівка перемістити пензлик в точку (х, у)
t.goto(15,220) #вказівка перемістити пензлик в точку (х, у)
Протестуйте
цей алгоритм
Завдання 14. Створити двовимірний логотип мовою
програмування Python3 в середовищі програмування Thonny.
Реалізація.
import turtle
print("Логотип: Спіральні
прямокутники із cпільною вершиною")
t=turtle.Pen()
a=5
t.begin_fill()
for j in range(1,7):
for j in range(1,5):
t.forward(a)
t.left(90)
t.forward(a/2)
t.left(90)
t.color(0,
0.1, 0.1)
t.forward(a)
t.left(90)
t.forward(a/2)
t.color(0.2, 0.1,
0.9)
a=2*a
t.right(90)
t.color(0.4, 0.9, 0.1)
t.end_fill()
Завдання 15. Самостійно створити довільний логотип на основі декількох трикутників мовою програмування Python3 в середовищі програмування Thonny.
Завдання 16. Самостійно створити довільний двовимірний логотип на основі чотирикутників мовою програмування Python3 в середовищі програмування Thonny.
Результат цієї
роботи треба надіслати на електронну адресу учителя
інформатики:
vinnser@gmail.com (Сергій
Петрович)