Основні інформаційні структурних даних .

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

Тип списків.

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

Зауваження:

Поточний елемент – це той єдиний елемент списку, який в даний момент доступний для обробки.

Базисними операціями над списками є:

1) створення пустого списку;

2) перевірка списку на пустоту;

3) перевірка існування попереднього або наступного елементу;

4) взяття в якості поточного елемента першого, останнього або наступного елементу списку;

5) вибір значення поточного елементу;

6) заміна значення поточного елементу на деяке значення базисного типу;

7) знищення поточного елементу зі списку із застосуванням в якості поточного попереднього або наступного;

8) занесення деякого значення базисного типу в список перед або після поточного елементу.

Тип черги.

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

1) створення пустої черги;

2) перевірка черги на пустоту;

3) вибір першого елемента з одночасною його зміною;

4) занесення деякого значення базисного типу в якості нового останнього елемента черги.

Тип стеків.

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

Набір базисних операцій над стеками складається з п’яти операцій:

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

Тип дерев:

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

Дерево в якому список піддерев є пустим називають тривіальним, а коріння називають листком.

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

Для дерева список базисних операцій може складатися з:

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

Тип графів

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

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

Тип орієнтованих графів (Орг-графи)

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

Методи розробки алгоритмів:

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

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

1) забезпечення оптимального часу розв’язку задачі;

2) забезпечення оптимального використання ресурсів;

3) забезпечення необхідної точності обчислення;

4) мінімальні вартісні затрати;

5) можливість використання стандартних підпрограм.

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

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

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

Інший підхід - об’єктно-орієнтоване програмування.