INFO - Informacie o MFF UK

Spolocny zaklad blokoveho studia (IS: 64231)

Blok : Spolocny zaklad odboru INFORMATIKA 

Predmety: Matematika. 
          Zaklady informatiky.


 Predmet: MATEMATIKA

1.1 Matematicka analyza

 1. Limita realnej funkcie realnej premennej. Nutna a postacujuca podmienka
    existencie limity funkcie v bode. Zakladne vety o limitach. Limita
    monotonnych funkcii a postupnosti.

 2. Spojitost funkcie. Zakladne vety o spojitych funkciach v bode. Spojite
    funkcie na mnozine a ich vlastnosti. Rovnomerne spojite funkcie.

 3. Limita funkcie viac premennych. Limita zobrazenia z R^n do R^m.
    Spojitost funkcie viac premennych. Spojitost zobrazenia z R^n do R^m.
    Kompaktne a suvisle mnoziny. Vlastnosti spojitych zobrazeni na
    kompaktnych mnozinach.

 4. Diferencovatelnost funkcie jednej a viacerych premennych.
    Diferencovatelnost zobrazenia z R^n do R^m.  Suvis medzi
    diferencovatelnostou a parcialnymi derivaciami. Spojitost a
    diferencovatelnost. Derivacia zlozeneho zobrazenia. Vety o strednej
    hodnote. Parcialne derivacie vyssich radov, podmienky pre zamennost ich
    derivovania. Taylorov vzorec. Extremy funkcii. Nutne a postacujuce
    podmienky pre existenciu extremu.

 5. Riemannov integral. Zakladne vlastnosti R-integralu. Nutna a
    postacujuca podmienka integrovatelnosti. Niektore mnoziny
    R-integrovatelnych funkcii. Veta o strednej hodnote. Metody vypoctu
    R-integralu. Newton-Leibnizov vzorec.

 6. Nevlastne integraly. Cauchyho-Bolzanova podmienka konvergenicie
    nevlastneho integralu. Kriteria  konvergencie nevlastneho integralu.

 7. Ciselne rady. Kriteria konvergencie. Absolutne a relativne konvergentne
    rady.

 8. Funkcionalne rady a postupnosti. Bodova a rovnomerna konvergencia.
    Kriteria pre rovnomernu konvergenciu postupnosti a radov funkcii. Vety
    o derivovani a integrovani rovnomerne konvergentnych postupnosti a
    radov.

 9. Mocninove rady. Abelova veta, polomer konvergencie. Vlastnosti
    mocninovych radov v intervale konvergencie. Taylorov rad.

10. Linearna diferencialna rovnica 1. a  n-teho radu. Zakladne vlastnosti
    rieseni. Linearna diferencialna rovnica 2. radu s konstantnymi
    koeficientami.

-------------------

1.2 Algebra

