NETB291 Състезателно програмиране - II част

Анотация:

Курсът подготовя студентите по Информатика за решаване на задачи, за които се изисква съставяне на по-сложни алгоритми. Изучава се целия път от поставяне на задачата до анализ на решенията - анализ на данните, преглед на съществуващи алгоритми за решаванети й, избиране на подходящ алгоритъм, модифициране на съществуващ или построяване на нов алгоритъм, избор на структури от данни, програмиране, тестване на програмата, анализ на ефективността на алгоритъма и програмата. Всички алгоритми се изучават заедно с най-ефективните им реализации като програми на С и С++.

прочети още
Мрежови технологии (на английски език)

Преподавател(и):

доц. Николай Киров  д-р

Описание на курса:

Компетенции:


Предварителни изисквания:
Студентите трябва да могат да програмират на С и/или С++.

Форми на провеждане:
Редовен

Учебни форми:
Лекция

Език, на който се води курса:
Български

Теми, които се разглеждат в курса:

  1. Технология за състезателно програмиране Стандарти на С и С++, компилатори. Стандартен вход и изход в С и С++. Пренасочване на входа и изхода. Примери за вход и изход за състезателни задачи.
  2. Динамично оптимиране (3 занятия) Класическа задача за раницата. Попълване на таблица. Най-дълга обща подредица. Хедонийски език. Формални системи. Задачи за монети. Домино подредица. Разстояние на Левенщайн.
  3. Алчни алгоритми Задачи за монети. Египетски дроби. Дробна задача за раница. Разходката на коня. Задания и крайни срокове.
  4. Състезание 1 Обсъждане на задачите от състезанието, резултати, тестове, решения на авторите и студентите
  5. Графи (3 занятия) Понятия и дефиниции. Представяния на граф: списък на ребрата, матрица на съседство, списък на наследниците. Обхождане в ширина и обхождане в дълбочина. Компоненти на свързаност. Минимален път. Най-дълъг път в ацикличен граф. Хамилтонов път и цикъл. Ойлеров цикъл. Максимален поток. Минимално покриващо дърво. Транзитивно затваряне и редукция. Топологично сортиране
  6. Състезание 2 Обсъждане на задачите от състезанието, резултати, тестове и решения на авторите и студентите
  7. Геометрични задачи Основни понятия и формули. Изпъкнала обвивка.
  8. Математически задачи Полиноми. Производна и интеграл. Системи уравнения. Комплексни числа.
  9. Компресиране Общи понятия. Кодиране на редици с повтарящи се елементи. Кодиране на Хъфман. Код с разделители.
  10. Състезание 3 Обсъждане на задачите от състезанието, резултати, тестове и решения на авторите и студентите.
  11. Тест

Литература по темите:

Учебници:

Преслав Наков, Панайот Добриков, Програмиране = ++Алгоритми; TopTeam Co., 2003, 696 страници

Antti Laaksonen, Competitive Programmer's Handbook, 2017, https://cses.fi/book.html

Допълнителна литература

[1] Лендерт Амерал, Алгоритми и структури от данни в С++, ИК "Софтех", София, 2001

[2] Робърт Седжуик, Алгоритми на С. Том 1 и 2, ИК "Софтех", София, 2002 (Ч 681.3 / С 307)

[3] Саймън Харис, Джeймс Рoс, Оснoви нa aлгoритмитe, Алекс Софт, 2006 (681.325.3 / Х 277)

[4] Красимир Манев, Алгоритми в графи. Основни алгоритми, КЛМН, 2013.

[5] MIT 6.006 Introduction to Algorithms, Fall 2011

[6] Data Structure Visualizations