Основи сучасного програмування Основи сучасного програмування Основи сучасного програмування Основи сучасного програмування Основи сучасного програмування Основи сучасного
Поняття алгоритму
Метою програмування є опис процесів обробки даних.
Введемо деякі означення.
Означення 1.1. Дані – це зображення фактів та ідей у формалізованому вигляді, придатному для передавання й переробки в деякому процесі.
Означення 1.2. Інформація – це вміст, який надається даним при їхньому зображенні.
Означення 1.3. Обробка даних – це виконання систематичної послідовності дій з даними.
Означення 1.4. Сукупність носіїв даних, які використовуються за будь-якої обробкиі даних, називатимемо інформаційним середовищем.
Означення 1.5. Набір даних, що містяться в будь-який момент в інформаційному середовищі, називатимемо станом цього середовища.
Означення 1.6. Процес обробки даних можна визначити як послідовність змін станів деякого інформаційного середовища.
Описати процес – означає визначити послідовність станів заданого інформаційного середовища. Якщо ми хочемо, щоб за заданим описом необхідний процес породжувався автоматично на комп'ютері, то необхідно, щоб опис був формалізованим. Такий опис називається програмою.
|
|
Основною у процесі програмування є розробка алгоритму – один із найскладніших етапів розв'язання задач з використанням комп'ютера. Візьмемо за основу уявлення про алгоритм як опис деякого обчислювального процесу. Визначальною особливістю обчислювального процесу є можливість розчленувати його на окремі дискретні дії. Таким чином, для написання алгоритму нам належить лише по пунктах їх перелічити. Алгоритм – це деяке правило перетворення інформації, застосування якого до заданої (початкової) інформації приводить до результату – нової інформації.
Кожне правило алгоритму містить точний опис деякої елементарної дії з перетворення інформації і вказівки на інструкцію, яку необхідно виконати.
Основна увага у теорії алгоритмів приділяється методам задання (описи, конструювання) алгоритмів – форматам запису.
Загальноприйнято оперувати мовою блок-схем. Інший різновид мови задання алгоритмів – це діаграми Насси – Шнейдермана. Для спрощення ми використовуватимемо словесний опис. Однак навіть таке спрощення надалі дозволить нам швидко перейти до написання програм.
Алгоритми мають такі властивості:
Елементарність. Кожна команда з набору містить указівку виконати деяку елементарну дію, що однозначно розуміється й точно виконується.
Визначеність. Виконання алгоритму строго визначене. Це означає, що на кожному кроці треба не лише точно виконати команду, але й однозначно визначити наступну. Тому повторне виконання алгоритму для одних і тих самих початкових даних точно повторює перше його виконання.
|
|
Масовість. Алгоритми зазвичай описують хід розв'язання не однієї-єдиної задачі, а цілого класу однотипних задач.
Результативність. Виконання будь-якого алгоритму має закінчитися через скінченну кількість кроків із деяким результатом.
Однак кількість кроків алгоритму, який розв'язує деяку задачу, заздалегідь невідома й може бути дуже великою. Тому властивість результативності конкретного алгоритму часто необхідно спеціально доводити, щоб результат був досяжним.
Алгоритми в процесі роботи для отримання результату обробляють деякі дані, тобто мають вхід (вхідні дані) і вихід (результат). Вхідні дані потрібні не для кожного алгоритму.
Крім вхідних і вихідних, зазвичай алгоритм передбачає тимчасове формування проміжних даних (ще їх називають допоміжними). Тому ще однією характеристикою алгоритму є обсяг пам'яті, яку він використовує.
При конструюванні алгоритму слід строго визначити кожен його крок, передбачивши будь-які можливі стани процесу й відповідні інструкції для їхньої обробки. Лише такий алгоритм гарантує однозначне отримання необхідного результату та класифікується як детермінований. Щодо такого алгоритму можна стверджувати: його неодноразове застосування до однакових вхідних даних завжди приводить до одного й того самого результату. Стохастичні алгоритми ми не розглядатимемо.