Лекція Р Тема: Формалізація та алгоритмізація обчислювальних процесів

Скачати 150.01 Kb.

Назва	Лекція Р Тема: Формалізація та алгоритмізація обчислювальних процесів
Дата	14.04.2013
Розмір	150.01 Kb.
Тип	Лекція

bibl.com.ua > Математика > Лекція

Лекція Р_1.
Тема: Формалізація та алгоритмізація обчислювальних процесів
Мета: Ознайомити учнів з поняттям обчислювального процесу, розглянути основні етапи розв’язування задачі. Розглянути основні схеми алгоритмів та їх властивості
План лекції

Етапи розв'язування задачі.
Класифікація мов програмування.
Алгоритм і його властивості.
Основні типи алгоритмів.

1. Етапи розв'язування задачі.

Окремі етапи розв’язування задачі на ПК взаємопов’язані: наступні етапи залежать від реалізації попередніх, після виконання поточного етапу може виникнути потреба повернення до попередніх етапів для їх уточнення і пошуку нових розв’язків.

Перший етап – формулювання задачі. На цьому етапі фахівець професійною мовою формулює завдання, визначає вхідні дані для його розв’язування, дає чіткі вказівки стосовно результатів розв’язку і форми, в якій вони повинні бути отримані. Для цього етапу, згідно стандарту, входять такі розділи: організаційно-економічна суть задачі, опис вхідних і вихідних даних, визначення мети розв’язування задачі, аналіз обмежень на вхідні і вихідні дані.

Другий етап – математичне формулювання задачі (математичне моделювання) містить у собі запис умов задачі з допомогою формул, рівнянь, нерівностей, графіків, таблиць тощо. Скласти математичну модель задачі – це визначити зв’язок вихідних даних з вхідними за допомогою математичних співвідношень з урахуванням існуючих обмежень на вхідні, проміжні та вихідні дані, одиниці їх виміру, діапазон зміни тощо.

Математичне формулювання задачі завершується вибором методу її розв’язку.

Третій етап – складання алгоритму розв’язування задачі, згідно з вибраним методом розв’язку.

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

Четвертий етап – програмування, тобто запис складеного алгоритму мовою програмування.

У сучасному програмуванні існує декілька підходів до програмування: структурне (детальне), модульне й об’єктно-орієнтоване програмування.

При структурному підході, якщо алгоритм розв’язування задачі складено правильно, програмування задачі однією з багатьох мов програмування трудношів не викликає.

Базовий підхід до будь якої задачі модульного програмування такий: “розділювати і керувати”, тобто метою декомпозиції програми є створення окремих модулів, які у свою чергу, представляють невеликі програми, що взаємодіють одна з одною за чітко визначеними правилами.

Модульне програмування використовує методологію, орієнтовану на обробку. Його основні ознаки:

кожен модуль реалізує одну і лише одну незалежну функцію;
кожен модуль має єдину точку введення-виведення;
розмір модуля потрібно мінімізувати;
кожен модуль може бути записаний мовою програмування розробником чи програмістом і може бути протестований окремо;
уся програма складається з протестованих модулів і тому саме легко перевіряється.

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

До методології розроблення програм, орієнтованої на дані, відносять об’єктно орієнтоване програмування (ООП) та проектування концептуальних баз даних.

Об’єктно орієнтоване програмування – домінуючий зараз спосіб програмування, який забезпечує модульність програм за рахунок розділення пам’яті на об’єкти, що вміщують дані, і процедури (методи), яким відомо, як маніпулювати з цими даними. Прикладами об’єктів можуть слугувати: вікно діалогу, командна кнопка, текстове поле, форма, звіт, таблиця, принтер, монітор, диск тощо. Зазвичай об’єкт відповідає за виконання деякого невеликого набору зв’язаних завдань та за підтримку інформації відносно його внутрішніх даних. Якщо об’єкт повинен виконати дії, які не входять до кола його “обов’язків”, він повинен мати доступ до об’єкта, який це завдання може виконати. В ООП у цьому випадку говорять, що об’єкти-клієнти передають повідомлення об’єктам-серверам.

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

П’ятий етап – тестування і відлагодження програми - це перевірка правильності роботи програми на комп’ютері та виправлення знайдених у ній помилок.

Тест – це спеціально підібрані вхідні дані задачі в сукупності з тими результатами, які повинна видавати програма при обробленні цих даних. При складанні тестів необхідно забезпечити перевірку всіх гілок програми. Розробка тесту для для перевірки працездатності складних програм є досить непростим завданням. Тому для відлагодження програм, складених тією чи іншою програмування, існують спеціальні програми-відлагоджувачі (debugger).