Uvodne pojmy: zakladne pojmy z teorie mnozin, relacie, funkcie,
binarne operacie. Pojem grupy, najzakladnejsie vlastnosti a priklady, pojem
pola, najzakladnejsie vlastnosti, priklady.

 1. Vektorove priestory, linearne zobrazenia: priestor, podpriestor,
    linearna zavislost, baza a dimenzia. Steinitzova veta, sucty
    podpriestorov, linearne zobrazenia, kompozicia linearnych zobrazeni,
    inverzne linearne zobrazenia, matica linearneho zobrazenia, jadro a
    obraz linearneho zobrazenia.

 2. Matice a riesenia linearnych rovnic nad polom F: matice, operacie s
    maticami (nasobenie, scitanie), elementarne riadkove operacie,
    trojuholnikovy a redukovany trojuholnikovy tvar matice, systemy
    linearnych rovnic nad polom F, mnozina rieseni homogennych a
    nehomogennych systemov linearnych rovnic, existencia a tvary rieseni.

 3. Determinanty, determinant linearneho zobrazenia a matice. Vlastnosti
    determinantov. Vypocty determinantov a ich pouzitie pri rieseni
    linearnych rovnic a hladani inverznej matice.

 4. Euklidovske vektorove priestory, kvadraticke formy: skalarny sucin,
    matica skalarneho sucinu, vlastnosti skalarneho sucinu, dlzka vektora,
    uhol medzi vektormi, ortonormalna baza euklidovskeho vektoroveho
    priestoru, ortogonalny doplnok, kvadraticke formy, matica kvadratickej
    formy, kanonicky tvar kvadratickej formy, Sylvestrov zakon
    zotvrvacnosti. Kladne (semi-)definitne matice. Sylvestrova podmienka.

 5. Podobnost matic, ortogonalna podobnost matic: matica linearneho
    zobrazenia pri danej baze, definicia podobnosti matic a vztah k
    linearnym zobrazeniam, kedy je matica podobna s diagonalnou maticou,
    ortogonalna podobnost, charakteristicky polynom matice, vlastne cisla
    realnej symetrickej matice.

 6. Grupy: grupy, podgrupy, izomorfizmus a homomorfizmus grup, cyklicke
    grupy (s klasifikaciou) a ich podgrupy, grupy permutacii, rozklad grupy
    podla podgrupy, Lagrangeova veta, homomorfizmus a izomorfizmus grup,
    normalna podgrupa, faktorizacia grupy podla podgrupy.

 7. Okruhy: zakladne vlastnosti operacii v okruhoch, podokruh, ideal
    (hlavny, maximalny, prvoideal), faktorizacia okruhu podla idealu, vztah
    medzi vysledkom faktorizacie a vlastnostami idealu, podla ktoreho sa
    faktorizuje, obor integrity a veta o podielovom poli.

 8. Okruhy hlavnych idealov, existencia jednotky, najvacsi spolocny
    delitel, vlastnosti delitelnosti, ireducibilne prvky, veta o
    jednoznacnom rozklade.

 9. Okruhy polynomov: pojem algebraickeho a transcendentneho prvku pre dany
    okruh, okruh polynomov R[x], okruh polynomov F[x] nad polom F ako
    okruh hlavnych idealov, veta o jednoznacnom rozklade polynomov nad
    danym polom, substitucny homomorfizmus (veta o substitucii), korene,
    viacnasobne korene, Hornerova schema, derivacia, Taylorov rozvoj.

10. Rozsirenia poli: jednoduche, viacnasobne a konecne rozsirenie pola,
    vztah medzi nimi, minimalny polynom daneho algebraickeho prvku,
    transcendentne rozsirenie.

11. Teoria konecnych poli: charakteristika pola, rozkladove pole daneho
    polynomu nad danym polom, veta o existencii a izomorfizmus rozkladovych
    poli, konecne polia - veta o existencii a izomorfizme konecnych poli.

-------------------

1.3 Kombinatorika

Zakladne pojmy. Pravidlo suctu a sucinu. Variacie a kombinacie s opakovanim
a bez opakovania. Permutacie a permutacie s poctom cyklov danej dlzky.
Zakladne kombinatoricke identity. Princip zapojenia a vypojenia, jeho
zovseobecnenia. Pouzitie principu zapojenia a vypojenia. Pocet
surjektivnych zobrazeni a pocet predpisanych surjekcii na konecnych
mnozinach. Polynomicka veta a jej dosledky. Spernerova veta a jej pouzitie.
Dirichletov princip a jeho pouzitie. Konigova lema. Ramseyova veta,
Ramseyove cisla, systemy reprezentantov, Hallova veta, Konigova veta pre
binarne matice. Rozklady (particie) prirodzenych cisel (usporiadane a
neusporiadane). Metoda diagramov. Eulerova veta.

-------------------

1.4 Kombinatoricka analyza

Zakladne metody vypoctu sum. Sumy a rekurentne vztahy. Viacnasobne sumy.
Konecny kalkul. Celociselne funkcie (dolna a horna cela cast, div, mod).
Sumy obsahujuce cele casti. Kombinacne cisla a ich vlastnosti. Binomicka
veta. Kombinatoricke identity.

-------------------

1.5 Teoria grafov

1. Zaklady: stromy, lesy, bipartitne grafy, eulerovske grafy, cyklovy
   priestor grafu.
2. Parenie: Konigova teorema a maximalnom pareni, Hallova teorema (o
   manzelstvach) a ich dosledky. Tuttova teorema o 1-faktore a jej
   zovseobecnenie. Petersenova teorema o 1-faktore v kubickych grafoch.

3. Suvislost: charakterizacia dvoj- a trojsuvislych grafov, Mengerova
   teorema a jej dosledky, hranovo disjunktne kostry v grafe.

4. Planarne grafy: Reprezentacia grafov v rovine a v priestore,
   stereograficka projekcia, Eulerova rovnost, dualita v rovine,
   Kuratowskeho teorema.

