..:: Martin Kot ::..
Introduction to theoretical computer science
General Actual Download Projects
 
General facts
Guarantee:  Ing. Zdeněk Sawa, Ph.D.
Number of credits:  6
Hours:  2/2/0/2
Completition:  Exam
Lecturers:  ,
Exercisers:  , , ,
, ,
 
Division of points
Accreditation: 
  • 20pts - term written exam
  • 10pts - written essay describing solution of some exercise(s) from a list given during the course
  • 5pts - performance of solution at exercises
  • Bonus 15pts - written essay describing solution of one of given more difficult examples. For each assignemnt only one student can get points.
  • Conditions for accreditation are only submission and presentation of solution of given exercise(s) (accepted by teacher) and taken written term exam (without minimal limit on obtained points)
Exam: 
  • 65pts - written exam
  • 0pts - optional oral exam - consultation of written exam
 
Annotation
The students obtain some basic knowledge of theoretical CS. The following introductory topics are taught in the subject: theory of automata, formal languages, algorithmic complexity (P and NPc problems), including their practical applications.
 
Time table
7:15
8:00
8:00
8:45
9:00
9:45
9:45
10:30
10:45
11:30
11:30
12:15
12:30
13:15
13:15
14:00
14:15
15:00
15:00
15:45
16:00
16:45
16:45
17:30
17:45
18:30
18:30
19:15
pondělímonday              
D210
LB285
Raška Š.
D210
LB281
Raška Š.
 
D210
LB289
Polikarpov B.
úterýtuesday    
D209
LB278
Delong P.
D209
LB279
Delong P.
               
   
D210
LB275
Moravec P.
D210
LB270
Moravec P.
       
D210
LB287
Polikarpov B.
   
středawednesday
D210
LB288
Moravec P.
D210
LB283
Moravec P.
D210
LB280
Raška Š.
               
čtvrtekthursday  
B5
LB276-81
Kot M.
C3
LB270, LB275, LB282-9
Sawa Z.
                 
 
D210
LB284
Bača R.
D210
LB276
Bača R.
   
D210
LB277
Bača R.
D210
LB282
Kohut O.
D210
LB286
Kohut O.
 
pátekfriday                            
 
Lectures
Languages and automata
  • Elementary terms of the set theory. Formal languages.
  • Finite automata and regular languages. Nondeterministic automata.
  • Finding in text, regular expressions.
  • Automata minimization, the pumping lemma.
  • Contex-free languages.
  • Push-down automata.
Algorithmic complexity
  • Computational models, Turing machines, computers, equivalence of models
  • Computational complexity, assymptotic notation.
  • Mathematical foundations: Recurrent equations, assymptotic notation, coding. Polynomial reductions.
  • The P and NP problems, NP-completeness.
  • Some NP-complete problems: SAT, coloring, independence, cover.
 
Study literature
Basic
Other
  • M. Chytil: Automaty a gramatiky, SNTL Praha, 1984.
  • John E. Hopcroft a Jeffrey D. Ullman: Formálne jazyky a automaty. Alfa Bratislava 1978.
  • J. Gruska: Foundation of Computing, International Thomson Computer Press 1997.
  • D. Kozen: Automata and Computability, Undergraduate Text in Computer Science, Springer Verlag 1997.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company 1997.
Literatura není povinná, pouze doporučená, na přednáškách a cvičeních se dozvíte vše potřebné. (Toto není recitační kroužek, takže se nemusíte učit nazpaměť pasáže z knih. Lépe řečeno, nazpaměť se ani učit nesmíte, látce je třeba porozumět.)
Pokud máte k dispozici jiné úvodní knihy či skripta pro daný předmět, klidně je můžete používat. Jedna věc však platí pro všechny -- některé věci na přednášce se mohou líšit od literatury (například odchylky v definicích pojmů, které nejsou jednoznačně ustálené) a u zkoušky pak platí to, co bylo na přednášce.