Шостий етап – обчислення (розв’язок задачі) на комп’ютері за складеною і відлагодженою програмою та аналіз отриманих результатів. Обчислення виконуються для деякого набору реальних вхідних даних, а аналіз отриманих результатів може слугувати підтвердженням (або запереченням) правомірності всіх попередніх етапів підготовки задачі до розв’язування.

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

2. Класифікація мов програмування.

Сучасні ЕОМ не настільки досконалі, щоб розуміти програми, складені на будь-якій мові, що використовує людина – російській, українській, англійській, польській… Тому команди, призначені для машини, необхідно записувати в зрозумілій їй формі. З цією метою використовують штучні мови, які названі алгоритмічними або мовами програмування. Алфавіт, словарний запас та структура цих мов вибираються таким чином, щоб вони були однаково зручні як людині (програмісту), що працює з програмою так і ЕОМ, яка повинна легко розшифровувати та виконувати задаваєму програмою послідовність команд. Тому, мову програмування можна вважати засобом спілкування між людиною та машиною.

Системи програмування призначені для полегшення та для часткової автоматизації процесу розробки та відлагодження програм. Основними компонентами цих систем є транслятори з мов високого рівня: Паскаль, Сі, Бейсік та ін. Особлива роль належить Ассамблерам. Програму мовою Ассамблера називають машинно-орієнтованою. Мовою Ассамблера користуються, як правило, системні програмісти. Ассамблери перетворюють програми, які представлені у машиноорієнтованих мовах, на машинну мову.

Транслятори мов програмування.

Транслятором мови програмування називається програма, що здійснює переклад тексту програми з мови програмування в машинні коди.

Залежно від способу перекладу з вхідної мови (мови програмування) транслятори поділяються на компілятори та інтерпретатори.

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

Комплекс засобів, що містить вхідну мову програмування, транслятор, машинну мову, бібліотеки стандартних програм, засоби відлагодження відтрансльованих програм і компонування їх в єдине ціле, називається системою програмування.

3. Алгоритм і його властивості.

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

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

Розглянемо послідовний алгоритм, де кожна наступна команда починає виконуватися після закінчення виконання попередньої.

Приклад 1. Обчислити

Алгоритм 1. Щоб розв’язати задачу, потрібно виконати три вказівки:

Виконати віднімання 92 – 32 і запам’ятати результат (60).
Виконати додавання 309 + 51 і запам’ятати результат (360).
Виконати ділення 360 : 60 і запам’ятати результат (6).

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

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

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

Команди виконавця. Кожен виконавець може виконати певну кількість команд, які називаються допустими командами виконавця.

Розглянемо таких виконавців: людину, робота й комп’ютер.

Людина здатна виконати практично необмежену кількість різних команд: іти, лічити, шити, пекти, їсти, спати тощо. Тому на дії людей розумні обмеження накладаються законами, мораллю й сумлінням.
Кількість команд для механічних виконавців є значно меншою. Наприклад: вперед, направо, наліво – це допустимі команди робота. Робот не виконує таких команд, як їсти чи пити.
Додавати, віднімати, множити, малювати, грати – це команди для комп’ютера, але йому не можна давати команд, характерних для людини чи робота, наприклад, команд для переміщення у просторі.
Команди, які не може виконати виконавець, називаються недопустими.

3.2. Способи опису алгоритмів:

словесний;
формульний;
графічний;
алгоритмічною мовою.

Розглянемо загальний вигляд алгоритму.

Алгоритмові даємо назву, команди нумеруємо. Назву пишемо з великої літери. Отже, алгоритм матиме такий вигляд:

Алгоритм. Назва

Команда 1.
Команда 2.
Команда 3.

…

n. Команда n.
Приклад 2. Складемо алгоритм переходу вулиці.

Алгоритм Перехід

Подивитися наліво.
Якщо немає перешкоди, то йти до середини вулиці,

інакше пропустити машини,

йти до середини вулиці.

3. Подивитися направо.

4. Якщо немає перешкоди, то завершити перехід,

інакше пропустити машини,

завершити перехід.

Розгляньте алгоритм. Команди 1 та 3 називатимемо простими, а 2 і 4 – складеними.

Запитання. Чи можна в алгоритмі поміняти будь-які дві команди місцями, чи буде новий алгоритм правильним?

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

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

Невизначеність. Наприклад, виникне в алгоритмі 1, якщо в знаменнику буде записано: 92 – 92 (ділення на нуль не допустиме).

Скінченність алгоритму. Алгоритм повинен бути скінченим. Це означає, що послідовність команд, які потрібно виконати, мусить бути скінченою.

Алгоритм 1 скінчений. Він складається з трьох дій. Кожна дія реалізується скінченою кількістю елементарних арифметичних операцій. Нескінченну кількість дій передбачає правило переведення деяких звичайних дробів, таких як 5/3, у нескінченні десяткові дроби.