5. Farbenie: Heawoodova teorema o 5 farbach, teorema o 4 farbach,
   algoritmus postupneho farbenia (greedy a.), Brooksova teorema o hornom
   odhade chromatickeho cisla, Konigova teorema o hranovom farbeni
   bipartitnych grafov, Vizingova teorema o hranovych farbeniach. Zoznamove
   chromaticke cislo (vyberove cislo).

6. Hamiltonovske grafy: Diracova postacujuca podmienka, hamiltonovske
   kruznice a postupnosti stupnov, Chvatalova teorema.

7. Toky v grafoch: Kirchhoffov zakon, Fordova a Fulkersonova teorema o
   maximalnom toku a reze minimalnej kapacity, jej vyuzitie. Fordov a
   Fulkersonov algoritmus na hladanie maximalneho toku. Grupove toky,
   k-toky pre male k, suvislost s farbeniami.

-------------------

1.6 Logika pre informatikov

Uvod do deklarativneho programovania.

* Prirodzene cisla, parova reprezentacia cisel, kodovanie jednoduchych
  matematickych struktur, rekurzia vs. iteracia.
* Niektore jednoduche aritmeticke funkcie (Gcd, Fib, Sqrt).
* Zoznamy. Zakladne funkcie a predikaty nad zoznamami.
* Triedenie zoznamov (insert sort, quicksort, merge sort).
* Kombinatoricke funkcie. Permutacie.
* Konecne mnoziny. Kodovanie konecnych mnozin pomocou zoznamov. Operacie
  nad konecnymi mnozinami.
* Binarne stromy. Zakladne pojmy (vyska stromu, velkost stromu, prechod
  stromom).
* Binarne prehladavacie stromy.
* Perfektne vyvazene stromy.
* Prioritne fronty. Reprezentacia pomocou perfektne vyvazenych stromov.
* Aritmeticke vyrazy. Denotacna funkcia. Vyhodnocovanie vyrazov z
  postfixovej formy.
* Vyrokova logika. Jazyk, vyrokovologicke ohodnotenie, tautologie.
  Rozpoznavanie tautologii.

Dokazovanie vlastnosti programov.

* Rekurzia a indukcia.
* Induktivne principy: matematicka indukcia a uplna matematicka indukcia,
  parova indukcia, indukcia s mierou, indukcia na zoznamoch, indukcia na
  stromoch, strukturalna indukcia a induktivne predikaty, indukcia so
  substituciou v parametri.
* Dokazovanie vlastnosti programov z prvej casti prednasky.

-------------------

1.7 Numericka matematika

Odhady nepresnosti vypoctov. Aproximacie funkcii polynomami. Interpolacia.
Numericka kvadratura. Metoda najmensich stvorcov. Newtonova metoda. Metoda
regula falsi. Systemy linearnych algebraickych rovnic. Gaussova eliminacia.
Numericke riesenie nelinearnych rovnic, systemy nelinearnych rovnic.

-------------------

1.8 Pravdepodobnost a matematicka statistika

Definicia a vlastnosti pravdepodobnosti. Pojem nahodnej premennej.
Diskretne a spojite nahodne premenne. Stredna hodnota nahodnej premennej a
jej vypocet. Disperzia. Nezavislost. Bernoulliho schema. Zakon velkych
cisel. Centralna limitna veta. Podmienena pravdepodobnost. Bayesov vzorec.
Definicia podmienenej pravdepodobnosti. Pojem nahodneho vyberu. Regresne
priamky, koeficient korelacie. Testovanie statistickych hypotez.
Intervalove odhady.

===================

 Predmet: ZAKLADY INFORMATIKY

2.1 Programovanie

Podprogramy, odovzdavanie parametrov, rekurzia. Metoda vyhladavania s
navratom (backtracking). Vstup a vystup, (standardne) V/V subory, textove a
binarne  subory. Realizacia datovych struktur (zasobnik, front, spajane
zoznamy, stromy, vyhladavacie stromy, grafy, mnoziny, ...) Rozne triediace
algoritmy, vyhladavanie. Objekty v jazyku Pascal (dedicnost, zapuzdrenie,
polymorfizmus).

-------------------

2.2 Principy tvorby software

Diagram datovych tokov. Entitno-relacny diagram a diagram tried.
Strukturovane metody analyzy (Yourdonova metoda). Objektovo-orientovane
metody analyzy (metoda OMT). Metoda riadenia projektov (metoda PRINCE).

2.3 Teoria programovania

