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

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

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

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

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

1) знаят:

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

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

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

2) могат:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Детерминирани крайни автомати.

2. Недетерминирани крайни автомати.

3. Еквивалентност между детерминираните и недетерминираните крайни автомати.

4. Минимизация на детерминираните крайни автомати.

5. Регулярни операции - обединение, сечение и допълнение на крайни автомати.

6. Декартово произведение на крайни автомати.

7. Регулярни езици. Регулярни изрази.

Контролна работа No 1

8. Нерегулярни езици. uvw - теорема.

9. Формални граматики. Йерархия на Чомски.

10. Контекстно свободни езици. Стекови автомати.

11. Рекурсивно изчислими езици. Машини на Тюринг.

12. Разрешимост. Стоп-проблем за машина на Тюринг.

Контролна работа No 2

Самостоятелна работа

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

• Лекции в 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)

или

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