Інформатика. 11 клас. Моделювання. Основи алгоритмізації.

Матеріал з Фізмат Вікіпедії
Перейти до: навігація, пошук

Інформатика. 11 клас. Моделювання. Основи алгоритмізації

Основні терміни і поняття

Модель – це об'єкт, який зберігає суттєві риси того об’єкта, що вивчається, і заміщує його під час дослідження.

Моделювання – це процес створення моделі, а також це дослідження об’єктів за допомогою побудови і вивчення їх моделей.

Прототип, або оригінал – це той об’єкт, для заміщення якого призначається модель.

Адекватність моделі – це її відповідність оригіналу в межах поставленої задачі.

Етапи комп’ютерного моделювання – це постановка задачі та її аналіз; побудова інформаційної моделі; розробка методу і алгоритму дослідження моделі; розробка комп’ютерної моделі; проведення комп’ютерного експерименту.

Інформаційна модель – це сукупність інформації, що характеризує властивості та стан об’єкта, його взаємозв’язки із зовнішнім світом.

Математична модель – це сукупність математичних формул, які відбивають взаємозалежності між параметрами об’єкта.

Комп’ютерна модель – це інформаційна модель, реалізована на комп’ютері.

Лінійний алгоритм – це алгоритм, який приписує одноразове виконання однієї і тієї самої послідовності дій при будь-яких допустимих вхідних даних задачі.

Алгоритм з розгалуженням – це алгоритм, який приписує виконання тих чи інших дій у залежності від результату перевірки умови.

Алгоритм з повторенням – це алгоритм, який приписує повторне виконання дій.

Слідування – це базова структура лінійного алгоритму:"дія 1"→ "дія 2".

Повторення, або цикл – це базова структура алгоритму з повторенням, яка має два варіанти: а) цикл з передумовою; б) цикл з післяумовою.

Структурний алгоритм – це алгоритм, складений виключно із базових алгоритмічних структур.


Класифікація моделей за способом уявлення

Розглядаючи моделі за ознакою галузі використання, можна сказати, що вони бувають:

навчальні — наочні посібники, тренажери, навчальні програми;

дослідні — створюються для дослідження характеристик реального об'єкта (наприклад, модель теплоходу перевіряється на плавучість, а модель літака — на аеродинамічні характеристики);

науково-технічні — для дослідження процесів та явищ (наприклад, ядерний реактор або синхрофазотрон);

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

імітаційні моделі — виконується імітація дійсної ситуації, що багато повторюється для вивчення реальних обставин (наприклад: випробування лікарських препаратів на мишах або інших тваринах, політ собаки в космос).

За ознакою фактора часу моделі можуть бути динамічні та статичні. В першому випадку над об'єктом виконуються дослідження протягом деякого терміну (наприклад, постійний нагляд сімейного лікаря), а в другому — робиться одноразовий зріз стану (наприклад, одноразове обстеження в поліклініці).

За способом представлення моделі можуть бути матеріальні та інформаційні.

Матеріальні моделі — це предметне відображення об'єкта зі збе­реженням геометричних та фізичних властивостей (наприклад: іграшки, чучела тварин, географічні карти, глобус і таке інше). Це матеріальні моделі реально існуючих об'єктів. Матеріальною моделлю можна також вважати хімічний або фізичний дослід. Ці моделі реалізують матеріальний підхід до вивчення об'єкта чи явища.

Моделі.jpg

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

Інформаційні моделі.jpg

Інформаційні моделі можуть бути:

§ вербальними — моделі отримані в результаті розумової діяльності людини і представлені в розумовій або словесній формі;

§ знаковими — моделі, що виражені спеціальними знаками (малюнками, текстами, схемами, графіками, формулами тощо).

Поняття алгоритму