PROGRAMOVE SCHEMY. Zakladne pojmy (standardna schema, interpretacia schem,
vlastnosti schem). (Ne)rozhodnutelnost vlastnosti standardnych schem.
Podtriedy standardnych schem s rozhodnutelnymi vlastnostami (volne,
Janovove schemy). Porovnavanie a preklad tried schem - vztahy medzi triedami
standardnych a rekurzivnych schem. Ciastocne interpretovane schemy.

SPRAVNOST PROGRAMOV. Ciastocna a totalna spravnost programov. Invarianty a
induktivne formuly. Metody dokazovania ciastocnej a totalnej spravnosti -
indukcne techniky. Najslabsia vstupna a najsilnejsia vystupna podmienka.
Systematicky vyvoj korektnych programov.

SEMANTIKA PROGRAMOV A JAZYKOV. Vyznam programu. Principy operacnej,
denotacnej a axiomatickej semantiky. Semanticke domeny a ich konstrukcia.
Formalna definicia (operacneho a denotacneho) vyznamu imperativnych a
rekurzivnych programov. Porovnanie operacnej a denotacnej semantiky
imperativnych a rekurzivnych programov. Korektnost vypoctovych pravidiel a
kriteria ich korektnosti.

-------------------

2.4 Principy pocitacov

Zakladne principy cinnosti pocitaca von Neumannovskeho typu.
Mikroinstrukcny subor, mnozina registrov, ALU, spracovanie instrukcii,
osetrenie preruseni, mikroprogramovanie, RISC versus CISC. Pamat, operacna,
pomocna, cache, virtualna. I/O zariadenia, metody I/O udajov, periferne
zariadenia.

-------------------

2.5 Operacne systemy

 1. Vyznam pouzivania jazyka assemblera. Assembler: typy instrukcii,
    zakladne sposoby adresovania (registrovy mod, nepriamy registrovy mod,
    autoinkrement, autodekrement, relativny mod).

 2. Makra - definicia, rozvoj, volanie. Assembler - ulohy, jedno- a
    dvojprechodovy assembler. Makroprocesor - ulohy, jedno- a
    dvojprechodovy makroprocesor, makroassembler.

 3. Struktura operacneho systemu, funkcie a sluzby operacneho systemu -
    systemove volania, zakladne prvky pocitacoveho systemu - procesy a
    subory.

 4. Procesy - vytvaranie, hierarchia procesov, zivotny cyklus procesu,
    komunikacia medzi procesmi.

 5. Synchronizacia procesov - casova zavislost procesov, vzajomne vylucenie
    a sposoby jeho dosiahnutia, klasicke problemy synchronizacie procesov.

 6. Uviaznutie - kriteria pre jeho vznik, metody riesenia problemu
    uviaznutia.

 7. Sprava procesov a procesora - planovace a ich funkcie, algoritmy
    planovania procesov.

 8. Sprava pamate - funkcie, transformacia adries, modely realnej pamate
    (typy spravy pamate: holy pocitac, jeden suvisly usek, staticke suvisle
    useky, dynamicke suvisle useky, strankovanie, segmentacia).

 9. Sprava pamate - modely virtualnej pamate, strankovanie - vypadok
    stranky, nahradzovacie algoritmy, strankovanie na ziadost a pracovna
    mnozina, niektore problemy pri implementacii - zalohovanie instrukcii,
    zamykanie stranok v pamati, zdielanie stranok.

10. Sprava suborov - funkcie, subory, adresare (typy, organizacia,
    implementacia), sprava volneho diskoveho priestoru, sprava priestoru
    prideleneho suboru (DOS, UNIX), zdielane subory (linky).

11. Sprava zariadeni - funkcie spravy zariadeni, technicke charakteristiky
    perifernych zariadeni (delenie V/V zariadeni, pojem riadiaca jednotka,
    priamy pristup do pamate), techniky pridelovania V/V zariadeni, V/V
    software, sprava diskovych poziadaviek.

-------------------

2.6 Databazove systemy

1. Datove modely. Entitno-relacny model. Bachmanove diagramy. Relacny
   model.

2. Architektura DBMS a modelovanie reality. Trojschemova architektura (ANSI
   sparc).

3. Relacny model. Relacna algebra. Tabulkova a predikatova interpretacia
   relacnej algebry. Negacia, domenovo nezavisle a bezpecne formuly.
   Relacny kalkul (domenovy). Relacny jazyk SQL. Programovanie v SQL.

4. Teoria navrhovania relacnych baz dat. Funkcne zavislosti, vyplyvanie,
   Armstrongove axiomy, efektivne odvodenie. Normalne formy 3NF, BCNF.
   Algoritmy pre upravu do normalnych foriem.

