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 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ė. 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

Atsiskaitymo reikalavimai

Kontrolinis darbas (uždavinių sprendimas raštu) ir egzaminas (atsakymas į teorinius klausimus ir uždavinių sprendimas raštu, bei, prireikus, patikslinimas žodžiu)

Vertinimo būdas

30 % pažymio sudaro kontrolinio įvertinimas, 70 % - egzamino įvertinimas

Aprobuota katedros

2006 12 22

Patvirtinta Studijų programos komiteto

2007 04 23