Точне математичне визначення алгоритму та вивчення цього поняття - предмет спеціальної математичної дисципліни - теорії алгоритмів, яка, в свою чергу, спирається на апарат математичної логіки. Тут ми розглянемо на змістовному (неформальному) рівні лише основні характерні риси цього поняття. Алгоритм - це правило перетворення інформації, застосування якого до заданої (вхідної) інформації приводить до результату - нової інформації. Так, наприклад, застосування правила додавання дробів до 1/2 і 2/3 дає результат 5/6. Основну увагу в теорії алгоритмів приділяється методам завдання (описання, конструювання) алгоритмів. Алгоритм - це скінченний набір інструкцій по перетворенню інформації (команд), виконання яких приводить до результату. Кожна інструкція алгоритму містить точний опис деякої елементарної дії по перетворенню інформації, а також (в явному або неявному вигляді) вказівку на інструкцію, яку необхідно виконувати наступною. Так, алгоритм додавання дробів можна задати такою послідовністю команд:

Приклад 1. Алгоритм додавання дробів.

Вхід: А/В, С/D; 1. Обчислити Y = B*D; {Перейти до наступної команди} 2. Обчислити X¬¬¬¬¬1 = A*D; {Перейти до наступної команди} 3. Обчислити X2 = B*C; {Перейти до наступної команди} 4. Обчислити X = X1+X2; {Перейти до наступної команди} 5. Обчислити Z = НСД(X,Y); {Перейти до наступної команди} 6. Обчислити Е = Х div Z; {Перейти до наступної команди} 7. Обчислити F = Y div Z; {Завершити роботу}. Вихід: E/F

Наш алгоритм складається з 7-ми інструкцій, кожна з яких містить опис однієї з арифметичних дій над цілими числами: додавання, множення, обчислення НСД і цілочисленне ділення div. Крім того, кожна інструкція (у неявному вигляді) містить вказівку на наступну виконувану інструкцію. Таким чином, алгоритм описує деталізований по кроках процес перетворення інформації. Рівень деталізації опису визначається набором можливих команд. Цей набір називають набором команд Виконавця або Інтерпретатора. При цьому мається на увазі, що алгоритми виконує Виконавець (Інтерпретатор) - деякий пристрій, що однозначно розрізнює і точно виконує (інтерпретує) кожну команду алгоритму. Для виконання нашого алгоритму Виконавець повинен, очевидно, вміти оперувати з цілими числами, виділяти чисельник і знаменник дробів, а також складати з пари цілих чисел дріб. Крім того, Виконавець повинен вміти запам’ятовувати результати виконання операцій і переходити до виконання наступної команди. Уявимо собі, що у нашому розпорядженні знаходиться Виконавець, який інтерпретує команди - операції цілочисельної арифметики - додавання віднімання, множення, обчислення неповної частки (div) та остачі (mod), обчислення НСД і НСК з запам’ятовуванням результатів і вмінням переходити до наступної команди. Тоді для цього Виконавця можна складати найрізноманітніші алгоритми арифметичних обчислень - тобто обчислень, заданих формулами типу Х = НСД ((А + В) div 100, (А * В - 7) mod 10) використовуючи команди, аналогічні командам алгоритму з приклада 1.

Приклад 2. Алгоритм поділу відрізка навпіл за допомогою циркуля та лінійки.

Вхід: Відрізок АВ; Побудувати коло О1 з центром А і радіусом АВ; Побудувати коло О2 з центром В і радіусом АВ; Знайти точки С і D перетину кіл О1 і О2; Побудувати відрізок СD; Знайти точку Е перетину АВ і СD. Вихід: Точка Е - середина відрізку АВ.

У прикладі 2 Виконавець має набір команд, за допомогою яких можна розв’язувати геометричні задачі на побудову за допомогою циркуля і лінійки. Виконання алгоритму полягає у послідовному виконанні кожної побудови і переході до виконання наступної команди. Відзначимо, що нумерувати команди алгоритму не треба, якщо Виконавець завжди переходить до наступної команди.

Характерні властивості алгоритмів

Поняттю алгоритму притаманні такі властивості:

1. Елементарність. Кожна команда з набору команд Виконавця містить вказівку виконати деяку елементарну (не деталізуєму більш повно) дію, яку Виконавець однозначно розуміє і виконує. Поняття елементарності тому відносне. Так в алгоритмі прикладу 1 міститься команда обчислення НСД двох чисел. Це означає, що Виконавець вміє знаходити НСД, причому алгоритм обчислення (алгоритм Євкліда або якийсь інший) захований від людини, яка складає алгоритми для цього Виконавця. Якщо набір команд Виконавця не містить команди обчислення НСД, обчислення НСД певно визначено у виді алгоритму.