5. Transakcie a spracovanie transakcii. Seriovatelnost, test
   seriovatelnosti. Zamky a zamykacie protokoly. Journal, commit a
   rollback. Optimisticke a pesimisticke riadenie transakcii, casove
   razitka.

6. Bezpecnost v databazovych systemoch. Autorizacia, metody ochrany pred
   neopravnenym pristupom. Ochrana  dat pred poskodenim a znicenim -
   backup.

7. Fyzicka organizacia. Dvojurovnovy model pamati a organizacie dat.
   Indexove subory. B a B^*-stromy. Hasovane subory. Dotazy na
   ciastocnu zhodu. Realizacia relacnych operacii. Kompresia dat (staticke
   metody, Ziv-Lempel.

-------------------

2.7 Teoria vypocitatelnosti

Programy a ich reprezentacia pomocou dataflow schem ako model
vypocitatelnosti. (Ciastocne) vypocitatelne funkcie. Veta o normalnej forme
vypocitatelnych funkcii. Vypocitatelne (rozhodnutelne) predikaty a ich
charakteristicke funkcie. Nerozhodnutelne predikaty, specialne predikat
zastavenia. Redukcia predikatov do problemu zastavenia ako metoda dokazu
ich nerozhodnutelnosti.

-------------------

2.8 Formalne jazyky a automaty

Regularne jazyky. Deterministicke a nedeterministicke konecne automaty,
regularne gramatiky, regularne vyrazy, ekvivalencia popisov regularnych
jazykov, Nerodova veta, pumpovacia lema, uzaverove vlastnosti.
Bezkontextove jazyky. Bezkontextove gramatiky, normalne tvary,
nedeterministicke zasobnikove automaty, ekvivalencia zasobnikovych
automatov a bezkontextovych gramatik, uzaverove vlastnosti. Kontextove
jazyky. Kontextove gramatiky, linearne ohranicene automaty, ich
ekvivalencia, uzaverove vlastnosti. Rekurzivne vycislitelne a rekurzivne
jazyky. Turingove stroje, frazove gramatiky, ich ekvivalencia, uzaverove
vlastnosti, univerzalny Turingov stroj, Turingova hypoteza. Nerozhodnutelne
problemy. Diagonalizacia, problem zastavenia, Postov problem,
nerozhodnutelne problemy pre bezkontextove jazyky, rozhodnutelne problemy
pre bezkontextove jazyky, metody dokazovania nerozhodnutelnosti.

-------------------

2.9 Efektivne algoritmy

Problem slovnika (2-3 stromy). Union/Find-Set problem. Algoritmy pre
hladanie najkratsich ciest a najlacnejsej kostry grafu. Principy tvorby
efektivnych algoritmov (vratane konkretnych aplikacii). Rozdeluj a panuj.
Dynamicke programovanie. "Greedy" algoritmy, vyvazenost a volba vhodnej
datovej struktury. Triedy P a NP, polynomialna redukovatelnost, Cookova
veta a NP-uplne problemy.

-------------------

2.10 Algoritmy a datove struktury

1. Matematicke zaklady. Asymptoticke oznacenia pre rast funkcii. Porovnanie
   funkcii na baze asymptotickych oznaceni. Iterativna logaritmicka funkcia
   (log^*). Riesenie rekurencii substituciou, iterativne, rekurzivne stromy
   - master metoda.

2. Algoritmy triedenia. Elementarne, Heapsort, BottomUp Heapsort,
   Quicksort, znahodneny Quicksort - analyza algoritmu. Halda, prioritna
   fronta. Dolny odhad pre triedenia porovnavanim.

3. Linearne triedenia. Counting-sort, Radix-sort, Bucket-sort.

4. Elementarne datove struktury. Elementarne datove struktury, ich
   implementacia, zasobnik, rad, zoznam, strom.

5. Hasovane tabulky. Tabulky s priamou adresaciou. hasovanie so zretazenim,
   s otvorenou adresaciou, univerzalne hasovanie.

6. Vyspelejsie datove struktury. Binarne prehladavacie stromy a problem
   vyvazenosti, cervenocierne stromy.

7. Vyspelejsie techniky tvorby algoritmov. Dynamicke programovanie,
   nasobenie retazca matic; greedy algoritmy, knapsack problem, Huffmanovo
   kodovanie.

Datum poslednej aktualizacie tohto dokumentu: 30.4.99.
Posledna aktualizacia udajov v systeme: 091006-V393.