Результативність алгоритму. Алгоритм результативний, якщо він дає результати (які можуть виявитися і неправильними). Наведені вище алгоритми є результативними.

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

Алгоритм 1 та Перехід є правильними. Помінявши місцями в алгоритмі Перехід будь-які дві команди, отримаємо неправильний алгоритм.

Формальність алгоритму. Алгоритм формальний, якщо його можуть виконати не один, а декілька виконавців з однаковими результатами. Цю властивість ще називають однозначністю алгоритму.

Наведені алгоритми задовольняють цю умову. Їх можуть виконати багато виконавців.

Масовість алгоритму. Алгоритм масовий, якщо він придатний для розв’язування не однієї задачі, а низки подібних задач (тобто задач певного класу).

Алгоритм 1 не є масовим. Алгоритм Перехід є масовим: так потрібно переходити всі вулиці.

Прикладами масових алгоритмів є загальні правила, якими користуються для множення, додавання, ділення двох багатозначних чисел, бо вони застосовні для будь-яких пар чисел.

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

Приклад 3. Складемо алгоритм розв’язування лінійного рівняння.

Запишемо лінійне рівняння у загальному вигляді:

аx + b = c.

Метод розв’язування описує формула

х =

Цю формулу можна розглядати як алгоритм, який застосовний для будь-яких чисел a, b та с, де а  0. Тому він є масовим.

4. Основні типи алгоритмів.

4.1. Блок-схеми.

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

Операція обробки, присвоювання

2. Операція вводу-виводу

3. Операція перевірки умов

4. Вивід на друк

5. Кінець та початок програми
В літературі можна зустріти й інші фігури.

Послідовність виконання дій визначається лініями. Напрям ліній зверху вниз та зліва направо беруть за основний і стрілками не позначають. Напрям ліній потоку справа наліво та знизу вгору показують стрілкою.

Блок-схеми алгоритмів прийнято читати зліва направо та зверху вниз. В блок-схемах переважають обчислювальні та логічні блоки: перші обчислюють по формулам (їх зображають прямокутниками з вказанням характеру обчислень), а другі – перевіряють деякі умови. Вказівки про обчислення задають по різному. Алгоритм будь-якої задачі заключається в граничні символи (овали) “початок” та “кінець”. Першим в алгоритмі виконується блок до якого веде стрілочка від блоку “початок”; закінчується обчислювальний процес блоком “кінець”. Таким чином, лінія потоку виходить з символу “початок” та входить в блок “кінець”. Між цими двома блоками розміщуються всі інші блок-схеми. Ніяких строгих правил розбиття алгоритму на окремі блоки при побудові схем не існує. У блоки можна виділяти виконання окремих арифметичних операцій, обчислення за формулами і навіть окремі алгоритми, які розв’язують більш вузькі класи задач. На наступних етапах алгоритмізації деякі з блоків можна докладніше деталізувати, оформивши їх у вигляді окремих схем.

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

4.2. Типи алгоритмів.

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

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

Чисельні алгоритми

Лінійні

Розгалужені

Циклічні

Арифметичні

Ітераційні

Мал.1

ІІ. Лінійні алгоритми (слідування).

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

Приклад 1. Розглянемо алгоритм Ранок.

алгоритм Ранок.

Встати о 6-й годині
Виконати гімнастичні вправи.
Вмитися.
Поснідати.
Вийти з дому о 7-й годині.

Це є приклад лінійного алгоритму.

ІІІ. Розгалужені алгоритми.

Розгалужені алгоритми передбачають вибір однієї з кількох можливих послідовностей дій залежно від значень вхідних даних або проміжних результатів. Кожну з таких послідовностей називають віткою розгалуження. Розгалужений алгоритм містить принаймні один логічний оператор (блок).

Приклад 2. Скласти схему алгоритму нарахування прибуткового податку П, коли відомо, що

П=	0, якщо Z  60,
	0,082 * Z, якщо 60 < Z  100,
	0,082 * 100 + 0,13 * (Z – 100), якщо Z > 100,

Де П – прибутковий податок, Z – заробітна плата.

Розв’язання. Залежно від значення заробітної плати Z прибутковий податок П можна обчислити по одній з трьох віток. Будуючи алгоритм, треба скористатись двома послідовними розгалуженнями у двох напряках: спочатку відокремимо перший випадок (Z  60) від двох наступних, а потім – другий від третього, перевіряючи умову Z  100. (мал.2)

IV. Циклічні алгоритми.

Циклічні алгоритми дають змогу здобути результат багаторазовим повторенням певної послідовності дій, що називаються циклом. Якщо число повторень циклу задане, то такі цикли називають арифметичними. Якщо кількість повторень циклу наперед невідоме, а визначається тільки в процесі застосування алгоритму, то такі цикли називають ітераційними.

