INFO - Informacie o MFF UK

Matematika - informatika (IS: 64243)

Matematika - informatika 

Gestori: Doc. RNDr. Ivan Trencansky, CSc.
	 Doc. RNDr. Ivan Kalas, CSc.

Predmety :
	1. Matematika *) 
	2. Didaktika matematiky *)
	3. Informatika 
	4. Didaktika informatiky

*) Sylaby su v specializacii matematika - fyzika.


 Predmet : Informatika ( obsahuje okruhy 1. a 2.)

(aktualne statnicove otazky sa nachadzaju tiez na katedrovom servri: 
www.edi.fmph.uniba.sk)

1.Teoreticke zaklady informatiky

Formalne jazyky a automaty
- zakladne pojmy (abeceda, jazyk, zakladne operacie)
- generovanie jazykov a typy gramatik (regularne, bezkontextove,
  kontextove, frazove gramatiky) 
- rozpoznavanie jazykov a typy automatov (konecne automaty, zasob-
  nikove automaty, Turingove stroje)
- Chomskeho hierarchia a charakterizacia jednotlivych tried
- pojem nedeterminizmu
- vplyv nedeterminizmu na vypoctovu silu vypoctovych modelov
  (konecnych automatov, zasobnikovych automatov, Turingovych stro-
  jov)
- rozhodnutelne a nerozhodnutelne problemy (problem zastavenia,
  Postov problem)
   
Zlozitost
- zakladne pojmy (problem, rozsah problemu, casova a pamatova
  zlozitost, zlozitost konkretneho algoritmu, asymptoticka  zlozi-
  tost, dolny, horny odhad, optimalny algoritmus, ...)
- metody tvorby efektivnych algoritmov (rozdeluj a panuj, dynamicke
  programovanie, backtracking, ...)
- efektivne reprezentacie datovych struktur (zoznamy, stromy, mnozi-
  ny, ...)
- zlozitost konkretnych problemov (triedenie, vyhladavanie, grafove
  problemy, pattern matching, ...)

Modely
- RAM, TS a vzajomne simulacie
- vztah deterministickeho a nedeterministickeho casu a priestoru
- hierarchia casu a priestoru
- NP-uplnost, problem splnitelnosti
- redukovatelnost NP-uplnych problemov (klika, Hamiltonova kruznica,
  ...)
   
Logika a diskretna matematika
- riesenie rekurentnych problemov, zostavenie a riesenie rekurentnej rovnice 
pre specialne typy uloh: Jozefova uloha, Hanojske veze, rezanie roviny.
- zovseobecnena Jozefova uloha, metoda neurcitych koeficientov. Linearne 
rekurentne rovnice s konstantnymi koeficientami. Dolny a horny odhad, 
hierarchie funkcii podla rychlosti rastu. Master Theorem s naznakom dokazu. 
Aplikacie Master Theoremu. 
- sumy, znacenie, vyznam. Vztah sumy a rekurencie. Zakladne sumacne zakony. 
Praca s viacnasobnymi sumami, Cebysevove nerovnosti. Metody na pocitanie
  sum. Metoda konecneho kalkulu a jej aplikacie na pocitanie sum. 
- kombinatorika. Zakladne kombinatoricke pojmy, kombinacne cisla a ich 
zakladne vlastnosti. Kombinacie, permutacie, variacie bez a s opakovanim. 
- zakladne pojmy z teorie grafov. Eulerovske grafy. Kreslenie grafu jednym 
tahom. Prechod bludiskom. Hamiltonovske grafy. Kreslenie grafu, rovinne 
grafy. Eulerov vzorec a jeho dosledky. Kuratowskeho veta.   

2. Programove systemy

- pocitac von Neumannovskeho typu, kodovanie informacie v pocitaci,
  booleovske funkcie
- kombinacne obvody, sekvencne obvody, digitalne systemy, cislicovy
  pocitac a principy jeho cinnosti, CPU, pamat, I/O
- siete - zakladne delenie, vrstvovy model sieti
- principy fungovania Internetu
- struktura operacneho systemu historia a generacie OS planovaci algoritmus 
- hierarchicky navrh OS pridelovanie pamati 
- problem zablokovania kriticke oblasti semafory 
- virtualizacia strankovanim na ziadost 
- sprava suborov 
- sprava zariadeni 
- jazyk Assembler 
- databazy - zakladne rozdelenie podla databazoveho modelu, konceptualna 
schema 
- databazy - relacna algebra, funkcne zavislosti, normalne formy, kriteria 
navrhu relacnej schemy

Poznamky:
- v ramci 3. okruhu bude cca 10 minutove vystupenie "pred triedou"
- v 3. sa predpoklada zasoba motivacnych uloh ku kazdej teme vhodnej
  na vyuku informatiky (pripadne i variant pre deti ZS - zaujmove
  kruzky)
   

 Predmet: Didaktika informatiky (obsahuje okruhy 3 a. 4.)

3. Metodika vyucovania programovania
   
Programovanie v Pascale
- typ mnozina: deklaracie, operacie s mnozinami, reprezentacia mnoziny v       
pocitaci, uvodne motivacne priklady, priklady pre pokrocilych 
- typ pole a zaznam: deklaracie, priklady na pouzitie 
- podprogramy: deklaracie, typy parametrov, funkcie, rekurzia, uvodne 
motivacne priklady, priklady pre pokrocilych 
- binarne vyhladavacie stromy, reprezentacia, vlastnosti, operacie, uvodne 
motivacne priklady, priklady pre pokrocilych 
- textove subory: zakladne pojmy, sposob prace s nimi, uvodne motivacne 
priklady, priklady pre pokrocilych 
- triedenia: typy, porovnanie, zlozitost intuitivne 
- rekurzia: vyhody, motivacne priklady 
- programove struktury: podmienene prikazy, cykly, vstup/vystup, uvodne 
motivacne priklady, priklady pre pokrocilych 
- dynamicke datove typy: smernik, spajany zoznam, front, zasobnik, uvodne 
motivacne priklady, priklady pre pokrocilych 
- unit korytnacka

Symbolicke programovanie v Comenius Logu
- typy udajov, praca so slovami, zoznamami a obrazkami. Motivacne ulohy na SS 
alebo ZS urovni. 
- procedury (prikazy a operacie, parametre). Rekurzia. Motivacne ulohy na SS 
alebo ZS urovni.
- korytnacia geometria. Praca s jednou korytnackou, pero, tvar, fazy. 
Rekurzivne ciary. Motivacne ulohy na SS alebo ZS urovni. 
- nasobne korytnacky, aktivne, neaktivne. Rozmnozovacie algoritmy. Motivacne 
ulohy na SS alebo ZS urovni. 
- korytnacia geometria. Obrazky, animacne korytnacky. Motivacne ulohy na SS 
alebo ZS urovni. 
- program ako udaje, udaje ako program. Modifikacia procedur (symbolicky 
vypocet nad programom). 
- projektovy pristup vo vyuke informatiky a vo vyuziti informacnych 
technologii v druhych predmetoch. Vizualizacia, otvorenost.


4. Skolska informatika

- Detske programovacie jazyky - charakteristika, ciele, sposob prace, udajove 
struktury, porovnanie s inymi jazykmi. 
- Informatika vo vseobecnom vzdelani. Ciele a organizacia vyuky, skolske a 
mimoskolske aktivity. 
- Navrhnite osnovy povinneho jednorocneho predmetu informatika pre gymnazium.
- Navrhnite celostatny projekt na zavedenie vypoctovej techniky do vyuky ZS. 
- Pre velke knizne (multimedialne) vydavatelstvo mate vypracovat navrh 
konkurzu na vyvoj skolskeho softveru. Ake stanovite ciele konkurzu? Co 
vsetko treba pozadovat? 
- Navrhnite koncepciu modernej ucebnice informatiky pre ZS alebo SS. Spomente 
jestvujuce ucebnice. 
- Pocitacova literatura - knihy a casopisy vydane u nas. Ake su, ake by mohli 
a mali byt. Ako pracovat s pocitacovou literaturou v SS praxi. 
- Navrhnite koncepciu, dlzku trvania, obsah a strukturu doplnujuceho kurzu 
ucitelov informatiky, ktori ucia na SS a su absolventi nasej fakulty. 
- Vseobecne zasady tvorby pedagogickeho softwaru. Vyuzitie multimedialneho 
pocitacoveho prostredia a e-mailu vo vyuke na SS. 
- Internet vo vyucbe informatiky a inych predmetov. 
- Ste spravcom pocitacovej ucebne na SS. Ako ju budete prevadzkovat, s akymi 
problemami treba pocitat. Aky hardware a software navrhnete kupit pri 
zriadovani ucebne? 
- Ako mozno na SS vyuzit pri vyuke informatiky i mimo nej profesionalny 
software typu graficky editor, textovy editor, DTP, databazovy system, 
hypertext, tabulkovy procesor atd. 
- Vyuzitie informacnych technologii pri vyuke handicapovanych deti. Vypoctova 
technika ako prostriedok komunikacie a kooperacie. 
- Navrhnite osnovy predmetu informatika pre 5. rocnik ZS, rozsah, ciele, 
prostriedky vyuky. 
- Informacne technologie v inych predmetoch na ZS, zasady tvorby pedagogickeho 
softwaru pre ZS. Aky hardware by ste navrhli pre ZS (ake pocitace, a tiez 
stavebnice typu LegoDacta). 
- Navrhy UNESCO a IFIP WG 3.1 osnov vyuky informatiky na gymnazium. Vyuzitie 
informacnych technologii v administrative skoly, v skolskej kniznici a pod. 
- Programatorske sutaze (KSP, MO-P), ich vyuzitie vo vyuke informatiky na SS. 
Aku informaticku sutaz by ste zorganizovali pre ziakov ZS? Informatika bez 
pocitaca. 
- Z historie vypoctovej techniky a vyvoja algoritmickeho myslenia. Dolezite 
medzniky v dejinach matematiky (v suvislosti s informatikou). 
- LegoLogo (LegoDacta) - nastroj na ucenie sa a objavovanie. 

Dátum poslednej aktualizácie tohto dokumentu: 30.4.99.
Posledná aktualizácia údajov v systéme: 091006-V393.