Теорія алгоритмів - Робоча програма навчальної дисципліни (Силабус)

Реквізити навчальної дисципліни

Програма навчальної дисципліни

1. Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання

Силабус освітнього компонента «Теорія алгоритмів» складено відповідно до освітньої програми підготовки бакалаврів «Інформаційні управляючі системи та технології» спеціальності 126 – Інформаційно управляючі системи та технології.

Мета курсу є формування та закріплення у студентів наступних компетентностей: ЗК 1 Здатність до абстрактного мислення, аналізу та синтезу ЗК 2 Здатність застосовувати знання у практичних ситуаціях ЗК 3 Здатність до розуміння предметної області та професійної діяльності. ЗК 5 Здатність вчитися і оволодівати сучасними знаннями ЗК 6 Здатність до пошуку, оброблення та узагальнення інформації з різних джерел. ФК 3 Здатність до проєктування, розробки, налагодження та вдосконалення системного, комунікаційного та програмно-апаратного забезпечення інформаційних систем та технологій, Інтернету речей (ІоТ), комп’ютерноінтегрованих систем та системної мережної структури, управління ними. ФК 4 Здатність проєктувати, розробляти та використовувати засоби реалізації інформаційних систем, технологій та інфокомунікацій (методичні, інформаційні, алгоритмічні, технічні, програмні та інші) ФК 11 Здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних та імітаційних моделей і методів. ФК 13 Здатність проводити обчислювальні експерименти, порівнювати результати експериментальних даних і отриманих рішень. ФК 15 Здатність до алгоритмічного мислення при розробці програмного забезпечення інформаційно-управляючих систем. І таким чином, сприяти більш глибшому розумінню студентом прикладних задач; сформувати математичний фундамент інженера комп'ютерних систем, здатного використовувати сучасний математичний апарат для дослідження, опису, аналізу, проектування алгоритмів для розв'язку задач.

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

Програмні результати навчання, на формування та покращення яких спрямована дисципліна: ПРН 2 Застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проєктування і використання інформаційних систем та технологій. ПРН 4 Проводити системний аналіз об’єктів проєктування та обґрунтовувати вибір структури, алгоритмів та способів передачі інформації в інформаційних системах та технологіях; оволодіння основними поняттями теорії алгоритмів; ПРН 12 Знати та володіти навичками та уміннями мовної діяльності, вміння спілкуватися в діалоговому режимі в галузі професійної діяльності з колегами та експертами предметних областей. ПРН 22 Використовувати методи математичного та імітаційного моделювання при розробці та проєктуванні інформаційних управляючих систем та технологій підтримки прийняття управлінських рішень. Тобто ознайомлення з технологіями дослідження, аналізу розробки та застосування алгоритмів; набуття практичних навичок використання методів і засобів проектування та дослідження алгоритмів.

2. Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)

МІСЦЕ ДИСЦИПЛІНИ В НАВЧАЛЬНІЙ ПРОГРАМІ

пререквізити Для успішного засвоєння дисципліни студент повинен володіти освітніми компонентами «Вища математика», «Спеціальні розділи математики» та «Програмування». постреквізити Компетенції, знання та уміння, одержані в процесі вивчення освітнього компонента є необхідними для подальшого вивчення освітніх компонентів «Проектування інформаційних систем», «Проєктування інформаційних систем», «Програмування-2» та «Аналіз даних в інформаційно-управляючих системах».

3. Зміст навчальної дисципліни

4. Навчальні матеріали та ресурси

Базова

1. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы / М.: Вильямс, 2000 – 384с.
2. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов/М.: Мир, 1981 – 368 с.
3. Седжвик Р. Фундаментальные алгоритмы на С++ / К.: ДиаСофт, 2001 – 688с.
4. Ковалюк Т.В. Основи програмування / К.: BHV, 2005 – 384 с.
5. Ананій В. Левітін Алгоритми: введення в розробку й аналіз Introduction to The Design and Analysis of Aigorithms. / М .: "Вильямс", 2006. - С. 275-284. - ISBN 5-8459-0987-2
6. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пірамідальна сортування / / Алгоритми: побудова й аналіз Introduction to Algorithms / Под ред. І. В. Красикова. - 2-ге вид. / М .: Вільямс, 2005. - С. 182-188. - ISBN 5-8459-0857-4
7. https://www.toptal.com/developers/sorting-algorithms/

Інформаційні ресурси

