Теорія обчислень, алгоритми і структури даних
Спеціальність: Комп'ютерні науки (Системи штучного інтелекту)
Код дисципліни: 6.122.13.O.013
Кількість кредитів: 8.00
Кафедра: Системи штучного інтелекту
Лектор: Засоба Є.
Семестр: 2 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування у студентів необхідних компетентностей:
інтегральна компетентність (ІНТ):
здатність використовувати теоретичні та фундаментальні знання, уміння і навички для успішного розв’язування складних спеціалізованих задач та практичних проблем під час професійної діяльності у галузі комп’ютерних наук та інформаційних технологій, комп’ютерної техніки та сучасних технологій проектування та програмування інформаційних систем, володіння навичками роботи з комп'ютером для вирішення задач спеціальності;
загальні компетентності (ЗК):
уміння ідентифікувати, формулювати та розв’язувати задачі;
уміння розробляти та керувати проектами;
уміння працювати самостійно;
навички використання інформаційних та комунікативних технологій;
фахові компетентності (ФК):
здатність застосовувати базові знання з фундаментальних наук: математики, фізики, електроніки для вирішення типових задач спеціальності;
здатність застосовувати знання математичних методів аналізу та синтезу складних об’єктів та систем із застосуванням сучасних методів інформаційних технологій;
здатність застосовувати знання основ охорони праці, виробничої санітарії і пожежної безпеки під час роботи з устаткуванням та обладнанням.
Результати навчання: ПР13. Володіти мовами системного програмування та методами розробки програм, що взаємодіють з компонентами комп’ютерних систем, знати мережні технології, архітектури комп’ютерних мереж, мати практичні навички технології адміністрування комп’ютерних мереж та їх програмного забезпечення
ПР14. Володіти мовами системного програмування та методами розробки програм, що взаємодіють з компонентами комп’ютерних систем, знати мережні технології, архітектури комп’ютерних мереж, мати практичні навички технології адміністрування комп’ютерних мереж та їх програмного забезпечення
ПР16. Розуміти концепцію інформаційної безпеки, принципи безпечного проектування програмного забезпечення, забезпечувати безпеку комп’ютерних мереж в умовах неповноти та невизначеності вихідних даних.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Алгебра і геометрія
Мови та парадигми програмування
Дискретна математика
Короткий зміст навчальної програми: Алгоритми та структури даних є основою, на якій будується будь-яке програмне забезпечення. Їхнє знання, розуміння та вміння застосувати є критично необхідним для розробника програмного забезпечення в будь-якій галузі. Оволодіння даним предметом дасть можливість майбутньому інженеру створювати якісні, швидкі та ефективні програмні рішення в будь-якому напрямку
Опис: Основи амортизаційного аналізу. О-нотації P-NP алгоритми. Перегляд Жадібних алгоритмів. Поняття поліноміальної та експоненційної складності. Еквівалентність алгоритмів НП. Двійковий та трійковий пошук. Монотонна функція як необхідна та достатня умова для двоичного пошуку. Сортування. Опис сортування: бульбашка, підрахунок, швидке злиття. Оцінки складності, обмеження застосування та порівняльний аналіз. Відправлення до іншого N log N сортування (піраміда, дерево)
Динамічне програмування. Загальна ідея ДП. Три необхідних умови для ефективності методу: вирішення проблем для підзадач, перетин підзадань, тривіальні підзадачі. Створення ДП з вершини вниз і знизу вгору. Алгоритми на стрічках. Функція Hash Двійкове дерево. Застосування та оцінка складності середньостатистичної ситуації. Оцінка складності найгіршого випадку. Збалансоване подвійне дерево. Чорні та червоні дерева. Купа. Дерево відрізків. Геометричні алгоритми. Площа багатокутника та об'єм ного багатокутника. Випукла оболонка
Методи та критерії оцінювання: 1. Виконання лабораторних та практичних робіт та їх захист.
2. Написання контрольних робіт.
3. Написання розрахунково-графічної роботи
4. Екзамен.
Критерії оцінювання результатів навчання: Лабораторна робота, Практична робота, Розрахунково-графічна робота - 40 балів
Іспит, Усна компонента - 60 балів
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
2. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, 3rd Edition. ISBN-10: 0201350882
3. Donald Knuth The Art of Computer Programming . — Addison-Wesley Professional, 2015. ISBN 978-0-13-439760-3.
4. kiena, Steven S, Revilla, Miguel A. Programming Challenges: The Programming Contest Training Manual
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).