Основи алгоритмізації

Основи сучасного програмування Основи сучасного програмування Основи сучасного програмування Основи сучасного програмування Основи сучасного програмування Основи сучасного

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

Метою програмування є опис процесів обробки даних.

Введемо деякі означення.

Означення 1.1. Дані – це зображення фактів та ідей у формалізованому вигляді, придатному для передавання й переробки в деякому процесі.

Означення 1.2. Інформація – це вміст, який надається даним при їхньому зображенні.

Означення 1.3. Обробка даних – це виконання систематичної послідовності дій з даними.

Означення 1.4. Сукупність носіїв даних, які використовуються за будь-якої обробкиі даних, називатимемо інформаційним середовищем.

Означення 1.5. Набір даних, що містяться в будь-який момент в інформаційному середовищі, називатимемо станом цього середовища.

Означення 1.6. Процес обробки даних можна визначити як послідовність змін станів деякого інформаційного середовища.

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

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

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

Основна увага у теорії алгоритмів приділяється методам задання (описи, конструювання) алгоритмів – форматам запису.

Загальноприйнято оперувати мовою блок-схем. Інший різновид мови задання алгоритмів – це діаграми Насси – Шнейдермана. Для спрощення ми використовуватимемо словесний опис. Однак навіть таке спрощення надалі дозволить нам швидко перейти до написання програм.

Алгоритми мають такі властивості:

Елементарність. Кожна команда з набору містить указівку виконати деяку елементарну дію, що однозначно розуміється й точно виконується.

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

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

Результативність. Виконання будь-якого алгоритму має закінчитися через скінченну кількість кроків із деяким результатом.

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

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

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

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