Subject

Основи на теоријата на компјутерските науки

Course Title

Основи на теоријата на компјутерските науки
Basics of theory of computing

Code

F23L3S039

Study Programme

Computer Science

Organizer of the study programme (unit, institute, department or division)

Faculty of Computer Science and Engineering

Degree level (first, second, third cycle)

Прв циклус

Academic year / semester

6 / Летен

Number of ECTS credits

Teacher

Марија Михова, Миле Јованов

Prerequisites for enrolling in the course

Дискретна математика или Дискретни структури 2 или Математика 2 или Избрани теми од математика

10.

Objectives of the course programme (competences)

На овој курс ќе стекнете основно разбирање за класичните модели кои се користат во основата на компјутерските науки за анализа на пресметковните процеси, вклучувајќи конечни автомати, граматики и Тјурингови машини. Овие модели може да се користат за да се одговори на прашања како што се кои проблеми може да се решат со компјутер и дали има некои проблеми кои се суштински потешки за решавање од другите.

11.

Course content

1. Основни концепти за јазици, граматики и автомати
2. Регуларни изрази и регуларни јазици
3. Детерминистички конечни автомат
4. Недетерминистички конечни автомати, Еквиваленција меѓу детерминистички и недетерминистички конечни автомати и редукција на број на состојби.
5. Својства на регуларните јазиции лема за пумпање кај регуларни јазици.
6. Контекстно слободни јазици
7. Push-down автомати
8. Врска меѓу контекстно слободни јазици и Push-down автомати
9. Лема за пумпање кај конекстно слободни јазици и затварач.
10. Тјурингови машини.
11. Хиерархија кај јазици (рекурзивнијазици, контекстно сензитивни...)
12. Вовед во компјутерска комплексност (П, НП)
13. Пресметливост.

12.

Learning methods

Предавања со користење на презентации, интерактивни предавања, вежби (користење на опрема и софтверски пакети), тимска работа, пример случаи, поканети гости предавачи, самостојна изработка и одбрана на проектна задача и семинарска работа.

13.

Total available time

6 ECTS x 30 hours = 180 hours

14.

Distribution of available time

30 + 45 + 15 + 15 + 75 = 180 часа

15.

Forms of teaching activities

15.1.	Lectures - theoretical instruction	30 hours
15.2.	Exercises (laboratory, auditory), seminars, teamwork	45 hours

16.

Other forms of activities

16.1.	Project assignments	15 часови
16.2.	Independent assignments	15 часови
16.3.	Home study	75 часови

17.

Assessment method

17.1.	Tests	0 points
17.2.	Seminar paper / project (presentation: written and oral)	15 бодови
17.3.	Activities and learning	0 points
17.4.	Final exam	90 бодови

18.

Grading criteria (points / grade)

up to 50 points	5 (five) (F)
from 51 to 60 points	6 (six) (E)
from 61 to 70 points	7 (seven) (D)
from 71 to 80 points	8 (eight) (C)
from 81 to 90 points	9 (nine) (B)
from 91 to 100 points	10 (ten) (A)

19.

Requirement for obtaining a signature and taking the final exam

Реализирани активности 15.2 и 16.1

20.

Language of instruction

Macedonian and English

21.

Method for monitoring the quality of teaching

internal evaluation and survey mechanism

22.

Literature

22.1.

Required literature

22.2.

Additional literature

No. Author Title Publisher Year