Алгоритм формування рейтингових списків абітурієнтів з урахуванням пріоритетності заяв



Стаття | Article    

Download

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

The algorithm for formation rating list of entrants according to their priority

Shapoval Oleksandr Serhiiovych, student, faculty of Informatics and Computer Science, department of Technical Systems Automation and Control, National technical university of Ukraine “Kyiv Polytechnic Institute”

Ukraine, Kiev

The article describes algorithm for formation rating list of entrants according to theirpriority. It allows calculating passing scores of specialties with quite high accuracy before the admission time lineended.

Keywords: data analysis, university admission, abit-poisk, vstup info

Вступ

Ключовим етапом в житті кожної людини є вступ до вищого навчального закладу. Завдяки впровадженню системи ЗНО у кожної дитини є чудовий шанс показати свої знання, склавши вибрані тести незалежного оцінювання та вступити до омріяного ВНЗ. Після отримання результатів складання тестів абітурієнт має змогу подати певну кількість заяв до вищих навчальних закладів. В заяві абітурієнт обов’язково повинен вказати ії пріоритетність – заздалегідь встановлена вступником черговість заяв (від 1 до 15, де 1 – найбільш пріоритетна заява)[1]. Цей показник використовується при формуванні списку після закінчення подання заяв відвступників. Для відстеження своїх рейтингових позицій був створений спеціальний сайт – «ІС Конкурс»[2]. За допомогою цього ресурсу кожен бажаючий може відслідковувати заяви абітурієнтів. Проблема полягає в тому, що вступник не має змоги до закінчення терміну подання заяв ознайомитися із попередньо сформованими рейтинговими списками із врахуванням пріоритетності заяв. Наявність таких попередньо сформованих даних надасть абітурієнтам, які, наприклад, не потрапляють на бюджет, подати нову заяву на той напрям, в якому програма розрахувала недобір на бюджетні місця. Таким чином вирішуються дві проблеми: перша – для вступників, які не є рекомендованими на зарахування за кошти держави , мають можливість все ж таки потрапити на бюджет; друга проблема – проблема наявності недобору на деякі спеціальності. Попередньо сформовані рейтингові списки дозволять керівникам ВНЗ повідомляти вступникам про наявні бюджетні місця, або коректувати державне замовлення, шляхом відмови бюджетних місць на тих напрямах, де присутній недобір.

Актуальність даної роботи полягає у необхідності вдосконалення відкритих систем для надання додаткової інформації під час вступної кампанії – вступу абітурієнтів до вищих навчальних закладів України.

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

Опис алгоритму

1.1 Підготовка вхідних даних

Для правильної роботи алгоритму перш за все необхідно визначитись із джерелом відкритих даних. Було використано інформаціюіз «ІС Конкурс» для збору та обробки основних даних, сайт «Перевірка сертифікатів зовнішнього незалежного оцінювання 2015 року»[3] – для ідентифікації абітурієнтів. У цій статті розглянуто приклади формування рейтингових списків за 28 липня 2015 року – за 5 днів до закінчення прийому заяв від вступників. На підготовчому етапі було створено тритаблиці – спеціальності вузів (university_specialities), абітурієнти (enrollees), заяви абітурієнтів (enrolle_statements).

Таблиця university_specialities.

Обов’язкові поля:

· university_id – назва або ідентифікатор вузу

· speciality_code – шифр спеціальності

· speciality_id – унікальний ідентифікатор запису

· free_places – кількість бюджетних місць

· speciality_k – коефіцієнт квоти для вступу поза конкурсом

· is_crrection_complete – показник завершення формування списку за даним напрямом

Обов’язково в таблицю слід вносити лише ті спеціальності, за якими передбачена пріоритетність заяв.

Таблиця enrolle_statements.

Обов’язкові поля:

· statement_id – ідентифікатор заяви

· enrolle_full_name – піб абітурієнта

· speciality_id – ідентифікатор конкретної спеціальності конкретного вузу

· statement_pk – правона поза конкурсний вступ

· statement_pch – правона першочерговий вступ

· statement_score – конкурсний бал заяви

· statement_target_direction – цільове направлення

· statement_university_status – статус заяви – рекомендований (1), не рекомендований (0)

