1. Побудова і аналіз алгоритмів Формалізація алгоритмів icon

1. Побудова і аналіз алгоритмів Формалізація алгоритмів




Назва1. Побудова і аналіз алгоритмів Формалізація алгоритмів
Сторінка1/19
Дата конвертації23.03.2013
Розмір1.24 Mb.
ТипДокументи
  1   2   3   4   5   6   7   8   9   ...   19


1.Побудова і аналіз алгоритмів

1.1.Формалізація алгоритмів.


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

  • формалізація і створення технічного завдання на вихідну задачу;

  • розробка алгоритму вирішення задачі;

  • написання, тестування, наладка і документування програми;

  • отримання розв’язку вихідної задачі шляхом виконання програми.

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

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

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

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

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

1.2.Покрокове проектування алгоритмів.


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

В основу процесу проектування програми з розбиттям її на достатню кількість дрібних кроків можна покласти наступну послідовність дій:

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

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

  3. Створюється образна модель процесу, який відбувається, використовуються графічні та інші способи представлення, образні „картинки”, які дозволяють краще зрозуміти виконання алгоритму в динаміці.

  4. В образній моделі виділяється найбільш суттєва частина, для якої підбирається найбільш точне словесне формулювання.

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

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

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

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

Схематично узагальнений процес програмування можна представити наступною схемою.



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

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

Третій етап процесу – програмування – забезпечує реалізацію кожного абстрактного типа даних і створення функцій для виконання різних операторів над даними цих типів. На цьому етапі також замінюються всі неформальні оператори псевдомови на код мови програмування. Результатом цього етапу повинна бути виконувана програма. Після її наладки отримують працюючу програму.
  1   2   3   4   5   6   7   8   9   ...   19



Схожі:

1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconПрактична робота №1 Способи представлення алгоритмів. Базові алгоритмічні структури. Типи алгоритмів в-1
Назвіть всі базові структури алгоритмів і дайте їм означення
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconТ. 1 Комп’ютерне моделювання. Основи алгоритмізації (6 год.)
Базові структури алгоритмів: слідування, розгалуження, повторення. Графічні схеми базових структур алгоритмів
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconПрограма для запису алгоритмів; б спеціально створена мова для запису алгоритмів; в мова програмування
Мова, призначена для запису алгоритмів розв’язування задач І вхідних даних для еом, – це
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconТема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів
Алгоритмом називається скінчена послідовність вказівок, виконання яких призводить до досягнення поставленої мети
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconТема: Базові алгоритмічні структури, типи алгоритмів. Виконавець та система команд виконавця
Після ознайомлення з різними формами запису алгоритмів зможемо розпізнати різні за типами команди, а відповідно і алгоритми, які...
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconПрограма для запису алгоритмів; б спеціально створена мова для запису алгоритмів; в мова програмування
В завданнях 1-11 підкресліть правильну відповідь. Розв’язки задач вставте після задачі
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconEnglish 202-11
Дискретний аналіз лекц. Вф-1 Мороховець Теорія алгоритмів та матлогіка пр. 201-11 Доценко
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconІнформації в базі даних. Внесення змін до інформації в базі даних. Поняття про мову програмування. Алфавіт мови. Основні поняття мови: ідентифікатори, числа, рядки, описи. Основні вказівки та їх опис
Базові структури алгоритмів. Основна властивість базових структур. Структурний підхід до конструювання алгоритмів
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconКафедра фізики напівпровідників
Основна увага приділяється теорії чисельних методів, розробці обчислювальних алгоритмів, оцінки точності вичислювальних формул. Курс...
1. Побудова і аналіз алгоритмів Формалізація алгоритмів iconПрактична робота № Програмування алгоритмів розгалужених обчислювальних процесів

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи