Teoretická informatika

[hrochodyl]

v ullmanovskych veciach to mas vysvetlene. Sice tiez tomu nejako extra nechapem ale tam to je aspon popisane

[jardo]

ludia nemate urobene tie algoritmy triedenia? aspon niektore?

[JankoHrasko]

ludia nemate urobene tie algoritmy triedenia? aspon niektore?

selection sort (triedenie použitím minimálneho prvku)
http://dl.dropbox.com/u/4446823/selection%20sort.jpg

[Jerryh]

ludia nemate urobene tie algoritmy triedenia? aspon niektore?

selection sort (triedenie použitím minimálneho prvku)
http://dl.dropbox.com/u/4446823/selection%20sort.jpg

urcite je dobry?  ako vymenis posledne 2 prvky ako nie su zoradene?

[bludar]

ludia nemate urobene tie algoritmy triedenia? aspon niektore?

selection sort (triedenie použitím minimálneho prvku)
http://dl.dropbox.com/u/4446823/selection%20sort.jpg

urcite je dobry?  ako vymenis posledne 2 prvky ako nie su zoradene?

podla mna by to stacilo definovat ze sa vymienaju prvky napravo od tych ukazovatelov

[Jerryh]

ludia nemate urobene tie algoritmy triedenia? aspon niektore?

selection sort (triedenie použitím minimálneho prvku)
http://dl.dropbox.com/u/4446823/selection%20sort.jpg

urcite je dobry?  ako vymenis posledne 2 prvky ako nie su zoradene?

podla mna by to stacilo definovat ze sa vymienaju prvky napravo od tych ukazovatelov

to ma napadlo ako prve, len som sa chcel uistit ze som to dobre pochopil ze sa to neda

[Patto]

nechce niekto nahodou vymenit termin a ist trosku skor? .... z 3.2. na 31.1?

[thom]

Nejake info z dnesnej skusky??

[kilomassa]

1.nerodove  2. algebry algoritmov priklad turing so 2 zasebnikmi druha mala daco so sekvencnym strojom a bubble ostatne nwm...

[frapko]

Nejake info z dnesnej skusky??

27.1.

1.skupina
- Nerodove ekvivalencie
- Algebra algoritmov
- Turingov stroj s jednou vstupnou paskou a dvomi zasobnikovymi - a^2n b^n c^n

2.skupina
- Uzáverové operácie nad jazykmi - Uzavretosť tried jazykov vzhľadom na zobrazenia
- Metapravidlá konštruovania schém a stratégií spracovania dát - Konvolúcia, Evolúcia, Transformácia
- Prepisat Bubblesort do Dijkstry, vzostupne

ak sa mylim v niektorej z otazok v skupine 2, tak ma opravte...

[JankoHrasko]

Nejake info z dnesnej skusky??

27.1.

1.skupina
- Nerodove ekvivalencie
- Algebra algoritmov
- Turingov stroj s jednou vstupnou paskou a dvomi zasobnikovymi - a^2n b^n c^n

2.skupina
- Uzáverové operácie nad jazykmi - Uzavretosť tried jazykov vzhľadom na zobrazenia
- Metapravidlá konštruovania schém a stratégií spracovania dát - Konvolúcia, Evolúcia, Transformácia
- Prepisat Bubblesort do Dijkstry, vzostupne

ak sa mylim v niektorej z otazok v skupine 2, tak ma opravte...

2.skupina
1.otázka : Zobrazenia nad jazykmi. Uzavretosť tried jazykov vzhľadom na zobrazenia
2.otázka (správne)
príklad - zostupne

[spdy_]

ako sa vam dnes darilo? aka bola uspesnost ?  

[bludar]

Moj postreh zo skúšky:

zatiaľ čo som tam bol prešla asi tak polovica možno aj nadpolovica. Neviem ako to šlo ďalej lebo som šiel odpovedať asi tak v prvej osmici ľudí. Na ústnej sa ma vypytoval na tie Nerodove ekv. mal som zaradiť nejaký jazyk do Chomského hierarchie konkrétne sa ma opýtal na jazyk   a^n b^n   že či sa da ako regularny urobiť či čo, odpoveď má byť že sa nedá samozrejme, lebo to vyplyva z Nerodovych Ekv.a zároveň som mal tie Nerodove Ekv. zle, ale nakoniec sme to dali nejako dokopy, opýtal sa ma aj na Kalužninovu alg. a potom už len čo je max subalgebra. Rozlúčil som sa, ako on povedal, s "vysokým Dé". Hurá!!!!

EDIT: Neroda som pochopil viac po prečítaní  neformálneho popisu http://cs.wikipedia.org/wiki/Myhillova-Nerodova_v%C4%9Bta
        Alebo aj http://stargate.cnl.tuke.sk/~klimek/skola/vypracovaneOtazkyZI.pdf tam je v II.16 dokaz ze jazyk 0^n1^n nie je reg. sa mi zda.

[luqash]

Moj postreh: mat priklad za 20 bodov ak je priklad za menej tak sa viac pyta :-)

[thom]

Inac neviem ci ste si to niekto vsimli, ale ja som si zapisoval co bolo na akom termine a vsimol som si, ze na kazdom druhom termine boli skoro tie iste otazky.
Takze na 31.1.2011 podla mojich vypoctov vychadza nieco take

A)
1.otazka:
Turingovsky vypočítateľné funkcie ( + príklad )
2.otazka:
Algebra logiky a problém funkcionálnej úplnosti. Algebra boolovských funkcií BF a problém funkcionálnej úplnosti BF

B)
1.otazka:
baza, poly mono druhova algebra. Alegebraicke systemy. Logicko funkcne modely.
2.otazka:
Uzaverove operacie. Uzaverove operacie nad jazykom. Elementerne uzaverove operacie nad triedami jazykov

priklad- prevod AD do AJ  + nejaky TS s dvoma zasobnikmi, alebo s dvoma pocitadlami

A taktiez 3.1.2011 by malo byt nieco take ako bolo dnes.
Ale to si vie zistit kazdy pozorny citatel

[deCode666]

Moj postreh: mat priklad za 20 bodov ak je priklad za menej tak sa viac pyta :-)

a keď máš príklad na 0? ... resp. nemáš príklad? 

[navarro]

Moj postreh: mat priklad za 20 bodov ak je priklad za menej tak sa viac pyta :-)

a keď máš príklad na 0? ... resp. nemáš príklad? 

Ta sa ti ani neoplati cakat na vyhodnotenie  ...resp by si musel mat teoreticke napisane perfektne dobre, lepsie jak v skriptach 

[luqash]

thom -> Korecko povedal, ze mame odkazat dalsim, ze na dalsi termin budu nove otazky :-) neviem co je na tom pravdy mozno zartoval
deCode -> ked mas nula bodov respektive malo bodov tak sa asi ani nic nepyta a posle ta prec

ale sa mi paci ako kazdy sa pyta a co ked mam tolko a tolko bodov a co ked da taku a taku otazku proste TREBA SA NAUCIT VSETKO to je jedina istota
tiez sa netreba spoliehat ani na ludi, ktori tvrdia, ze sa to ucili par dni a spravili to lebo ti vacsinou zabudnu povedat, ze orafali priklad od kolegu tak isto ako aj teoriu a Hudak im na to nahodou neprisiel respektive maju minimalne IQ 150 a vsetko si odvodili sami(su aj taki)

inak toto bola jednoznacne najtazsia skuska aku som za posledne 4 roky mal takze si to netreba prekladat na piaty rocnik, ale spravit to hned :-)

[Ali N]

Mam pocit ze dnes bol ochotnejsi dat znamku nez minule (20.1.), mozno to bolo aj tym ze som mal viac napisane ale minule ked som nevedel jednu otazku co mi dal na ustnej tak ma poslal prec (resp. pytal sa dalej, snazil sa ma naviest na spravnu odpoved ale stale sa tocil okolo tej jednej otazky), zatial co teraz sa ma spytal na sekvencne stroje, ked som nevedel tak mi vysvetlil ze co chcel pocut a dal mi dalsiu otazku ... neviem ci to fakt bolo tym ze som mal viac napisane alebo to zalezi od nalady, ale mne je to uz jedno, hlavne ze mam svoje D61

[jardo]

ludia nevedli by ste sem hodit co je to transformacii, vela som toho v skriptach nenasiel
DIKY

[Sxx]

ak ma niekto zapisane ake otazky boli na terminoch po 17.1 do 27.1 tak dajte. Neviem to tu najst, asi to skapalo s DB

[thom]

suhrn otazok zo semestra:
=====================4.1.2011==========================
A)
T1:  Uzaverove operacie. Uzaverove operacie nad jazykom.
       Elementerne uzaverove operacie nad triedami jazykov