· statement_university_tmp_status – тимчасовий статус заяви: не рекомендований (0), рекомендований (1), ця заява неможе братись участь у наданні рекомендації, оскільки абітурієнта вжере комендовано на іншому напрямку за вищим пріоритетом (3)

Таблиця enrolles. Заповнюється за допомогою виокремлення унікальних записів ПІБ із таблиці та додатковою перевіркою на сервісі «Перевірка сертифікатів зовнішнього незалежного оцінювання 2015 року». Даний сервіс після вводу даних видає перелік предметівЗНО даної особи. Якщо є кілька вступників з однаковими ПІБ – система видасть відповідну інформацію. Таким чином можна визначати абітурієнтів з однаковим ПІБ та однозначно їх ідентифікувати лише за допомогою відкритих Інтернет ресурсів.

Обов’язкові поля:

abiturient_id – ідентифікатор абітурієнта

abiturient_full_name – ПІБ абітурієнта

abiturient_rec_statement_id – ідентифікатор рекомендованої заяви на бюджет з найвищим пріоритетом

statement_rec_recount – кількість наданих рекомендацій до зарахування набюджет

1.2 Розробка алгоритму

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

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

ЕТАП 1.

  1. Отримати всі записи із таблиці спеціальності вузів (university_specialities), які задовольняють умові is_correction_complete = 0. Якщо такі записи існують – перейти до пункту 2, інакше – алгоритм завершив свою роботу.

  2. Для кожного запису із пункту 1 виконати наступні дії:

· Отримати кількість рекомендованих заяв – позначемо буквою A

· Отримати кількість можливих рекомендацій – B. Цей вираз задовольняє умові statement_university_status = 0 таstatement_university_tmp_status = 0

Якщо кількість можливих рекомендацій B більше нуля та кількість бюджетних місць даної спеціальності теж більше нуля – перейти до пункту 2.1, інакше – для запису даної спеціальності поставити позначку is_correction_complete = 1 та перейти до пункту 3.

2.1 Виконати наступні дії

· Отримати кількість рекомендованих заяв зі статусом statement_pk = 1 – C.

· Отримати кількість можливих рекомендацій заяв зі статусом statement_pk = 1 – D.

Якщо з числа можливих рекомендацій залишились лише заяви зі статусом statement_pk =1 – для запису даної спеціальності поставити позначку is_correction_complete = 1 та перейти до пункту 3, інакше – перейти до пункт 2.3.

2.3 Виконати наступні дії

· Отримати кількість вільних місцьдля надання рекомендацій на дану спеціальність – E

Якщо E > 0 – перейти до пункту 2.4, інакше – для запису даної спеціальності поставити позначку is_correction_complete = 1 таперейти до пункту 3.

2.4 Отримати із таблиці заяви абітурієнтів (enrolle_statements), попередньо відсортовані за спаданням записи за наступними полями: statement_target_direction, statement_pk, statement_score, statement_pch . Обрати лише перші n відсортованих записів, де n = E – кількість вільних місць для надання рекомендацій на дану спеціальність. Для кожного запису заяви абітурієнта виконати наступні дії:

· враховуючи квоту заяв для вступу поза конкурсом statement_pk встановити поле statement_university_tmp_status = 1

Таким чином в цьому пункті ми тимчасово рекомендуємо до зарахування нову партію заяв абітурієнтів з урахуванням конкурсного балу вступника та інших полів за умови наявності вільних місць. Далі переходимо до пункту 3.

ЕТАП 2.

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

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

Після закінчення другого етапу алгоритм знову переходить до пункту 1.

1.3 Результат роботи алгоритму

Результат роботи алгоритму – сформовані рейтингові списки із урахуванням пріоритетності заяв. За такими списками дуже легко вирахувати недобір та прохідний бал на бюджет. Точність таких даних у порівнянні із офіційними списками залежить від деяких факторів, а саме: · чим раніше до закінчення прийому заяв від абітурієнтів буде розрахований рейтинговий список – тим більша неточність розрахунку