1. https://classroom.google.com/c/NTkxMzQ0NTgyOTkx?cjc=nzwe6ka ІС-x1,
2. https://classroom.google.com/c/NTkxMzQ0OTMwOTI0?cjc=55bvryy ІС-x3,
3. https://classroom.google.com/c/NTkxMzI2NzY4OTkx?cjc=nvjk27k ІС-x2 Запис лекцій минулих років: https://www.youtube.com/@Doroshenko_Kateryna_S/featured Канал "Теорія алгоритмів"

Навчальний контент

5. Методика опанування навчальної дисципліни (освітнього компонента)

Лекційні заняття

Лабораторні заняття (комп'ютерні практикуми)

Всього на лабораторні заняття виділено 36 годин.

Контрольна робота №1/2

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

Модульна контрольна робота (МКР)

МКР виконується після вивчення Розділів 1-3 та виконання практичних занять 1-5. Контрольна робота проводяться у середовищі Moodle. Кожен студент отримує індивідуальне завдання, відповідно до якого необхідно описати вибрану математичну модель, обгрунтувати обрану структуру даних, описати базовий алгоритм та провести його оцінку складності, реалізувати алгоритм в обраній мові програмування, провести базові тести, виконати оцінку якості коду за результатами яких побувати часові діаграми.

Самостійна робота студента

Самостійна робота студентів складається з:

1. Підготовки до аудиторних занять https://classroom.google.com/c/NTkxMzQ0NTgyOTkx?cjc=nzwe6ka ІС-x1, https://classroom.google.com/c/NTkxMzQ0OTMwOTI0?cjc=55bvryy ІС-x3, https://classroom.google.com/c/NTkxMzI2NzY4OTkx?cjc=nvjk27k ІС-x2. https://www.youtube.com/channel/UCf9xOF5-J_HBrtx0R39_k7g відеолекції

2. Виконання лабораторних робіт https://classroom.google.com/c/NTkxMzQ0NTgyOTkx?cjc=nzwe6ka ІС-x1, https://classroom.google.com/c/NTkxMzQ0OTMwOTI0?cjc=55bvryy ІС-x3, https://classroom.google.com/c/NTkxMzI2NzY4OTkx?cjc=nvjk27k ІС-x2.

3. Виконання МКР (модульної контрольної роботи).

Самостійна робота

6. Політика навчальної дисципліни (освітнього компонента)

Система вимог, які викладач ставить перед студентом:

1. Форми організації освітнього процесу, види навчальних занять і оцінювання результатів навчання регламентуються: "Положенням про організацію освітнього процесу в Національному технічному університеті України Київському політехнічному інституті імені Ігоря Сікорського";
2. правила відвідування занять: заборонено оцінювати присутність або відсутність здобувача на аудиторному занятті, в тому числі нараховувати заохочувальні або штрафні бали. Відповідно до РСО даної дисципліни бали нараховують за відповідні види навчальної активності на лекційних та практичних заняттях.
3. правила поведінки на заняттях: студент має можливість отримувати бали за відповідні види навчальної активності на лекційних та практичних заняттях, передбачені РСО дисципліни. Використання засобів зв’язку для пошуку інформації на гугл-диску викладача, в інтернеті, в дистанційному курсі на платформі Сікорський здійснюється за умови вказівки викладача;
4. політика дедлайнів та перескладань: якщо студент не проходив або не з’явився на МКР (без поважної причини), його результат оцінюється у 0 балів. Перескладання результатів МКР не передбачено;
5. політика щодо академічної доброчесності: Кодекс честі Національного технічного університету України «Київський політехнічний інститут» https://kpi.ua/files/honorcode.pdf встановлює загальні моральні принципи, правила етичної поведінки осіб та передбачає політику академічної доброчесності для осіб, що працюють і навчаються в університеті, якими вони мають керуватись у своїй діяльності, в тому числі при вивченні та складанні контрольних заходів з дисципліни «Системи автоматизації»;
6. при використанні цифрових засобів зв’язку з викладачем (мобільний зв’язок, електронна пошта, спілкування на форумах та у соцмережах тощо) необхідно дотримуватись загальноприйнятих етичних норм, зокрема бути ввічливим та обмежувати спілкування робочим часом викладача.

Політика виставлення оцінок:

кожна оцінка виставляється відповідно до розроблених викладачем та заздалегідь оголошених студентам критеріїв, а також мотивується в індивідуальному порядку на вимогу студента; у випадку не виконання студентом усіх передбачених навчальним планом видів занять (лабораторних робіт, МКР) до заліку він не допускається; всі завдання обов'язково мають бути відпрацьовані.

Відвідування є обов'язковим

(за винятком випадків, що вказані та описані наказами по роботі університету під час пандемій, воєнних дій, стихійних лих та інших непереборних обставин. Або коли існує поважна причина із сторони студента, наприклад, хвороба чи дозвіл працівників деканату). Якщо студент не може бути присутніми на заняттях, він все одно несете відповідальність за виконання завдань, що проводились в комп'ютерному класі.

Порядок зарахування пропущених занять.

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

Реферати також можуть підготувати студенти, у яких недостатньо рейтингових балів.

Політика академічної поведінки та доброчесності:

конфліктні ситуації мають відкрито обговорюватись в академічних групах з викладачем, необхідно бути взаємно толерантним, поважати думку іншого. Плагіат та інші форми нечесної роботи неприпустимі. Всі індивідуальні завдання та курсову роботу студент має виконати самостійно із використанням рекомендованої літератури й отриманих знань та навичок. Цитування в письмових роботах допускається тільки із відповідним посиланням на авторський текст. Недопустимі підказки і списування у ході захисту лабораторних робіт, на контрольних роботах, на іспиті. https://kpi.ua/files/honorcode.pdf

Норми академічної етики:

дисциплінованість; дотримання субординації; чесність; відповідальність; робота в аудиторії з відключеними мобільними телефонами. Повага один до одного дає можливість ефективніше досягати поставлених командних результатів. При виконанні лабораторних робіт студент може користуватися ноутбуками. Проте під час лекційних занять та обговорення завдань лабораторних робіт не слід використовувати ноутбуки, смартфони, планшети чи комп'ютери. Це відволікає викладача і студентів групи та перешкоджає навчальному процесу. Якщо ви використовуєте свій ноутбук чи телефон для аудіо- чи відеозапису, необхідно заздалегідь отримати дозвіл викладача. https://kpi.ua/files/honorcode.pdf

Дотримання академічної доброчесності студентів й викладачів

Pегламентується: – Кодекс честі Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікоського» (https://kpi.ua/code); – Статут КПі ім. Ігоря Сікорського (https://kpi.ua/statute);

7. Види контролю та рейтингова система оцінювання результатів навчання (РСО)

Розподіл балів по дисципліні

R=(241+124+2*5+18)*0,6+40=100

7.1 Поточний контроль:

вправи на лекційних заняттях, тестування, МКР, виконання та захист лабораторних робіт.

Тестування по матеріалам лекційних занять

Ваговий бал 1. Максимальна кількість балів за тестування – 1 бал * 24 лекції що оцінюються = 24 балів. Тестування проводиться у системі дистанційного навчання GoogleClass та доступне протягом 5 робочих днів після завершення поточної лекції. У деяких випадках термін проходження тестування може бути продовжений лектором. Тривалість проходження одного тестування – 10 хвилин. Кількість спроб – одна. У деяких випадках, що пов’язані з технічними проблемами студентів, може надатися повторна спроба на окремі тестування. Кожне тестування містить 5 запитань різного формату (вибір правильного варіанту з переліку; вірно/невірно; визначити відповідність; чисельна відповідь; вибір пропущених слів; перетаскування на зображення тощо). Критерії оцінювання:

• запитання типу «вибір правильного варіанту з переліку», «вірно/невірно», «чисельна відповідь» оцінюються однозначно: вірна відповідь – 0,2 бал, невірна відповідь – 0 балів;
• запитання, на які немає однієї конкретної відповіді, типу «визначити відповідність», «вибір пропущених слів», «перетаскування на зображення» оцінюються у відповідності до кількості елементів у тесті (наприклад, якщо треба вставити 4 слова у текст, то студент отримає по 0,025 балів за одне правильне вставлене слово, а за всі 4 правильно вставлені слова отримає відповідно 0,1 балів) – невірна відповідь – 0 балів, частково вірна відповідь – 0,01-0,09 балів, вірна відповідь 0,1 бал.

Лабораторні роботи

Ваговий бал. Лабораторні роботи - ваговий бал 4. Максимальна кількість балів за всі лабораторні роботи складає 4 бали * 12 роботи = 24 бали. На лабораторних роботах студенти перевіряють працездатність написаних програм за попередньо вирішеними вдома задачами. Для допуску до поточної лабораторної роботи необхідно мати Протокол, оформлений відповідно до норм оформлення технічної документації, який має містити всі необхідні пункти, відповідно до Методичних вказівок. Також для допуску до лабораторної роботи (окрім 1-ї) необхідно захистити попередню. Студенти, що не захистили попередню лабораторну роботу можуть бути не допущені до виконання наступної. Лабораторні роботи виконуються бригадою. Критерії оцінювання лабораторної роботи з ваговим балом 4:

• вірно вирішено всі задачі, продемонстрована працездатність всіх програм (схем), вірні відповіді на запитання до захисту – 4 бали;
• вірно вирішено всі задачі,, продемонстрована працездатність всіх програм (схем), відповіді на питання до захисту мають неточності – 2-3,9 бали;
• вірно вирішено всі задачі,, але деякі з них містять помилки або неточності, продемонстрована працездатність не всіх програм (схем), відповіді на питання до захисту мають неточності – 1-1,9 бали;
• вірно вирішено всі задачі, продемонстрована працездатність не всіх програм (схем), відповіді на питання до захисту мають неточності – 0-0,9 балів;
• лабораторна робота не виконана або протокол не представлений – повертається на відпрацювання або доопрацювання. УВАГА! Захист всіх лабораторних робіт є умовою допуску до складання заліку. Студенти, що на момент консультації перед екзаменом не захистили лабораторні роботи, не допускаються до основної здачі та готуються до перескладання. УВАГА! Для допуску до перескладання заліку треба у визначений викладачем термін здати всі заборгованості по лабораторним роботам.

Модульна контрольна робота

Ваговий бал – 18. Модульна контрольна робота (МКР) виконується протягом семестру та захищається на останньому з лабораторних занять, але обовязково після вивчення Розділу 1 та виконання лаб. занять 1-5. Критерії оцінювання модульної контрольної роботи: На модульній контрольній роботі студент виконує 2 завдання. Кожне завдання оцінюється від 0 до 9 балів:

• вірно виконаний завдання, сформована мат модель, обгрунтовано структуру даних, зображено алгоритм та оцінено його складність, складена програма, виконана тестова симуляція методом часових діаграм відповідає умові – 9 балів;
• вірно виконаний завдання, сформована мат модель, обгрунтовано структуру даних, зображено алгоритм та оцінено його складність, складена програма, виконана тестова симуляція методом часових діаграм частково відповідає умові – 6-8,9 балів;
• • вірно виконаний завдання, сформована мат модель, обгрунтовано структуру даних, зображено алгоритм та оцінено його складність, складена програма, виконана тестова симуляція методом часових діаграм не відповідає умові – 3-5,9 балів;
• задачу виконано з помилками, програма складена не вірно або виконаний вірно тільки алгоритм – 2-3,9 балів;
• алгоритм та розрахунки виконано з помилками, програма не компілюється – 0-1,9 балів.

7.2 Календарний контроль:

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

1. За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 16 балів. На першій атестації (8-й та 9-й тиждень)студент отримує "зараховано", якщо його поточний рейтинг не менше 10 балів.
2. За результатами 13 тижнів навчання максимально можлива кількість балів – 55 балів. На другій атестації (14-й тиждень) студент отримує "зараховано", якщо його поточний рейтинг не менше 30 балів.

7.3 Семестровий контроль: залік

Умови допуску до семестрового контролю:

1. 24 бали мінімально позитивна оцінка за лабораторні роботи
2. 6 балів мінімально за дві контрольні
3. 10 мінімум балів за МКР
4. 24 тестування по лекції

тобто, - зарахування усіх лабораторних робіт та МКР.

Форма семестрового контролю – залік Максимальна сума балів за роботу у семестрі складає 60. Необхідною умовою допуску до заліку - виконані та захищені лабораторні роботи, МКР, семестровий рейтинг не менше 30 балів.

Залік містить дві складові: теоретичну та практичну. Теоретична складова направлена на перевірку набутих в результаті вивчення освітнього компонента знань студентів у вигляді тестування за лекційним матеріалом семестру. Кожне тестування містить 20 запитань різного формату (вибір правильного варіанту з переліку; вірно/невірно; визначити відповідність; чисельна відповідь; вибір пропущених слів; перетаскування на зображення тощо). Максимальна кількість балів за тестування складає 20 питань * 1 бал = 20 балів. Практична складова передбачає перевірку набутими студентами умінь синтезувати алгоритми, проєктувати та перевіряти відповідно до умов завдання з розробки інформаційних систем. Кожному студенту надається окрема задача, відповідно до умов якої необхідно виконати моделювання, скласти алгоритм та програму у вибраному студентом середовищі програмування та виконати симуляцію методом часових діаграм. Максимальна кількість балів за задачу складає 20 балів.

Критерії оцінювання теоретичної складової

• запитання типу «вибір правильного варіанту з переліку», «вірно/невірно», «чисельна відповідь» оцінюються однозначно: вірна відповідь – 1 бал, невірна відповідь – 0 балів;
• запитання, на які немає однієї конкретної відповіді, типу «визначити відповідність», «вибір пропущених слів», «перетаскування на зображення» оцінюються у відповідності до кількості елементів у тесті (наприклад, якщо треба вставити 4 слова у текст, то студент отримає по 0,25 балів за одне правильне вставлене слово, а за всі 4 правильно вставлені слова отримає відповідно 1 бал) – невірна відповідь – 0 балів, частково вірна відповідь – 0,1-0,9 балів, вірна відповідь 1 бал. Критерії оцінювання практичної складової
• вірно виконаний синтез алгоритму, складена програма, виконана симуляція роботи розробленого програмного засобу методом часових діаграм відповідає умові – 20 балів;
• вірно виконаний синтез алгоритму, складена програма, виконана роботи розробленого програмного засобу симуляція методом часових діаграм частково відповідає умові – 15-19 балів;
• синтез виконано з помилками, складена програма, виконана симуляція роботи розробленого програмного засобуметодом часових діаграм не відповідає умові – 10-14 балів;
• синтез виконано з помилками, програма складена не вірно але компілюється – 5-9 балів;
• синтез виконано з помилками, програма не складена або не компілюється – 0-4 бали.

7.4 Таблиця відповідності рейтингових балів оцінкам за університетською шкалою:

7.5 Додаткові (бонусні) бали

Рейтинговою системою оцінювання передбачені додаткові бали за виконання додаткових завдань. Один студент не може отримати більше ніж 10 бонусних балів у семестрі. Бонусні бали можуть бути отримані за такі види робіт: «Івенти», «Вправи на лекційних заняттях», «Додаткові лекції».

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

Вправи на лекційних заняттях Ваговий бал 0,25. Максимальна кількість балів за всі виконані вправи – 0,25 балів * 24 лекцій = 6 балів (на лекціях де заплановано КР1 та КР2, по 10 хв кожна, не проводиться додаткове опитування) Вправи проводяться тільки на лекційних заняттях і доступні тільки у спеціально виділений викладачем час. В інший час незалежно від обставин вправи недоступні. Вправи виконуються студентами у системі дистанційного навчання. Тривалість проходження однієї вправи від 2 до 5 хвилин, в залежності від її складності. Тривалість вправи попередньо озвучується викладачем. Кількість спроб – одна. Після кожної вправи проводиться коротке обговорення її результатів. Кожна вправа – це тестування, яке містить 1 завдання різного формату (вибір правильного варіанту з переліку; вірно/невірно; визначити відповідність; чисельна відповідь; вибір пропущених слів; перетаскування на зображення тощо).

Критерії оцінювання

• запитання типу «вибір правильного варіанту з переліку», «вірно/невірно», «чисельна відповідь» оцінюються однозначно: вірна відповідь – 0,05 бал, невірна відповідь – 0 балів;
• запитання, на які немає однієї конкретної відповіді, типу «визначити відповідність», «вибір пропущених слів», «перетаскування на зображення» оцінюються у відповідності до кількості елементів у тесті (наприклад, якщо треба вставити 4 слова у текст, то студент отримає по 0,0125 балів за одне правильне вставлене слово, а за всі 4 правильно вставлені слова отримає відповідно 0,05 балів) – невірна відповідь – 0 балів, частково вірна відповідь – 0,01-0,49 балів, вірна відповідь 0,5 балів.

Додаткові лекції Додаткові лекції – це теми на самостійне опрацювання, які забезпечать здобувачам посилення теоретичних знань з дисципліни. Ваговий бал 0,5. Максимальна кількість балів за опрацювання додаткових лекції – 0,5 балів * 15 лекцій (теми вказано нижче) = 7,5 балів. Бали здобувачі отримують за завантаження у систему GoogleClass конспекту опрацьованої лекції.

8. Додаткова інформація з дисципліни (освітнього компонента)

Рекомендовані теми рефератів.

1. Ієрархія класів складності.
2. Повнота задач NP-класу.
3. Розгляд евристичних алгоритмів.
4. Дослідження застосування АТД в різноманітних алгоритмах.
5. Використання хешування в криптографії.
6. Використання хешування в різних галузях діяльності.
7. Дерева пошуку в теорії ігор.
8. Дерева пошуку в задачах прйняття рішень.
9. Сортування Timsort.
10. Інтроспективне сортування.
11. Блукаюче сортування.
12. Млинцеве сортування.
13. Топологічне сортування.
14. Мережеве сортування.
15. Зовнішнє сортування ( методи не розглянуті в лекці).

Робочу програму навчальної дисципліни (силабус):

Складено Дорошенко Катерина С. ст викладач каф. ІСТ

Ухвалено Засідання кафедри : протокол 21 від 29.06.2023

Погоджено Метод рада факультету: протокол 11 від 29.06.2023