Subject 'Logic and Algorithms Theory /Discrete Mathematics'

Name in Estonian: Loogika ja algoritmiteooria

Year:   2007/2008    2008/2009    2009/2010    2010/2011    2011/2012    

State codeI112
Study languageEstonian
Credit points 2.5 CP; 4 ECTS
Grading method Exam

General description

The first part of the course is devoted to basic steps of construction defined on abstract structures and more complicated structures in the framework of which it is possible to deal with the formulating of terms, formulas, deductions etc used in algorithms theory and logic. The second part of the course proceeds from the different foundations of determination of algorithmic computing, which support such formalisms as the machines with unlimited number of registers, Turing machines and operator terms. Further treatment is primarily based on the concept of operator terms and Church-Turing thesis. Problems associated with the presentation and enumeration of recursive functions (Kleene's normal form) are studied in more detail. The treatment of the complexity of algorithmic computing proceeds from Blum's axiomatics, compatible with time- and space-complexity concepts and NP-complete problems. The third part of the course is related to logical structures (terms, formulas, deduction steps, derivatives, interpretations). The basis for the determination of the above-mentioned structures is the procedure for the transforming of texts.

Is taught in following curricula

2010: ISa  ISa-k  ISd  TS*  
2009: IA  ISa  ISa-k  ISd  ISd-k  TS*  
2008: IA  ISa  ISa-k  ISd  ISd-k  TS*  
2007: ISa-k  
* Optional subject

Related subjects

Replacement Subjects
I103 Logic and Algorithms Theory /Discrete Mathematics