· за допомогою відкритих даних неможливо отримати квоту на зарахування абітурієнтів поза конкурсом. Вам потрібно самостійно підібрати квоту для всіх спеціальностей. Отже алгоритм на основі лише відкритих даних не може дати точність 100% співпадання з офіційно сформованими рейтинговими списками, які зазвичай доступні у «ІС Конкурс» після кількох днів після завершення прийому заяв від абітурієнтів

Для реалізації даного алгоритму використана СУБД Mysql для зберігання даних та мова програмування PHP для безпосередньої реалізації алгоритму.

Нарисунку нижче представлено фрагмент сформованого списку

Рисунок 1 – фрагмент розрахованого списку із урахуванням пріоритетності в системі пошуку абітурієнтів «Абіт Пошук»[4]

На рисунку 1 навпроти кожної заяви присутня колонка «Куди». Вона означає, куди абітурієнт може бути рекомендованим на зарахування за кошти держави. Якщо навпроти заяви значення цієї колонки дорівнює «Сюди» - це значить, що програма розрахувала проходження абітурієнтана бюджет саме на цей напрям. Також значення може мати прочерк – це означає, що алгоритму не вдалося рекомендувати абітурієнта на місця держзамовлення. Віншому випадку – буде відображено назву ВНЗ, напрям та пріоритет заяви, яка була рекомендована до зарахування.

Рисунок 2 – залежність точності розрахованих рейтингових списків від допустимої похибки

Було проаналізовано точність роботи алгоритму на прикладі рейтингових списків НТУУ «КПІ» (рис. 2), в даному випадку точність роботи алгоритму формування списків із урахуванням пріоритетності заяв – це таке значення, наскільки прохідний бал, розрахований на основі сформованих алгоритмом списків відрізняється від розрахованого прохідного балу на основі офіційних рейтингових списків, які були оприлюднені пізніше і викладені на «ІСКонкурс». На осі абсцис – допустима похибка розрахунку прохідного балу – від +/- 0 балів (100% співпадання) до +/- 5 балів. На осі ординат – відсоток правильно розрахованих рейтингових списків у межах допустимої похибки.

На рис. 2 колонки справа (чорного кольору) – відповідність розрахованих алгоритмом списків офіційному розподілу, колонки зліва (синього кольору) – відображення точності розрахунку прохідного балу після закінчення терміну зарахування вступників за кошти держави.

Важливі дати, зображені на рисунку:

Для демонстрації роботи алгоритму використовувались рейтингові списки «ІС Конкурс» за 28 липня 2015 року – за 5днів до закінчення прийому заяв від вступників.

6 серпня 2015 року – дата, коли «ІС Конкурс» оприлюднила офіційно сформовані рейтингові списки. Для демонстрації точності алгоритму, який розглядається в даній статті було збережено списки vstup.info за 6 серпня – для подальшого розрахунку прохідного балу на бюджет тайого порівняння з даними алгоритму.

12 серпня 2015 року – оприлюднення системою «ІС Конкурс» сформованих списків із зарахуванням абітурієнтів за кошти держави, які були рекомендовані в першу хвилю та виконали відповідні правила прийому до вищих навчальних закладів – віднесли оригінали документів у відповідні терміни. Також в ці списки входять абітурієнти, які були зараховані на вакантні бюджетні місця та виконали відповідні правила вступу.

Головний недолік алгоритму – недостатня кількість відкритої інформації, потрібної для більш точного розрахунку списків. Для покращення результату роботи програми необхідні дані про квоти пільгових категорій вступників.

Переваги алгоритму:

- простота реалізації

- всі необхідні дані для роботи алгоритму можна самостійно отримати із відкритих джерел

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

Висновки

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

Перелік посилань

  1. Про затвердження Умов прийому на навчання до вищих навчальних закладів України в 2015 році [Електронний ресурс] – Режим доступу: http://zakon4.rada.gov.ua/laws/show/z1390\-14
  2. Інформаційна Система «Конкурс» [Електронний ресурс] – Режим доступу: http://vstup.info

  3. Перевірка сертифікатів зовнішнього незалежного оцінювання 2015 року [Електронний ресурс] – Режим доступу: http://certs.testportal.com.ua

  4. Система пошуку абітурієнтів «Абіт Пошук» [Електронний ресурс] – Режим доступу: http://abit\-poisk.org.ua
May 27, 2016