Basics of theory of computing

1.

Subject title

Basics of theory of computing

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

2.

Code

F23L3S039

3.

Study program

Примена на информациски технологии, Софтверско инженерство и информациски системи, Компјутерско инженерство, Интернет, мрежи и безбедност, Информатичка едукација, Software engineering and information systems, Компјутерски науки, Примена на информациски технологии, Софтверско инженерство и информациски системи, Компјутерско инженерство, Интернет, мрежи и безбедност, Software engineering and information systems, Компјутерски науки, Стручни студии за програмирање, Стручни студии за програмирање, Statistics and Data Analytics,

4.

Organizer of the study program (unit, institute, department, division)

Faculty of Information Sciences and Computer Engineering

5.

Study cycle (first, second, third)

Прв циклус

6.

Academic year / semester

3 / Летен

7. Number of ECTS credits

6.0

8.

Instructor

проф. д-р Марија Михова проф. д-р Миле Јованов

9.

Prerequisites for enrollment

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

10.

Subject goals and competencies:

On this course you will gain a basic understanding of the classical mathematical models used to analyze computing processes, including finite automata, grammars, and Turing machines. These mathematical models can be used to answer questions such as what problems can be solved by computer, and whether there some problems that are intrinsically harder to solve than others.

11.

Subject content:

1. Basic concepts of languages, grammars and automata 2. Regular expressions and regular languages 3. Deterministic finite automaton 4. Non-deterministic finite automata, Equivalence between deterministic and non-deterministic finite automata and reduction of number of states. 5. Properties of regular languages and pumping lemma for regular languages. 6. Context-free languages 7. Push-down machines 8. Relationship between context-free languages and Push-down automata 9. Pumping lemma for connected free languages and a closure. 10. Turing machines. 11. Hierarchy in languages (recursive languages, context sensitive...) 12. Introduction to computer complexity (P, NP) 13. Computability.

12.

Learning methods:

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

13.

Total available time fund

6.0 ECTS x 30 hours = 180 hours

14.

Time distribution

30 + 45 + 15 + 15 + 75 = 180 hours

15.

Forms of teaching activities

15.1.

Lectures - theoretical teaching

30 hours

15.2.

Exercises (laboratory, classroom), seminars, team work

45 hours

16.

Other forms of activities

16.1.

Project tasks

15 hours

16.2.

Independent tasks

15 hours

16.3.

Homework

75 hours

17.

Grading method

17.1.

Tests

0 points

17.2.

Seminar work / project (presentation: written and oral)

15 points

17.3.

Activities and learning

0 points

17.4.

Final exam

90 points

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.

Condition for signature and taking final exam

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

20.

Language of instruction

Македонски и англиски

21.

Quality assurance method

механизам на интерна евалуација и анкети

22.

Literature

22.1.

Mandatory literature

22.2.

Additional literature