СИСТЕМА АВТОМАТИЧНОГО ТЕСТУВАННЯ КОНСОЛЬНИХ ПРОГРАМ

"ACM Contester"

Семен Юрій Володимирович, Бабіля Руслан Васильович, Яремчук Назарій Іванович, Україна

Керівник: аспірант кафедри програмування Білецький Василь Миколайович

Львівський Національний Університет, факультет прикладної математики та інформатики

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

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

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

Цю, на перший погляд, досить складну проблему ми вирішили наступним чином:

Введемо деякі обмеження та уточнення:

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

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

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

Розроблена нами система працює в режимі 24/7 і зарекомендувала себе як надійна, стабільна система, яке не потребує ніяких втручань у її роботу. Завдяки цьому, користувачі системи мають змогу у будь-який, зручний для них, час перевірити чи правильно побудований алгоритм.

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

На даний момент у системі зареєстровано понад 170 користувачів та понад 50 завдань олімпіадного рівня різної складності. Зареєстровано понад 8 тисяч запитів на перевірку алгоритму та проведено 5 відкритих інтернет олімпіад і понад 10 олімпіад факультетського рівня.