UL/FRI/MAG-RI/1/IRZ/Izpiti/FAQ

Glej tudi vprašanja starega predmeta TOR2.

Katere vrste aksiomatik poznamo?

poznamo naslednje vrste aksiomatik:

nazorna aksiomatika | izhaja iz dejanskih izkušenj
hipotetična aksiomatika | postavi aksiome in raziskuje

Naštej nekaj primerov hipotetičnih aksiomatik.

primeri hipotetičnih aksiomatik so:

Cantorjeva teorija množic,
Peanova naravna števila,
neevklidske geometrije

Katere aksiome ima Cantorjeva teorija množic?

Cantorjeva teorija množic ima aksiom:

ekstenzionalnosti | množica je določena s svojimi elementi

abstrakcije | vsaka lastnost določa neko množico

izbire | obstaja funkcija, ki izbere en element v
| poljubni množici v neki družini množic

Kako definiramo dobro urejenost?

dobro urejenost določa relacija
"pred", za katero veljajo lastnosti:

minimalni element | je "pred" ostalimi

irefleksivnost | element ni "pred" sabo

sovisnost | za različna elementa
| je en "pred" drugim

Kaj je kardinalno število?

kardinalno število je število,
ki opisuje moč množice

lahko je naravno število, ali
pa neskončno število

Kaj je ordinalno število?

ordinalno število opisuje
urejenost neke množice

če imata dve množici enako
ordinalno število, pomeni
da sta si podobni

Katere tri smeri so se razvile za
reševanje matematike iz krize?

za reševanje matematike iz krize,
so se razvile naslednje smeri:

intuicionizem | obstajati = konstruirati
logicizem | Boole, Frege, Russell
formalizem | sintaksa vs. semantika

Opiši Russlovo protislovje
v Cantorjevi teoriji množic.

Russlovo protislovje je množica , ki
hkrati vsebuje in ne vsebuje sama sebe

S čim je določen formalni aksiomski sistem?

formalni aksiomski sistem
je določen z naslednjim:

simbolični jezik | znaki, funkcije, kvantifikatorji, ...
aksiomi | logični in lastni aksiomi
pravila sklepanja | izpeljava novih formul

Naštej temeljne probleme
osnov matematike.

temeljni problemi osnov
matematike so naslednji:

neprotislovnosti | možno izpeljati
polnosti | možno izpeljati
odločljivosti | obstaja algoritem za izpeljevanje
popolnosti | izpeljava vsake resnične formule

Kateri pravili sklepanja uporablja
predikatni račun prvega reda?

predikatni račun prvega reda
uporablja pravili sklepanja:

modus ponens |
generalizacija |

Kaj je cilj Hilbertovega programa?

cilj Hilbertovega programa je izpeljati vso
matematiko v nekem formalnem sistemu, ki je:

neprotisloven, popoln, odločljiv

vsako trditev bi bilo mogoče preveriti

Kaj pravita Göedlova teorema?

Göedlova teorema pravita:

"če je formalni sistem neprotisloven, ni popoln"
"neprotislovnosti sistema ni moč dokazati znotraj njega"

Kaj je model teorije?

model teorije je interpretacija
aksiomskega sistema, v katerem
so vsi lastni aksiomi veljavni

teorija, ki smiselno
formalizira področje

Kaj sestavlja model rekurzivnih funkcij?

model rekurzivnih funkcij sestavljajo:

začetne funkcije:
ničelna | ζ(x) = 0
naslednik | N(x) = x + 1
projekcija |

pravila sestavljanja:
kompozicija |
primitivna rekurzija |
minimizacija |

Katere splošne modele
računanja smo spoznali?

spoznali smo naslednje splošne modele računanja:

rekurzivne funkcije (GK), splošne rekurzivne
funkcije (HG), λ-račun, Turingov stroj,
Postov stroj, Markovski algoritem

Kakšen je smiseln računski model?

smiseln računski model je tak,
čigar računski stroj(primerek) ima:

končno zmogljive ukaze, končno dolg opis stroja,
iz opisa in stanja je jasen nadaljni potek računanja,
stroj ima potencialno na voljo neskočno
prostora ter časa za računanje