Оскільки кількість повторень арифметичного циклу наперед відома, то його можна організувати за допомогою лічильника циклу. Під лічильником циклу розумітимемо змінну k, яка підраховує кількість виконань циклу. Лічильники циклів можна використовувати в режимах додавання і віднімання. Розглянемо використання лічильника в режимі додавання.

Приклад 4. Обчислити значення суми

S = 1 + 2² + 3² + 4² + … + n².

Розв’язання. У цьому алгоритмі оператори 2-3 підготовляють обчислювальну частину циклу (оператори 4-5) до виконання першого обчислення. Вони становлять підготовчу частину циклічного алгоритму. Оператори 4-5 у процесі застосування алгоритму виконуються n раз і дають можливість обчислити шукану суму S. При кожному виконанні циклу значення змінної k збільшується на одиницю, а значення S – на k². Перевірка закінчення циклу виконується за допомогою оператора умовного переходу шляхом порівняння числового значення лічильника циклу k із заданим числом n – еталоном циклу. Виконання циклу повторюється до виконання умови k = n (мал. 3).

Цикл може бути двох видів: цикл поки, цикл до.

До циклу поки входять логічний блок Р і функціональний блок А, яким у найпростішому випадку є арифметичний блок (серія арифметичних операторів). Блок А, що називають тілом циклу, розміщують за блоком Р. Блок А виконується доти, поки істинною є умова Р. Якщо умова Р, яка перевіряється логічним блоком, не виконується вже при першій перевірці, то оператори тіла циклу А не виконуються жодного разу (мал. 4).

У циклі до функціональний блок А розміщується до перевірки логічної умови Р. У цьому разі тіло циклу виконується принаймні один раз (мал. 5).
Цикл поки Цикл до

ні

так

так ні

Мал. 4 Мал. 5
Конструюючи алгоритми, використовують тільки зазначені базові структури: слідування, розгалуження і цикл. При цьому можуть замінювати кожний функціональний блок будь-яким структурним елементом. Можливість такої заміни дає змогу будувати як завгодно складні алгоритми методом послідовного уточнення.

Метод послідовного уточнення полягає в тому, що використовують три типи структурних схем алгоритмів:

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

Допоміжні алгоритми (підпрограми).

Структурний підхід до конструювання алгоритмів тісно пов’язаний з використанням допоміжних алгоритмів. Допоміжним називатимемо алгоритм, що використовується в іншому (основному) алгоритмі як його складова частина.

Приклад: Алгоритм обчислення площі за формулою герона є допоміжним алгоритмом, який в основному алгоритмі використовується тричі.

Приклад: Алгоритм день

Виконати алгоритм Ранок.
Виконати алгоритм Технікум.
Виконати алгоритм Вечір.

Схожі:

ТЕМА: Табличний процесор МЕТА: засвоїти технологію адресації в Excel, проведення розрахунків, використання логічних функцій для реалізації обчислювальних...	Алгоритмізація та програмування”: диференційований підхід до підбору задач, їх змісту та рівню Орієнтація на розв’язування цікавих задач і розвиток алгоритмічного мислення – ось основне завдання розділу “Алгоритмізація та програмування”....
23 Алгоритмізація Алгоритмізація. Поняття алгоритму. Властивості алгоритму. Способи опису алгоритмів. Навчальна алгоритмічна мова. Базові структури...	Уроку І. Організація класу Мета: навчальна: ознайомити з деякими відомостями з історії виникнення обчислювальних пристроїв; закріпити знання інформаційних процесів,...
Лекція №7 Тема: Соціальні групи Мета вивчення: розкрити сутність соціальної групи, яка має психологічну основу; відзначити, що вона ґрунтується на активізації психічних...	Комплексне кваліфікаційне завдання №1 з професії 7241. 1 „Електромеханік... Ви працюєте електромеханіком з ремонту та обслуговування лічильно – обчислювальних машин III розряду. Вам пропонується
Комплексне кваліфікаційне завдання №1 з професії 7241. 1 „Електромеханік... Ви працюєте електромеханіком з ремонту та обслуговування лічильно – обчислювальних машин IV розряду. Вам пропонується	ІНДИВІДУАЛЬНИЙ ПЛАН РОБОТИ МАГІСТРА Прізвище, ім’я, по батькові:... Для вирішення завдання на цей час існує багато евристичних процедур, що Тому розроблення формальної моделі опису роботи планувальника...
Тема Лекція №1 „Міграційне право як наука та навчальна дисципліна”(тези) Наука міграційного права має подвійний предмет вивчення. По-перше, це загальні принципи, інститути і норми регулювання міграційних...	Навчально-тематичний план з предмета “ Технології” для професії "Оператор... Оператор компютерного набору. Електромеханік з ремонту та обслуговування лічильно-обчислювальних машин

Додайте кнопку на своєму сайті:
Портал навчання