ПЛАН ЗАНЯТТЯ No 1
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Основи алгоритмізації. Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: розглянути поняття алгоритму, властивості алгоритмів та основні типи алгоритмів . Виховна: викликати бажання вивчення дисципліни.
Тип заняття: лекція. Форми та методи проведення заняття: вступна лекція.
Методи та форми проведення заняття: мовний, репродуктивний.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Сафронов И.К. Задачник-практикум по информатике. – СПб.: БХВ-
Петербург, 2002.- 432с. 3. Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных
в Delphi: Пер. с англ./ Бакнелл Джулиан М.: СПб ООО «ДиасофтЮП», 2003. – 560 с.
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду, готовності
аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій. 5. Вивчення нового матеріалу: Тема лекції: Основи алгоритмізації.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Лекція No1. Тема: Основи алгоритмізації.
План 1. Поняття алгоритму та алгоритмізації. 2. Способи задавання алгоритмів. 3. Базові структури алгоритмів.
- Поняття алгоритму та алгоритмізації. Процес розв'язання прикладної задачі — не одномоментний акт, він складається з послідовності певних дій чи операцій. Під алгоритмом розуміють скінченну послідовність операцій чи дій, яка забезпечує розв'язання задачі певними ресурсами за певний час.
Алгоритмізацією задачі називається процес зведення задачі до послідовності операцій, що виконуються одна за одною.
Алгоритм має задовольняти певним вимогам. 1. Масовість. Застосовуватися не для однієї, а для цілого класу однотипних задач. 2. Скінченність. Складатися зі скінченної кількості операцій чи дій, кожна з яких потребує скінченного відрізка часу. 3. Результативність. Після закінчення виконання алгоритму має бути певний результат.
- Однозначність. Виконання кожної дії алгоритму і всієї послідовності дій має здійснюватися однозначно. Це означає, що скільки б разів алгоритм не застосовувався до одних і тих самих вихідних даних, результат виконання кожної дії і всієї послідовності у цілому буде один і той самий.
- Правильність. При застосуванні алгоритму до допустимих вхідних даних має бути отриманий потрібний результат. Доведення правильності алгоритму — один з найскладніших етапів його створення. Найпоширеніша процедура перевірки правильності алгоритму — обґрунтування правомірності та перевірка правильності кожного з кроків при наборі тестів, підібраних так, щоб охопити всі допустимі вхідні і вихідні дані.
- Ефективність. Забезпечувати розв'язання задачі за мінімальний час з мінімальними затратами апаратних і програмних ресурсів.
Для оцінки алгоритмів існує багато критеріїв. Найчастіше аналіз алгоритму (або, як кажуть, аналіз складності алгоритму) полягає в оцінці затрат часу на розв'язок задачі у розрахунку на одиницю вхідних даних. Фактично, ця оцінка зводиться до оцінки кількості базових елементарних операцій, на які можна розкласти даний алгоритм, оскільки кожна така операція виконується за конкретний, відомий відрізок часу. Складність алгоритму оцінюється також кількістю апаратурних ресурсів, зокрема обсягом пам'яті, задіяної для виконання даного алгоритму.
2. Способи задавання алгоритмів. Алгоритм може задаватися різними способами:
▪ словесно, словами і реченнями природної мови — української, англійської тощо;
▪ графічно, за допомогою спеціальних схем із застосуванням умовних графічних позначень;
▪ символами спеціальної алгоритмічної мови. Запис алгоритму словами і реченнями природної мови найдоступніший для ширшого кола користувачів і не потребує спеціальної підготовки. Водночас така форма найменш точна та визначена, оскільки допускає різні тлумачення одного і того самого поняття внаслідок синонімічного багатства природних мов.
Застосування спеціальних графічних схем для запису алгоритму дає змогу наочно бачити взаємозв'язок вхідних і вихідних величин на різних етапах виконання алгоритму. Крім того, алгоритм у такій формі доволі просто змінювати і коригувати.
Алгоритм, записаний спеціальною алгоритмічною мовою, може бути використаний на комп'ютері для розв'язку прикладних задач.
Графічне зображення алгоритмів Алгоритм зручно зображати графічно, у вигляді спеціальних схем. Схемою називається умовне наочне графічне зображення алгоритму за допомогою умовних графічних позначень. Умовні графічні позначення на схемах алгоритмів унормовані державними стандартами.
Розглянемо основні умовні графічні позначення на схемах.
- Зв'язок між окремими операціями чи діями алгоритму позначають лінією (мал. 1, а). 2. Операцію, або послідовність операцій позначають прямокутником. Всередині прямокутника записується зміст операції чи послідовності операцій (мал. 1, б).
- Перевірка умови позначається ромбом. Всередині ромба записується сама умова. Залежно від того, виконується умова чи ні, подальші операції вказуються стрілками, що виходять з вершин ромба, позначених «так» і «ні» (мал. 1, в).
- Початок і кінець алгоритму зображуються заокругленими прямокутниками із написом усередині «початок» і «кінець» (мал. 1, г).
- Програма чи алгоритм, що входять до даного алгоритму як складова частина, зображуються прямокутником з подвійними вертикальними сторонами (мал. 1, д).
- Коментарі, що пояснюють операції обробки інформації, виділені квадратною дужкою зі штриховою лінією (мал.1, е).
- З'єднання розірваних зв'язків зображується колом з позначенням номера зв'язку (мал. 1, є).
а)
P = b2 - ас
б)
x>0
в)
Початок
г) Кінець
д)
-
- - ⌈ │ ⌊
початкових Присвоюван
ня параметрам значень е)
4 4
є)
Мал. 1
- Базові структури алгоритмів.
Алгоритми розв'язку складних задач мають схему зі складною структурою. Водночас, у будь-якій складній структурі можна виділити базові структури і розглядати складні структури як сукупність базових структур. Це значно спрощує і прискорює створення, коригування, перевірку алгоритму на правильність. Розглянемо базові структури алгоритму:
▪ послідовна структура. У цій структурі операції обробки інформації виконуються послідовно, одна за одною (мал. 2, а);
▪ розгалужена структура. Визначальною операцією цієї структури є операція перевірки умови, залежно від чого процес обробки інформації розгалужується на два альтернативні напрями (мал.2,
б);
▪ циклічна структура. Замкнена послідовність операцій, коли після виконання останньої операції переходять до виконання першої (рис. 2, в).
f = lg a
1 a = b + c ∙ d
f = lg a
2
g = f ∙ a
y = a + b
а)
3
4
ні x>0
так
5
y = c / b
б)
6
x = a + n ∙ b
в) x = a + n ∙ b
ні n = 0
так
y = x ∙ c
- Контрольні питання 1. Дайте поняття алгоритму. Перерахуйте його властивості 2. Перерахуйте способи задавання алгоритмів. 3. Назвіть базові структури алгоритмів.
Література:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Сафронов И.К. Задачник-практикум по информатике. – СПб.: БХВ-
Петербург, 2002.- 432с. 3. Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры
данных в Delphi: Пер. с англ./ Бакнелл Джулиан М.: СПб ООО «ДиасофтЮП», 2003. – 560 с.
Для перегляду тексту необхідно залогінитись.