Kako dokazujemo izračunljivost
s pomočjo izreka o rekurziji?

če funkcija nima nepremične točke,
potem po izreku o rekurziji ali
ni totalna ali ni izračunljiva

Katere osnovne načine uporabe
Turingovega stroja smo spoznali?

osnovni načini uporabe
Turingovega stroja so:

računanje vrednosti funkcije
generiranje elementov množice
ugotavljanje pripadnosti množici

Kaj omogoča izrek o rekurziji?

izrek o rekurziji nam omogoča izvajanje
rekurzivnih programov na Turingovih strojih

Ni mi uspelo razčleniti (slovarska napaka): \varphi_{f(n)}(x)=[...n...x...]\ \}\ \mbox{\tiny PROGRAM}

Katere vrste računskih
problemov poznamo?

poznamo naslednje vrste
računskih problemov:

odločitveni | da/ne problemi
iskalni | en element množice z lastnostjo
preštevalni | koliko elementov ima lastnost
naštevalni | vsi elementi, ki imajo lastnost

Katere možnosti se pojavijo pri
določanju odločljivosti in

pri določanju odločljivosti se
pojavijo naslednje možnosti:

obe množici odločljivi, obe neodločljivi,
ena je polodločljiva in druga neodločljiva

Na katere načine dokazujemo
neizračunljivost problemov?

neizračunljivost problemov dokazujemo
z naslednjimi metodami dokazovanja:

diagonalizacija | z diag. v protislovje
m-prevedba | N neodl., vodi v protislovje
z izrekom o rekurziji | ni nepremične točke ni totalna/ni izr.
z Riceovim izrekom | netrivialne lastnosti so neodločljive

Kaj pravi Cobham-Edmondsova teza?

Cobham-Edmondsova teza pravi, da
sta časovni zahtevnosti reševanja nekega
problema na dveh računskih modelih
polinomsko odvisni ena od druge

Kdaj je algoritem učinkovit?

algoritem je učinkovit, če je njegova časovna
zahtevnost navzgor omejena s polinomom

S čim je določen razred zahtevnosti?

razred zahtevnosti je določen z:

vrsto problema | odločitveni, iskalni, ...
računskim modelom | uniformni/neuniformni
mero zahtevnosti | čas, prostor, št. procesorjev, ...
omejitveno funkcijo | log, poly, exp, ...

Naštej nekaj problemov iz razreda NP.

v razredu NP so problemi:

izpolnjivost Boolovih formul,
iskanje Hamiltonovega cikla

Kaj intuitivno pomeni P=NP?

P=NP intuitivno pomeni, da obstajajo
problemi, za katere je težje poiskati
rešitev, kot preveriti, ali je neka
predlagana rešitev pravilna

Kaj pravi Church-Turingova teza?

Church-Turingova teza pravi, da je
"izračunljivo" tisto, kar je izračunljivo
na Turingovem stroju, ali pa na drugem
enako močnem računskem modelu

S čim je določen Turingov stroj?

Turingov stroj je definiran s sedmerko:



določen pa je že samo s funkcijo δ,
pri tem je en ukaz možno zakodirati kot:


=
0ⁱ10^j10^k10^l10^m

Kakšna je povezava med
problemom in jezikom?

povezava med problemom in jezikom
je kodirna funkcija, ki vsaki pozitivni
nalogi problema določi mesto v
jeziku računskega problema

Kako bi lahko izgledal univerzalni Turingov stroj?

univerzalni Turingov stroj bi imel tri trakove:

na prvem bi imel kodo stroja in besedo w,
drugi trak bi bil enak kot pri simuliranem stroju T,
tretji trak pa bi hranil trenutno stanje in končna stanja

Kdaj je formula izpolnjiva in kdaj veljavna?

formula je izpolnjiva, kadar postane
pravilna pri neki prireditvi prostih spr.

veljavna je, če je pravilna pri
vsaki prireditvi prostih spr.

Naštej nekaj primerov lastnih aksiomov.

lastni aksiomi so:

aksiom o vzporednicah v geometriji,
aksiom izbire v teoriji množic