Основи алгоритмізації. Лекція 1 Початкові поняття програмування. - презентация

1 Основи алгоритмізації. Лекція 1 Початкові поняття програмування

2 Зміст лекції 1. Моделювання процесів та явищ на комп ' ютері Моделювання процесів та явищ на комп ' ютері 2. Етапи розв ' язування задач на ПК Етапи розв ' язування задач на ПК 3. Алгоритм та його властивості Алгоритм та його властивості 4. Базові структури алгоритмів Базові структури алгоритмів 5. Способи запису алгоритмів Способи запису алгоритмів 6. Побудова алгоритмів Побудова алгоритмів

3 Моделювання процесів та явищ на комп'ютері Моделювання – це особлива форма експерименту, коли досліджується не сам об'єкт, а деяка його заміна. Необхідність у моделюванні явищ і процесів за допомогою ПК виникає в таких ситуаціях, коли провести безпосередній лабораторний експеримент складно або неможливо. Комп'ютерне моделювання засноване на використанні математичних моделей і методів обробки даних. Модель – це опис істотних для поставленої задачі властивостей і закономірностей поведінки об'єктів, що забезпечують її розв'язок. Модель необхідна для того, щоб: зрозуміти, як побудований конкретний об'єкт – його структуру, властивості, закони розвитку і взаємодії з навколишнім світом; навчитися керувати об'єктом або процесом і визначити найкращі способи управління при заданих цілях і критеріях; прогнозувати прямі чи непрямі наслідки впливу на об'єкт.

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

5 І етап. І етап. Постановка задачі Точне формулювання умов та цілей розв'язування ІІ етап. ІІ етап. Побудова математичної моделі Розгорнутий змістовний опис задачі замінюється її математичною моделлю за допомогою математичних співвідношень ІІІ етап. ІІІ етап. Розробка алгоритму розвязування задачі Складання алгоритму обробки інформації на основі побудованої математичної моделі IV етап. IV етап. Вибір мови програмування Після оцінки характеру задачі і складності алгоритму вибирається найоптимальніша мова програмування V етап. V етап. Написання програми Створення програми на основі розроблених алгоритмів V І етап. V І етап. Трансляція і налагодження програми Переведення програми на машинну мову (компіляція). Перевірка програми на синтаксичні, змістовні та логічні помилки за допомогою системи тестів. Основні етапи проектування програми V ІІ етап. V ІІ етап. Аналіз результатів На основі аналізу результатів можлива зміна підходу до розв'язку задачі і повернення до ІІ етапу VІІІ етап. VІІІ етап. Експлуатація Текст програми, доповнений описом обмежень на початкові дані, відповідною документація для користувача, описом середовища програмування, тиражується

6 Поняття алгоритму Термін «алгоритм» уперше був використаний середньовічними вченими, які перекладали на латинь твори середньоазіатського мудреця, вченого Аль Хорезмі IX ст. Алгоритмами вони називали правила арифметичних дій над багаторозрядними числами. Точне математичне визначення алгоритму і вивчення цього поняття - предмет спеціальної дисципліни - теорії алгоритмів, яка виникла у 30-ті роки ХХ ст. Алгоритм – це скінчена послідовність інструкцій (команд), виконання яких приводить до результату. Кожна команда алгоритму містить точний опис деякої елементарної дії (операції), а також, у явному або неявному вигляді, вказівку на команду, яку необхідно виконати наступною. Інформацію, вхідну для алгоритму, прийнято називати його входом, а результат виконання – виходом. С1С1 С2С2 С k-1 CkCk ВхідВихід

7 Виконавець алгоритму Виконавець (Інтерпретатор) алгориму – деякий фізичний або абстрактний пристрій, що однозначно розпізнає і точно виконує (інтерпретує) кожну команду алгоритму. Виконавця хаpактеpизують: середовище; елементарні дії; система команд; відмова. Кожен алгоритм описується з врахуванням можливостей конкретного виконавця. У кожного виконавця є набір команд, які він може виконувати. Система команд виконавця – сукупність команд, які можуть бути використані виконавцем

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

9 Властивості алгоритмів Дискретність Алгоритм повинен складатися з сукупності окремих команд, виконання яких повинно бути послідовним. Визначеність (однозначність) Кожна команда алгоритму однозначно визначає дії виконавця і не припускає подвійного тлумачення. Суворо визначеним є і порядок виконання операцій. Формальність Будь-який виконавець здатний сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи покроково, може виконати поставлене завдання Скінченність Виконання алгоритму припиняється після завершення скінченої кількості кроків. Масовість В алгоритмі повинна передбачатися можливість його використання для цілого класу однотипних задач. Результативність Виконання будь-якого алгоритму, за скінченну кількість кроків, повинно забезпечувати можливість отримання результату.

