Pogojev za vključitev v delo ni.
Teorija izračunljivosti
2022/2023
Program:
Magistrski študijski program 2. stopnje Finančna matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
izbirni
Skupina:
R1
ECTS:
6
Jezik:
slovenski, angleški
Nosilec predmeta:
Izvajalec (kontaktna oseba):
Ure na teden – 1. ali 2. semester:
Predavanja
3
Seminar
0
Vaje
2
Laboratorij
0
Vsebina
Turingovi stroji in izračunljive funkcije. Univerzalni stroj. Neodločljivi problemi in neizračunljive funkcije.
Osnovni izreki in pojmi: Izrek s-m-n, izrek u-t-m, izrek o rekurziji, izračunljive in izračunljivo preštevne množice, njihove lastnosti, neseparabilne množice, Riceov izrek, Rice-Shapirov izrek.
Računanje z oraklji, Turingove redukcije in stopnje.
Dodatna vsebina: izračunljivi funkcionali, zveznost funkcionalov, izrek KLS, izračunljiva realna števila, osnovni rezultati izračunljive realne analize.
Temeljni literatura in viri
J. E. Hopcroft, J. D. Ullman: Uvod v teorijo avtomatov, jezikov in izračunov, FER, Ljubljana, 1990.
P. Odifreddi: Classical Recursion Theory, North-Holland, 1989.
Cilji in kompetence
Znanje osnovnih pojmov in rezultatov v teoriji izračunljivosti.
Predvideni študijski rezultati
Znanje in razumevanje: Razumevanje povezav med računskimi pojmi, kot so Turingovi stroji, in osnovnimi matematičnimi pojmi, kot so množice števil.
Uporaba: Snov predstavlja teoretično matematično podlago za računalništvo v splošnem smislu.
Refleksija:
Vpliv pojma izračunljivosti na osnove matematike.
Prenosljive spretnosti – niso vezane le na en predmet:
Analitično in abstraktno razmišljanje o teoretičnih mejah računalništva.
Metode poučevanja in učenja
predavanja, vaje, domače naloge, konzultacije
Načini ocenjevanja
Izpit iz vaj (2 kolokvija ali pisni izpit)
Ustni izpit
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)
Reference nosilca
Andrej Bauer:
AWODEY, Steve, BAUER, Andrej. Propositions as [Types]. Journal of logic and computation, ISSN 0955-792X, 2004, vol. 14, no. 4, str. 447-471. [COBISS-SI-ID 13374809]
BAUER, Andrej. First steps in synthetic computability theory. V: Proceedings of the 21st Annual Conference on Mathematical Foundations of Programming Semantics (MFPS XXI), (Electronic notes in theoretical computer science, ISSN 1571-0661, Vol. 155). Amsterdam: Elsevier, 2006, str. 5-31. [COBISS-SI-ID 14631001]
BAUER, Andrej. A ralationship between equilogical spaces and Type Two Effectivity. Mathematical logic quarterly, ISSN 0942-5616, 2002, vol. 48, suppl. 1, str. 1-15. [COBISS-SI-ID 12033369]
