Dalyko sando kodas

ALTE2114

Dalyko sando pavadinimas

Algoritmų teorija

Dėstytojo (-jų) pedagoginis vardas, mokslo laipsnis, vardas ir pavardė

doc. dr. Stanislovas Leonas Norgėla
a. Adomas Birštunas

Katedra, centras

Informatikos katedra

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

pirmosios pakopos

Semestras

rudens (3) 

ECTS kreditai

3

VU kreditai

2

Auditorinės valandos

viso dalyko 32

paskaitų 32

seminarų

pratybų

laboratorinių darbų

konsultacijų

Reikalavimai

Turi būti išklausytas diskrečiosios matematikos kursas

Dėstomoji kalba

lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

Supažindinimas su skirtingais algoritmo sąvokos formalizavimo metodais. Algoritmiškai apskaičiuojamųjų funkcijų analizė.

Dalyko sando turinys

Daugiajuostės Turing mašinos. Primityviai rekursinės funkcijos. Bendrarekursinės funkcijos. Aibių numeracija. Rekursyviai skaičiosios aibės. Neišsprendžiamos problemos. Universalios funkcijos. Greitai augančios funkcijos. Posto numeracija. Produktyvios ir kreatyvios aibės. Rekursyviai neatskiriamos aibės. Baigtiniai automatai. Tikimybiniai automatai. Lambda skaičiavimo termai. Tipizuotas lambda skaičiavimas. Algoritmų sudėtingumas.

Pagrindinės literatūros sąrašas

1.   R.Lassaigne, M. de Rougemont. Logika ir algoritmų sudėtingumas, Žodynas, Vilnius, 1999.

2.   S.Norgėla, Matematinė logika, TEV, 2004.

Papildomos literatūros sąrašas

Mokymo metodai

Konsultacijos, paskaitos.

Lankomumo reikalavimai

Kad būtų leista laikyti egzaminą būtina lankyti 50 % užsiėmimų

Atsiskaitymo reikalavimai

Įskaita  

Vertinimo būdas

-

Aprobuota katedros

2006-08-31

Patvirtinta Studijų programos komiteto

2006-09-25