Приклад 3. Алгоритм Євкліда обчислення найбільшого спільного дільника цілих додатних чисел А і В: НСД (А,В).

Вхід А,В; Обчислити U = A; Обчислити V = B; Поки U <> V виконувати Якщо U < V то Обчислити V = V - U інакше Обчислити U = U - V; Обчислити D = U. Вихід: D - найбільший спільний дільник А і В.

У цьому прикладі використана команда повторення. Вона має вид: Поки <Умова> виконувати <Команда> Виконуючи цю команду, Виконавець перевіряє істинність Умови. Якщо Умова істинна, Виконавець виконує Команду, вказану після слова виконувати і повторює перевірку Умови. Виконання Команди і перевірка Умови повторюються до тих пір, поки Умова істинна. Якщо Умова хибна, Виконавець переходить до виконання команди, наступної за командою повторення. В цьому ж прикладі використаний ще один різновид команди розгалуження - команда виду. Якщо < Умова > то <Команда 1 > інакше < Команда 2 > Виконуючи цю команду, Виконавець перевіряє Умову. Якщо умова виконана, виконується Команда 1, в іншому випадку виконується команда 2. Далі Виконавець переходить до наступної команди. Відмітимо, що команда повторення, як і команди розгалуження, містить у собі інші команди.

2.Визначеність. Виконання алгоритму суворо визначено. Це означає, що на кожному кроку Виконавець не тільки точно виконує команду, але й однозначно визначає наступну команду, що буде виконуватись. Тому повторне виконання алгоритму для одних і тих же вхідних даних у точності повторює перше його виконання. Так, у виконанні алгоритму у прикладі 3 можливі розгалуження, які, однак, однозначно визначені умовами D < 0, D = 0.

3. Масовість. Алгоритми, як правило, описують хід рішення не одної-єдиної задачі, а цілого класу однотипних задач. Так у прикладі 2 описаний алгоритм додавання будь-яких двох дробів. Одна-єдина задача, яка розв’язується Виконавцем у даний момент, визначена значеннями вихідних даних А, В, С, D. Зміна вхідних даних означає розв’язування іншої задачі з цього ж класу задач. Аналогічно, алгоритм прикладу 2 будує середину будь-якого відрізка, заданого його кінцями, а у прикладі 3 за допомогою алгоритму розв’язується будь-яке наведене квадратне рівняння.

4. Результативність. Виконання будь-якого алгоритму повинно бути закінчено через скінченне число кроків (тобто виконання скінченного числа команд) з деяким результатом. Так, у прикладі 2 результат - точка Е - середина відрізку АВ. Алгоритм прикладу 3 видає результат “Розв’язків немає” навіть у тому випадку, коли рівняння не має дійсних коренів, оскільки його дискримінант менше нуля. Відмітимо, однак, що кількість кроків алгоритму, який розв’язує деяку задачу, заздалегідь невідомо і може бути дуже великим, тому властивість результативності конкретного алгоритму часто потрібно спеціально доводити. Так, перевірка властивості результативності в прикладі 4 потребує доведення того, що виконання команди повторення закінчиться за скінчену кількість кроків. Розглянуті приклади показують, що поняття Виконавця є однією з основних абстракцій, які використовують для вивчення алгоритмів. Саме система команд Виконавця і є уточнення набору засобів, за допомогою яких будуються алгоритми. У наших прикладах системи команд Виконавця предметно-орієнтовані. Так, у прикладі 1 Виконавець має справу з цілочисельною арифметикою, а у прикладі 3 - з арифметикою дійсних чисел. Особливо наочно це демонструє Виконавець прикладу 2, команди якого виконують геометричні побудови. Разом з цим очевидно, що існують команди, які повинні входити у систему команд будь-якого Виконавця, який претендує на універсальність у деякій предметній області. Це команди розгалуження, повторення, переходу. Ці команди безпосередньо не вказують на перетворення даних, а лише на керування цими перетвореннями. Незважаючи на всю різноманітність форм представлення інформації та операцій її перетворення, які використовує людина у своїй діяльності, виявилось можливим створення універсального Виконавця, система команд якого дозволяє промоделювати будь-яку іншу систему команд. Таким Виконавцем є ЕОМ.