Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆
  1. Перевірка програми.

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

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

Аналітичний і експериментальний аналіз доповнюють один одного. Аналітичний ана­ліз може бути неточним, якщо зроблені надто сильні припущення для спрощення. В цьо­му випадку можуть бути отримані лише грубі оцінки. З іншого боку, отримати доста­тнє екс­пе­риментальне підтвердження для гарантій будь-якої статистичної достовірності може вия­ви­тися неможливим чи непрактичним. Експериментальні результати можуть бути одноріч­ними.

Тестування також дозволить визначити обчислювальні обмеження програм, вхідні да­ні, на яких програма працює добре, а на яких погано. Так, алго­ритм ETS працює добре для n  6 і погано для n  15. На жаль і перехід не плавний – алгоритм працює погано впро­між­них випадках. Особливо важливо знати, для яких вхідних даних алгоритм розв’язує проблему за експоненціальний час, а для яких – проблема може бути розв’язана за поліноміальний час.

  1. Документування.

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

Приклад2

Тема Пошук лексикографічно найменшого циклічного зсуву заданої стрічки

Постановка задачі

Дано стрічку з l (l>0) символів, які пронумеровані зліва направо від 0 до l‑1. Розглядаються всі можливі її циклічні зсуви. Серед цих циклічних зсувів знайти лексикографічно найменший, тобто вказати номер символу, з якого слід починати зсув, щоб отримати лексикографічно найменшу стрічку. Якщо таких символів декілька – то вказати номер найлівішого з них.

Ця задача має цікаві застосування. Наприклад, за допомогою відповіді на поставлене запитання можна дуже швидко перевірити, чи є дана стрічка нерозкладною (за Рибаком).

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]