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

проф. Красимир Манев  д-р
гл. ас. Стоян Боев  д-р

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

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

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

1) знаят:

- възможностите и ограниченията на съвременния компютър;

- основни понятия от теорията на изчислимостта – азбука, дума, език;

- основни изчислителни модели (крайни автомати, стекови автомати, машина на Тюринг) и формални граматики, пораждащи съответните класове от езици.

2) могат:

- да построяват НДКА по зададен регулярен език;

- да построяват ДКА по зададен НДКА;

- да построяват регулярен израз по зададен ДКА и обратно;

- да доказват нерегулярност на даден език;

- да построяват НДСА по зададен контекстно-свободен език;

- да построяват дърво на извод по зададена контекстно-свободна граматика;

- да проследяват работата на зададена машина на Тюринг.

Предварителни изисквания:
Студентите да имат знания и/или умения:

- познаване на сновни понятия и закони от теорията на множествата;

- познаване на основни видове релации и функции;

- умения да извършват операции с множества и функции.

(Горните изисквания се покриват в пълна степен от курсовете GENB005 Основи на информатиката и CSCB021 Дискретна математика)

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

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

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

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

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

• Лекции в Moodle, гл. ас. д-р Стоян Боев

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

• M.Sipser, Introduction to the theory of computation, Thomson Course Technology, 2006

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

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

Две контролни работи през семестъра (минимална средна оценка - Добър 4)

или

Самостоятелна работа + Финален изпит