10 Базові структури алгоритмів Базові структури алгоритмів – це структури, за допомогою яких створюється алгоритм для розв'язання певної задачі. Основна особливість базових алгоритмічних структур – їх повнота, тобто цих структур достатньо для створення найскладнішого алгоритму. Базовий тип алгоритму Означення Лінійний (слідування) Забезпечує отримання результату шляхом одноразового виконання послідовності дій, незалежно від вхідних даних і проміжних результатів. Дії в таких алгоритмах виконуються послідовно, одна за одною, тобто лінійно. Розгалужений Дає можливість здійснити вибір однієї з двох можливих послідовностей дій, в залежності від виконання або невиконання певної умови. Повторення (циклічний) Передбачено повторення деякої серії команд відповідно до сформульованої умови.

11 Способи запису алгоритмів Різні способи запису застосовуються для подання алгоритму у вигляді, який однозначно розуміється і його розробником, і виконавцем. Вибір способу залежить від того, хто його записує, або на кого він орієнтований. Словесна форма подання Словесна форма подання Графічний спосіб запису Графічний спосіб запису Таблична форма запису Таблична форма запису Мова програмування

12 Словесний спосіб Це найпростіша і найдоступніша форма подання алгоритму. Словесний спосіб - алгоритм записується природною мовою у вигляді пронумерованих етапів його виконання. Алгоритм знаходження НСД двох цілих додатних чисел (алгоритм Евкліда) 1.Дано два цілих додатних числа. Якщо вони рівні, то перше з них є найбільшим спільним дільником, якщо ж ні, то перейдемо до пункту 2. 2.Порівняємо два числа і виберемо більше. 3.Більше з двох чисел замінимо різницею більшого і меншого. 4.Перейдемо до пункту 1. Нехай задано два числа 45 і Отже, за сім кроків ми отримали результат НСД (45,12)=3. назад

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

14 Табличний спосіб запису Таблична форма запису - це запис алгоритму у вигляді таблиці. Таблиці, що використовуються, можуть бути різними Алгоритм обчислення R=2a+3b діїдія величина результат 12 1*2ak 2*3bu 3+kuR назад

15 Блок-схеми базових структур алгоритмів Слідування – вказівка S подається у вигляді послідовності двох (або більше) простих вказівок S1, S2, …,Sn, що виконуються одна за одною. S1 S2S2 … Sn S Розгалуження ( вибір ) Для виконання вказівки S треба спочатку визначити, хибне чи істинне деяке твердження P. Якщо твердження Р істинне, то виконується вказівка S1 і на цьому вказівка S закінчується. Якщо ж твердження хибне, то виконується вказівка S2 і на цьому виконання вказівки S закінчується. Розгалуження -+-+ S P S1 S2S2 ПОВНЕ +-+- S P S1 НЕПОВНЕ

16 Цикл – ПОКИ (цикл з передумовою) Для виконання вказівки S спочатку треба визначити, істинне чи хибне твердження P. Якщо P істинне, то виконується вказівка S1 і знову повертаються до визначення істинності твердження P. Якщо твердження P хибне, то виконання вказівки S вважається закінченим Цикли Цикл – ДО (цикл з післяумовою) Спочатку виконується вказівка S1, а потім визначається істинність твердження P. Якщо твердження P хибне, то знову виконується вказівка S1 і визначається істинність твердження P. Якщо ж твердження істинне P, то виконання вказівки S вважається закінченим. S P S S Цикл з параметром (цикл з лічильником) Для виконання вказівки S потрібно для параметра цикла і від початкового його значення F до кінцевого значення K з кроком H виконати певну серію команд S1 - S P S1 + і:=F,K,H

17 Побудова алгоритмів Метод покрокової деталізації 1-й крок. Розділити складну задачу на декілька простих задач (якщо виконавець не може виконати дану операцію, то виникає необхідність розкласти її на деяку сукупність більш простих операцій). 2-й крок. Якщо отримаємо сукупність операцій, яка містить в собі тільки операції системи команд виконавця, то потрібно завершити процес деталізації. 3-й крок. Скласти для кожної допоміжної задачі свій допоміжний алгоритм, при необхідності об'єднати дані в структури. 4-й крок. Скомпонувати результати проектування простих задач. 5-й крок. Проаналізувати роботу алгоритму.

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

19 Дякуємо за увагу!