T2 Algebra: baza, poly mono druhova algebra. Alegebraicke systemy. Logicko funkcne modely.
P: Zostrojte algoritmus Dijkstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne.

B)
T1 - Automatove zobrazenia - vlastnosti k tomu
T2 - Metaalgebra algoritmov, kriterium funkcionalnej uplnosti v dijkstrovej metaalgebre.
P - Polynom zegalkina z dvoch funkcii.

=====================11.1.2011==========================
Len jedna skupina bola

TI2I.6 : Turingovsky-vypocitatelne funkcie. Definicia a ilustracia na priklade.

TI2II.6 : Algebra logiky a problem funkcionalnej uplnosti.
     Algebra boolovskych funkcii (BF) a problem funkcionalnej uplnosti systemov BF.

Priklad
Previest do algebry Janova z Dijkstru.

=====================13.1.2011==========================
A)
Dijkstrova algebra + napisat konvoluciu evoluciu
Univerzalny turingov stroj + Halting Problem
Priklad bol stroj s dvoma pocitadlami (a na 2n,b na n,c na n)

B)
Nerodove ekvivalencie
Algebra algoritmov
Prepisat asi Bubblesort do Dijkstry

=====================17.1.2011==========================
A)
1.otazka:
Uzaverove operacie. Uzaverove operacie nad jazykom.
Elementerne uzaverove operacie nad triedami jazykov
2.otazka:
baza, poly mono druhova algebra. Alegebraicke systemy. Logicko funkcne modely.
Priklad: Zostrojte algoritmus Dijkstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne.

B)
1 otazka: turing. vypocitatelne funkcie
2 otazka: alegbra logiky a boolova algebra
priklad: previest do Alg. Janova nejaky bordel...

=====================20.1.2011==========================
A)
prva otazka bol PCP a MPCP a druha otazka graf reprezent. a graf-schema (toto som necakal)

priklad bol turingov stroj rozpoznava L x pricom x patri 0,1,2 * ... kazdy mohol napisat riesenie vlastne niekto pouzil zasobniky niekto ne... s este som zabudol ze podmienka bola aby pocet 1 a 0 bol rovnaky 2 bolo jedno kelo budze...

B)
1. Zobrazenia definovane na jazykoch. Uzavretost tried jazykov vzhladom na zobrazenia.
2. Metapravidla konstrukcie schem a strategie spracovania dat: konvolucia, evolucia, metapravidlo transformacie schem.
PR.: Dijkstra - bubblesort zostupne.

=====================24.1.2011==========================
A)
1.otazka:
Turingovsky vypočítateľné funkcie ( + príklad )
2.otazka:
Algebra logiky a problém funkcionálnej úplnosti. Algebra boolovských funkcií BF a problém funkcionálnej úplnosti BF

B)
1.otazka:
baza, poly mono druhova algebra. Alegebraicke systemy. Logicko funkcne modely.
2.otazka:
Uzaverove operacie. Uzaverove operacie nad jazykom. Elementerne uzaverove operacie nad triedami jazykov

priklad- prevod AD do AJ

=====================27.1.2011==========================
1.skupina
- Nerodove ekvivalencie
- Algebra algoritmov
- Turingov stroj s jednou vstupnou paskou a dvomi zasobnikovymi - a^2n b^n c^n

2.skupina
- Uzáverové operácie nad jazykmi - Uzavretosť tried jazykov vzhľadom na zobrazenia
- Metapravidlá konštruovania schém a stratégií spracovania dát - Konvolúcia, Evolúcia, Transformácia
- Prepisat Bubblesort do Dijkstry, zostupne

[Matejus]

bol by niekto taký láskavý a napísal tu insert sort algoritmus v Dijkstrovej forme ? Ja som si ho totižto napísal, ale vyšlo mi to dosť zložito s piatimi alternatívami, nezdá sa mi to správne. Ďakujem vopred

[thom]

ludia nevedli by ste sem hodit co je to transformacii, vela som toho v skriptach nenasiel
DIKY

V TIMgr7122010 je to na strane 211 - 11.2 Metapravidlo transformácie schém a optimizácia triediaci-ch algoritmov, v podstate cela kapitola popisuje o tranformacii.

[jardo]

[/quote]
V TIMgr7122010
[/quote]

a to kde najdem?