CITB106 Лабораторни упражнения по програмиране и дискретна математика

Анотация:

Основна цел на курса е да се интегрират и разширят знанията от заложените в програмата задължителни курсове по Програмиране и Дискретна математика. В първата си част той покрива основни знания по Теория на числата и практическите и приложения в кодирането на информация. Във втората си част курсът е насочен към комбинаторни алгоритми за преброяване, генериране и кодиране на основни комбинаторни конфигурации.

прочети още
Информационни технологии

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

гл. ас. Стоян Боев  д-р
гл. ас. Валентина Иванова  д-р

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

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

Успешно завършилите курса студенти:

1) знаят:

• Основите на програмирането с езика С/C++: стандартни типове данни, структури за управление, функции, масиви и структури;

• Основни похвати в процедурното програмиране: итерация, рекурсия и работа с динамична памет;

• Основни приложения на модулната аритметика в компютърната наука и кодирането на информация;

• Основни комбинаторни конфигурации и реализацията им на езика C;

2) могат:

• Да намират ефективно НОД и НОК на две цели числа;

• Да определят ефективно дали дадено число е просто или не и да генерират прости числа;

• Да преобразуват ефективно числата от една бройна система в друга;

• Да намират ефективно член на дадена рекурентна редица;

• Да генерират и кодират дадена комбинаторна конфигурация.


Предварителни изисквания:
Паралелно посещаване на основните курсове по Програмиране и Дискретна математика.

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

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

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

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

1 Делимост - теорема за деление с частно и остатък; Прости числа. Основна теорема на аритметиката.

2 Най-голям общ делител (НОД) и най-малко общо кратно (НОК). Тъждество на Безу.

3 Модулна аритметика - основни свойства на сравненията; операции в остатъчното поле.

4 Приложение на делимостта при преобразуване от една бройна система в друга.

5 Генериране на прости числа и разлагане на прости множители

6 Обобщен алгоритъм на Евклид

7 Приложения на модулната аритметика при кодиране на информацията.- хеширане, шумозащитно кодиране и криптография.

Контролна работа №1 – онлайн тест

8 Подмножества – преброяване, генериране и кодиране.

9 Пермутации – преброяване, генериране и кодиране.

10 Разбиване на числа и множества – преброяване, генериране и кодиране.

11 Множества – представяне в паметта и реализация на операциите – обединение, сечение, допълнение,

симетрична разлика.

12 Подмножества – представяне в паметта и реализация на комбинаторните алгоритми – преброяване,

генериране и кодиране.

13 Пермутации – представяне в паметта, реализация на операциите композиция и обратна пермутация. Реализация на комбинаторните алгоритми – преброяване, генериране и кодиране.

14 Разбиване на числа и множества – реализация на комбинаторните алгоритми - преброяване,

генериране и кодиране.

15 Контролна работа №2

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

• Лекции в Moodle, проф. Иван Ланджев, гл. ас. д-р Стоян Боев, гл. ас. д-р Марияна Райкова

• К. Манев, Увод в дискретната математика, НБУ, 1996; КЛМН, София, 2003

• Kenneth H. Rosen, Descrete mathematics and its applications, 2007

• C. Stein, R. Drysdale, K. Bogart, Discrete mathematics for Computer Scientists

• T. Feil, J. Kroan, Essential discrete mathematics for computer science

• L. Lovasz, J. Pelikan, K. Vesztergombi, Discrete Mathematics: Elementary and Beyond, Springer, New York, 2003

• E. Reingold, J. Nievergelt, N. Deo, Combinatorial algorithms : theory and practice

• D. Kreher , D. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search

• D. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1

• Шилдт Х., Практически самоучител по С, Софтпрес, 2001

• cplusplus.com - The C++ Resources Network - http://www.cplusplus.com/

• Eckel B., Thinking in C++, 2nd edition, v.1,v2, http://mindview.net/Books/TICPP/ThinkingInCPP2e.html

Средства за оценяване:

Един онлайн тест и един практически изпит. Студентите се освобождават от финален изпит със средно аритметичен резултат от поне Добър /4/.