Dalyko sando kodas

ALTE2114

Dalyko sando pavadinimas

Algoritmų teorija

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

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 48

paskaitų 32

seminarų

pratybų 16

kontrolinių darbų 1

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ė. Pristatomi teiginių skaičiavimai.

Dalyko sando turinys

Turing mašinos. Baigtiniai automatai. Algoritmų sudėtingumas. Primityviai rekursyviosios funkcijos. Bendrosios rekursyviosios funkcijos. Dalinai rekursyviosios funkcijos. Aibių numeracija. Rekursyviai skaičiosios aibės. Neišsprendžiamos problemos. Greitai augančios funkcijos. Universaliosios funkcijos. Lambda skaičiavimas. Hilberto tipo skaičiavimas. Dedukcijos teorema. Gentzeno tipo skaičiavimas. Natūralioji dedukcija. Disjunktų dedukcinė sistema.

Pagrindinės literatūros sąrašas

1.   S.Norgėla, Logika ir dirbtinis intelektas, TEV, 2007.

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

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

Papildomos literatūros sąrašas

Mokymo metodai

Paskaitos, konsultacijos.

Lankomumo reikalavimai

Kad būtų leista laikyti egzaminą būtina per kontrolinį surinkti bent 1 balą (iš 3 galimų) arba lankyti 66 % pratybų.

Atsiskaitymo reikalavimai

Kontrolinis darbas ir egzaminas, atsakymas į klausimus raštu ir (prireikus) patikslinimas žodžiu.

Vertinimo būdas

30 % pažymio sudaro pratybų (kontrolinio) įvertinimas, 70 % - egzamino įvertinimas

Aprobuota katedros

2008 08 29

Patvirtinta Studijų programos komiteto

2008 09 12