Сайт підготовки до олімпіади з інформатики

ЕТАПИ РОЗВ'ЯЗАННЯ ЗАДАЧ НА КОМП'ЮТЕРІ

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

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

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

3. Побудова алгоритму. Наступним етапом є розробка алгоритму обробки інформації на основі побудованої математичної моделі.  Тепер необхідно знайти спосіб розв'язування цієї задачі. Для цього можуть бути застосовані вже відомі методи, проведена їх оцінка, аналіз, відбір або розроблені нові методи. Наприклад, вибір методу розв'язування системи рівнянь, що описує дану математичну модель. Під час створення складних алгоритмів застосовується метод покрокової розробки. Сутність цього методу полягає в тому, що алгоритм розробляється «зверху донизу». На кожному етапі приймається невелика кількість рішень, що призводить до поступової деталізації, уточнення як виконуваної, так і інформаційної структури алгоритму. Такий підхід дозволяє розбити алгоритм на окремі частини — модулі, кожний з яких розв'язує свою самостійну підзадачу. Це дає можливість сконцентрувати зусилля на розв'язуванні кожної підзадачі, що реалізується у вигляді окремої процедури. Для кожного такого модуля визначаються свої методи реалізації алгоритму та структура даних, якими він оперує. Останнім етапом у методі покрокової розробки є об'єднання окремих незалежних модулів у єдине ціле. Для цього між модулями повинні бути встановлені зв'язки, тобто узгоджена передача інформації від одних модулів до інших: результати виконання одних модулів є вхідною інформацією для інших.

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

4. Вибір мови програмування. Алгоритм, призначений для виконання на комп'ютері, має бути записаний мовою програмування. Різноманітність існуючих мов програмування потребує від програміста реальної оцінки складності та характеру задачі. Тільки після цього він зможе здійснити оптимальний вибір мови програмування для реалізації поставленої задачі. Враховуючи можливість розбиття всього алгоритму на окремі модулі, для кожного з них вибір мови програмування можна здійснити окремо. Процес розробки програми, як і алгоритму, може здійснюватися за принципом «зверху донизу». Це дозволяє одержати добре структуровану програму, читання і розуміння якої значно полегшене.

5. Складання програми. Цей етап потребує лише знання вибраної мови програмування. Суть його полягає в тому, щоб на основі розроблених алгоритмів і структур даних створити програму для комп'ютера.

6. Компіляція програми. Переведення програми на машинну мову здійснюється за допомогою спеціальних програм — компіляторів. Однією з їх функцій є перевірка відсутності в програмі синтаксичних помилок. Не тіште себе надією, що ваша, навіть найпростіша, програма написана бездоганно. Серед програмістів побутує прислів'я:
«Якщо програма не має помилок, це означає, що у вас поганий компілятор!!!»

7. Налагодження програми, контрольний прорахунок. Виправлення усіх синтаксичних помилок у програмі на попередньому етапі .зовсім не позбавляє вас від помилок іншого типу — змістовних, логічних. Вони з'являються під час помилкового трактування умови поставленої задачі, через недосконалість математичної моделі або недоліки у побудованому алгоритмі, що призводить до одержання помилкового результату. Такі помилки не можуть бути усунені на стадії компіляції, тому що для їх виявлення необхідна інформація про сутність самої задачі. Це може зробити лише сам розробник. Процес налагодження програми полягає втому, що готується система тестів, за допомогою якої перевіряється робота програми в різних можливих режимах. Кожний тест містить набір вхідних даних, для яких відомий результат. Для більшості програм виникає необхідність добору не одного, а серії тестів, щоби перевірити якнайбільше можливих ситуацій, які можуть виникнути в процесі роботи програми. Якщо для всіх тестів результати роботи програми збіглися з розрахунками, то можна вважати, що логічних помилок немає.

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

Караванова Т.П., Основи алгоритмізації та програмування. 750 задач з рекомендаціями та прикладами (посібник)