Bakalářská státnice - Informatika - Základy informatiky - obor Programování

From ωικι.matfyz.cz

Súvisiace stránky: Státnice, Základy matematiky, Obecná informatika, Správa počítačových systémů

Tato stránka není kompletní a/nebo může obsahovat chyby!
Table of contents
1 Základy teoretické informatiky

1.1 Logika - jazyk.
1.2 Formule.
1.3 Sémantika.
1.4 Tautologie.
1.5 Rozhodnutelnost.
1.6 Splnitelnost.
1.7 Pravdivost.
1.8 Dokazatelnost.
1.9 Normální tvary výrokových formulí.
1.10 Prenexní tvary formulí predikátové logiky.
1.11 Automaty - Chomského hierarchie.
1.12 Třídy automatů a gramatik.
1.13 Determinismus a nedeterminismus.

2 Algoritmy a datové struktury

2.1 Základní algoritmy - třídění.
2.2 Vyhledávání.
2.3 Algoritmy vyhledávání v textu.
2.4 Kombinatorické algoritmy.
2.5 Grafové algoritmy - nejkratší cesta.
2.6 Minimální kostra.
2.7 Prohledávání grafů.
2.8 Barvení grafů.
2.9 Časová a prostorová složitost algoritmů.
2.10 NP-úplnost.
2.11 Metoda rozděl a panuj.
2.12 Lineární struktury.
2.13 Stromové struktury.
2.14 Haldy.
2.15 Hašování.

3 Databáze

3.1 Podstata a architektury DB systémů. Konceptuální, logická a fyzická úroveň pohledů na data.
3.2 Algoritmy návrhu schémat relací.
3.3 Normální formy.
3.4 Referenční integrita.
3.5 Transakční zpracování.
3.6 Uzamykací protokoly.
3.7 Zablokování.
3.8 ER-diagramy.
3.9 Metody návrhů IS.
3.10 Základy SQL.
3.11 Indexy.
3.12 Triggery.
3.13 Uložené procedury.
3.14 Uživatelé.
3.15 Uživatelská práva.
3.16 Vícevrstevné architektury.
3.17 Vazba databází na internetové technologie.

4 Programovací jazyky a překladače

4.1 Principy a implementace objektově orientovaných jazyků a jazyků s blokovou strukturou.
4.2 Běhová podpora vyšších programovacích jazyků.
4.3 Oddělený překlad, sestavení, řízení překladu.
4.4 Makroprocesory, skriptovací jazyky.
4.5 Neprocedurální programování.
4.6 Struktura překladače, lexikální, syntaktická analýza.
4.7 Interpretované jazyky
4.8 Generické programování a knihovny
4.9 Návrhové vzory.

5 Architektura počítačů a operačních systémů

5.1 Architektury počítače
5.2 Procesory, multiprocesory
5.3 Sběrnice, protokoly
5.4 Vstupní a výstupní zařízení
5.5 Architektury OS
5.6 Vztah OS a HW, obsluha přerušení
5.7 Procesy, vlákna, plánování
5.8 Synchronizační primitiva, vzájemné vyloučení
5.9 Zablokování a zotavení z něj
5.10 Organizace paměti, alokační algoritmy. Principy virtuální paměti, stránkování, algoritmy pro výměnu stránek, výpadek stránky, stránkovací tabulky, segmentace
5.11 Systémy souborů, adresářové struktury
5.12 Plánování pohybu hlav disků
5.13 Bezpečnost

6 Sítě a internetové technologie

6.1 ISO/OSI vrstevnatá architektura
6.2 TCP/IP.
6.3 Bezpečnost, firewally.
6.4 Spojované a nespojované služby, spolehlivost
6.5 Modulace, kódování
6.6 Topologie sítí
6.7 HW a SW technická zařízení pro propojování sítí.
6.8 Bezpečnost
6.9 Internetové a intranetové protokoly a technologie
6.10 značkovací jazyky (XML, HTML)

[edit]

Základy teoretické informatiky

Zkompilovaná verze textu (http://andree.matfyz.cz/statnice/Programovani_1.pdf) ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

Požadavky:[1] (http://www.mff.cuni.cz/studium/bcmgr/ok/i3a6.htm)

  • Logika
    • jazyk, formule, sémantika, tautologie
    • Rozhodnutelnost, splnitelnost, pravdivost, dokazatelnost
    • Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky
  • Automaty
    • Chomského hierarchie
    • třídy automatů a gramatik
    • determinismus a nedeterminismus
[edit]

Logika - jazyk.

[edit]

Formule.

[edit]

Sémantika.

[edit]

Tautologie.

  • Pojem tautologie. (zdroj: Štepánkův slajd 43 z VL0.pdf (http://ktiml.mff.cuni.cz/downloads/VL0.pdf), skripta (http://ktiml.ms.mff.cuni.cz/downloads/Pl_ps.zip) strana 16)
  • Tautologický důsledek. (zdroj: Štepánkův slajd 44 z VL0.pdf (http://ktiml.mff.cuni.cz/downloads/VL0.pdf))
[edit]

Rozhodnutelnost.

[edit]

Splnitelnost.

[edit]

Pravdivost.

[edit]

Dokazatelnost.

[edit]

Normální tvary výrokových formulí.

  • Věta o ekvivalenci. (zdroj: Štepánkův slajd 8 z VL3.pdf (http://ktiml.mff.cuni.cz/downloads/VL3.pdf)) (Jesliže jsou podformule A1..An fle A ekvivalentní s A'1..A'n a A' vytvořím záměnou těchto podformulí, je i A ekvivalentní s A')
  • Důkaz rozborem případů. (zdroj: Štepánkův slajd 15 z VL3.pdf (http://ktiml.mff.cuni.cz/downloads/VL3.pdf)) ( T mn. flí a A,B,C fle pak T,(A v B) |- C právě když T,A|-C a T,B|-C )
  • CNF a DNF. (zdroj: Štepánkův slajd 20 z VL3.pdf (http://ktiml.mff.cuni.cz/downloads/VL3.pdf)) (klauzule = disjunkce literlů, pak CNF je konjunkce klauzulí a DNF je disjunkce konjunkcí literálů)
  • Věta o normálních tvarech. (zdroj: Štepánkův slajd 22 z VL3.pdf (http://ktiml.mff.cuni.cz/downloads/VL3.pdf)) (Ke každé formuli lze sestrojit ekvivalentní formuli v CNF nebo DNF)
[edit]

Prenexní tvary formulí predikátové logiky.

  • Prenexní tvar formule. (zdroj: Štepánkův slajd 3 z PL1.pdf (http://ktiml.mff.cuni.cz/downloads/PL1.pdf)) (fle, kde jsou všechny kvantifikáory na začátku a zbytek je otevřená formule)
  • Věta o prenexních tvarech. (zdroj: Štepánkův slajd 5 z PL1.pdf (http://ktiml.mff.cuni.cz/downloads/PL1.pdf)) (Ke každé fli lze sestrojit fle v prenexním tvaru, která je s ní ekvivalentní)
  • Prenexní operace. (zdroj: Štepánkův slajd 7 z PL1.pdf (http://ktiml.mff.cuni.cz/downloads/PL1.pdf))
[edit]

Automaty - Chomského hierarchie.

[edit]

Třídy automatů a gramatik.

  • Definice všech 4 tříd gramatik. (zdroje: Bartákův slajd 7 z lecture07.pdf (http://ktiml.mff.cuni.cz/~bartak/automaty/lectures/lecture07.pdf) / wikipedie (http://cs.wikipedia.org/wiki/Chomsk%C3%A9ho_hierarchie))
  • Definice konečného automatu. (zdroje: Bartákův slajd 9 z lecture01.pdf (http://ktiml.mff.cuni.cz/~bartak/automaty/lectures/lecture01.pdf) / wikipedie (http://cs.wikipedia.org/wiki/Kone%C4%8Dn%C3%BD_automat#Form.C3.A1ln.C3.AD_definice))
  • Definice zásobníkového automatu. (zdroje: Bartákův slajd 2 z lecture08.pdf (http://ktiml.mff.cuni.cz/~bartak/automaty/lectures/lecture08.pdf) / wikipedie (http://en.wikipedia.org/wiki/Pushdown_automaton#Definition))
  • Definice Turingova stroje. (zdroje: Bartákův slajd 4 z lecture11.pdf (http://ktiml.mff.cuni.cz/~bartak/automaty/lectures/lecture11.pdf) / wikipedie (http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj#Definice))
  • Převody mezi nimi. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Chomsky_hierarchy#External_links))
  • L0(rekurzivně spočetné jazyky) = turingův stroj
  • L1(kontextové jazyky) = lineárně omezený automat (NTS s omezenou páskou)
  • L2(bezkontextové jazyky) = nedeterministický zásobníkový automat
  • L3(regulární/pravé lineární jazyky) = konečný automat
[edit]

Determinismus a nedeterminismus.

  • Nedeterministický konečný automat. (zdroje: Bartákův slajd 4 z lecture03.pdf (http://ktiml.mff.cuni.cz/~bartak/automaty/lectures/lecture03.pdf) / wikipedie (http://en.wikipedia.org/wiki/Nondeterministic_finite_state_machine#Formal_definition))
  • Deterministický zásobníkový automat rozeznává jen deterministické BK jazyky (podmnožina BK jazyků)
  • Turingův stroj: DTS = NTS
  • Konečný automat: DKA = NKA
[edit]

Algoritmy a datové struktury

Zkompilovaná verze textu (http://andree.matfyz.cz/statnice/Programovani_2.pdf) ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

[edit]

Základní algoritmy - třídění.

  • Selection sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Selection_sort))
  • Bubble sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Bubble_sort))
    • Cocktail sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Cocktail_sort))
    • Comb sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Comb_sort))
  • Insertion sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Insertion_sort))
    • Gnome sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Gnome_sort))
    • Library sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Library_sort))
    • Shell sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Shell_sort))
  • Merge sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Merge_sort))
  • Heapsort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Smoothsort))
  • Quicksort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Quicksort))
    • Introsort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Introsort))
  • Radix sort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Radix_sort))
  • Bogosort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Bogosort))
    • An evil sort. (zdroj: wikipedie (http://home.tiac.net/~cri_d/cri/2001/badsort.html#evilsort))
[edit]

Vyhledávání.

  • Lineární vyhledávání. (zdroj: wikipedie (http://sk.wikipedia.org/wiki/Line%C3%A1rne_vyh%C4%BEad%C3%A1vanie))
  • Binární vyhledávání. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Binary_search))
    • Interpolační vyhledávání. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Interpolation_search))
  • Hledání k-tého největšího prvku. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Selection_algorithm))
[edit]

Algoritmy vyhledávání v textu.

  • Rabin-Karp. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm))
  • Knuth–Morris–Pratt (zdroj: wikipedie (http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm))
  • Aho-Corasick (zdroj: wikipedie (http://en.wikipedia.org/wiki/Aho-Corasick_algorithm))
[edit]

Kombinatorické algoritmy.

  • Lineární programování a simplexová metoda. (zdroj: Berkeley (http://www.cs.berkeley.edu/~sinclair/cs170/lp.pdf))
  • Rychlá Fourierova transformace. (zdroj: Berkeley (http://www.cs.berkeley.edu/~sinclair/cs170/fft.pdf))
[edit]

Grafové algoritmy - nejkratší cesta.

  • Dijkstrův algoritmus. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm))
  • Bellman-Fordův algoritmus. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Bellman-Ford_algorithm))
  • Floyd-Warshallův algoritmus. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm))
slidy ze složitosti (http://kti.mff.cuni.cz/~cepek/cer-bile.zip)
skripta diskrétní mat. z všb (http://www.cs.vsb.cz/hlineny/vyuka/DIM-slides/)
[edit]

Minimální kostra.

  • Prim (Jarník, Dijkstra). (zdroj: wikipedie (http://en.wikipedia.org/wiki/Prim%27s_algorithm) - pozor na pseudo-kód, je tam možná chyba)
  • Kruskal. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm))
    • Datové struktury. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_linked_lists))
  • Borůvka. (zdroje: Přednášky z Univerzity v Californii (http://www.ics.uci.edu/~eppstein/161/960206.html#fib) / wikipedie (http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm))
[edit]

Prohledávání grafů.

  • Prohledávání do hloubky. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Depth_first_search))
    • Informované prohledávání do hloubky - heuristiky. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Best-first_search))
    • Aplikace DFS. (zdroj: přednáška z VUT v Brně (http://zorro.fme.vutbr.cz/graphs/foil16.html))
  • Prohledávání do šířky. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Breadth-first_search))
[edit]

Barvení grafů.

  • Barvení grafů obecně. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Graph_coloring))
[edit]

Časová a prostorová složitost algoritmů.

  • Definice algoritmu.
  • Časová a prostorová složitost algoritmů. (slidy z VŠB (http://www.cs.vsb.cz/kot/download/uti-pr-08.pdf))
  • Očková notace. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Big_O_notation))
  • Amortizovaná složitost. (zdroje: Čepkovi slajdy Složitost I (http://ktiml.mff.cuni.cz/~cepek/cer-bile.zip) str.36 / wikipedie (http://en.wikipedia.org/wiki/Amortized))
[edit]

NP-úplnost.

Něco málo je popsáno na posledních slajdech na tomto odkazu (Čepek-ADS): [2] (http://ktiml.mff.cuni.cz/~cepek/ADS-KS.ppt) A o něco více na (zdroje: Čepkovy slajdy Složitost I (http://ktiml.mff.cuni.cz/~cepek/cer-bile.zip) od str.48)

Shrnutí složitosti algoritmů na WolframMathWorld (http://mathworld.wolfram.com/topics/ComplexityofAlgorithms.html)

  • Složitost problému. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Computational_complexity_theory))
  • Definice NP. (zdroj: wikipedie (http://en.wikipedia.org/wiki/NP_%28complexity%29))
  • Vztah P a NP. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP))
  • NP-těžký problém. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Np-hard))
  • NP-uplný problém. (zdroj: wikipedie (http://en.wikipedia.org/wiki/NP-complete))
  • Příklady NP-úplných problémů. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems))
  • Nedokonalé řešení NP-úplných problémů. (zdroj: wikipedie (http://en.wikipedia.org/wiki/NP-complete#Imperfect_solutions))
[edit]

Metoda rozděl a panuj.

  • Metoda rozděl a panuj. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm))
  • Mergesort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Mergesort))
  • Quicksort. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Quicksort))
  • Hanojské věže. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Hanoi_towers#Recursive_algorithm))
  • Master theorem. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Master_theorem))
    • Důkaz master theorem. (zdroj: Univerzita v Indianapolisu (http://www.cs.iupui.edu/~xkzou/teaching/CS580/RecurrenceAndMasterTheorem.ppt))
[edit]

Lineární struktury.

  • Pole.
  • Množina.
  • Spojový seznam.
    • Dvousměrný spojový seznam.
  • Zásobník.
    • Oboustranný zásobník.
  • Fronta.
    • Oboustranná fronta.
    • Prioritní fronta.
[edit]

Stromové struktury.

  • B strom. (wikipedie (http://cs.wikipedia.org/wiki/B-strom#Form.C3.A1ln.C3.AD_definice))
  • B+ strom. (wikipedie (http://en.wikipedia.org/wiki/B%2B_tree))
  • B* strom. (wikipedie (http://en.wikipedia.org/wiki/B%2A_tree))
  • Binární vyhledávací strom. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Binary_search_tree))
  • AVL strom. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Avl_tree))
  • Červeno-černý strom. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Red-black_trees))
  • Intervalový strom.
  • Trie (prefixový strom). (zdroj: wikipedie (http://en.wikipedia.org/wiki/Trie))
    • Patricia trie. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Patricia_trie))
  • Vícerozměrný strom.
[edit]

Haldy.

  • Halda. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Heap_%28data_structure%29))
  • Binární halda. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Binary_heap))
  • Fibonacciho halda. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Fibonacci_heap))
[edit]

Hašování.

(zdroj: Skripta (http://ktiml.ms.mff.cuni.cz/downloads/HASOVANI.PS) Dat.Struktury - Koubek)

  • Hašovací funkce. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Hash_function))
  • Hašovací tabulka. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Hash_table))
  • Hašování se separovanými řetězci
  • Hašování s uspořádanými řetězci
  • Hašování s přemísťováním
  • Hašování se dvěma ukazateli
  • Srůstající hašování (LISCH, EISCH, LICH, EICH, VICH)
  • Hašování s lineárním přidáváním
  • Dvojité hašování
  • Univerzální hašování
  • Perfektní hašování
[edit]

Databáze

Zkompilovaná verze textu (http://andree.matfyz.cz/statnice/Programovani_3.pdf) ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

[edit]

Podstata a architektury DB systémů. Konceptuální, logická a fyzická úroveň pohledů na data.

  • Architektura DB systémů. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Database), Architektury DB (http://www.fs.vsb.cz/books/dbacc20/dbacc01.htm#dbacc022))
  • Architektura DB systémů a ostatně vše kolem databází (zdroj: [3] (http://home.zcu.cz/~ruz/pred_db1.doc))
  • Konceptuální, logická a fyzická úroveň pohledů na data. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Data_modeling))
[edit]

Algoritmy návrhu schémat relací.

  • Pojmy kolem algoritmů (závislosti, klíče, ...). (zdroj: Univerzita Carlton (http://www.scs.carleton.ca/~ldnel/3005notes/normal_forms.html))
  • Algoritmus dekompozice na převod do 3NF. (zdroje: Univerzita Carlton (http://www.scs.carleton.ca/~ldnel/3005notes/decomposition_example.html) / Houstonská univerzita (http://www2.cs.uh.edu/~marek/notes/lecture12/tsld004.htm) / Californská státní univerzita (http://www.sci.csuhayward.edu/~billard/cs4660/node21.html))
  • Algoritmus syntézy na převod do 3NF.
  • Algoritmus na převod do BCNF. (zdroj: Californská státní univerzita (http://www.sci.csuhayward.edu/~billard/cs4660/node23.html)).
[edit]

Normální formy.

  • Přehled normálních forem. (zdroje: Litt's Tips (http://www.troubleshooters.com/littstip/ltnorm.html) / wikipedie (http://en.wikipedia.org/wiki/Database_normalization))
  • 1NF. (zdroje: Skopalův slajd 13 z DBI025_03.ppt (http://urtax.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_03.ppt) / wikipedie (http://en.wikipedia.org/wiki/First_normal_form))
  • 2NF. (zdroje: Skopalův slajd 16 z DBI025_03.ppt (http://urtax.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_03.ppt) / wikipedie (http://en.wikipedia.org/wiki/Second_normal_form))
  • 3NF. (zdroje: Skopalův slajd 18 z DBI025_03.ppt (http://urtax.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_03.ppt) / wikipedie (http://en.wikipedia.org/wiki/Third_normal_form))
  • BCNF. (zdroje: Skopalův slajd 21 z DBI025_03.ppt (http://urtax.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_03.ppt) / wikipedie (http://en.wikipedia.org/wiki/Boyce-Codd_normal_form))
[edit]

Referenční integrita.

  • Referenční integrita. (zdroje: Skopalův slajd 10 z DBI025_07.ppt (http://urtax.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_07.ppt) / wikipedie (http://en.wikipedia.org/wiki/Referential_integrity))
[edit]

Transakční zpracování.

  • Pojem transakce, ACID. (zdroje: Skopalův slajd 6 z DBI025_09.ppt (http://urtax.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_09.ppt) / wikipedie (http://cs.wikipedia.org/wiki/Datab%C3%A1zov%C3%A1_transakce))
  • Commit, rollback (abort). (zdroje: Skopalův slajd 8 z DBI025_09.ppt (http://urtax.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_09.ppt) / wikipedie (http://en.wikipedia.org/wiki/Commit_%28data_management%29))
  • Savepoint. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Savepoint))
  • Žurnál. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Transaction_log))
  • Úrovně izolace. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Transaction_isolation_level#Isolation_Levels))
[edit]

Uzamykací protokoly.

  • Protokoly řízení konfliktů. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Concurrency_control))
  • Plán, sériový plán. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Schedule_%28computer_science%29))
  • 2-fázové zamykání. (zdroj: wikipedie (http://en.wikipedia.org/wiki/2PL))
  • Striktní 2-fázové zamykání. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Strict_two-phase_locking))
  • Rigorózní 2-fázové zamykání. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Rigorous_two-phase_locking))
  • Konzervativní 2-fázové zamykání. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Conservative_two-phase_locking))
[edit]

Zablokování.

  • Deadlock. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Deadlocks))
  • Wait-for grafy. (zdroj: University of Iowa (http://www.cs.uiowa.edu/~jones/opsys/notes/17.html))
  • Priorizace transakcí.
  • Protokol časových razítek. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Timestamp-based_concurrency_control))
  • Stromový protokol.
  • Multiverzovací protokol. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Multiversion_concurrency_control))
  • Wait-die a wound-wait strategie. (zdroj: Santa Clara University (http://www.cse.scu.edu/~jholliday/dd_9_16.htm) - v kapitole Deadlock Avoidance)
  • Optimistické algoritmy. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Optimistic_concurrency_control))
[edit]

ER-diagramy.

  • ER-diagramy. (zdroj: wikipedie (http://en.wikipedia.org/wiki/ER_diagram))
  • Entita.
  • Vztah.
  • Atribut.
  • Slabé entitní typy.
  • Integritní omezení (kardinality).
  • Dědičnost (ISA-vztah).
  • Druhy dědičnosti (partial / exclusive, total / overlapping).
[edit]

Metody návrhů IS.

  • Asi obecné informace o návrhu tabulek.
[edit]

Základy SQL.

  • DML. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Data_Manipulation_Language))
    • SELECT. (zdroje: wikipedie (http://cs.wikipedia.org/wiki/SELECT#Syntaxe) / wikipedie (http://en.wikipedia.org/wiki/Select_%28SQL%29))
    • UPDATE. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/UPDATE))
    • DELETE. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/DELETE))
    • INSERT. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/INSERT))
  • DDL. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Data_Definition_Language))
    • CREATE. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Create_%28SQL%29))
    • ALTER. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Alter_%28SQL%29))
    • DROP. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Drop_%28SQL%29))
  • DCL. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Data_Control_Language))
[edit]

Indexy.

  • Index. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Index_%28database%29)).
  • Manipulace s indexy v SQL.
[edit]

Triggery.

  • Trigger. (zdroj: Kopeckého slajdy (http://www.ms.mff.cuni.cz/~kopecky/vyuka/dbapl/dbaslide.ppt) na Databázové aplikace)
  • Manipulace s triggery v SQL.
[edit]

Uložené procedury.

  • Uložené procedury. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Stored_procedure))
[edit]

Uživatelé.

  • Manipulace s uživateli. (zdroj: SQL Zoo (http://sqlzoo.net/howto/source/z.dir/i10others.xml))
[edit]

Uživatelská práva.

[edit]

Vícevrstevné architektury.

(zdroj: Slidy VUTBR (http://www.fit.vutbr.cz/study/courses/DSI/public/pdf/nove/10_clsrv.pdf))

Srovnání architektur: http://www.sei.cmu.edu/str/descriptions/clientserver.html

[edit]

Vazba databází na internetové technologie.

  • Niesom istý, ale možno tým je myslené niečo takéto (zdroj: fit.vutbr (http://www.fit.vutbr.cz/study/courses/DSI/public/pdf/nove/DodatekC_WWW.pdf))
[edit]

Programovací jazyky a překladače

Zkompilovaná verze textu (http://andree.matfyz.cz/statnice/Programovani_4.pdf) ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

[edit]

Principy a implementace objektově orientovaných jazyků a jazyků s blokovou strukturou.

  • Třída.
  • Dědičnost.
  • Polymorfismus.
  • Obalení.
  • Virtuální funkce. (zdroj: Bednárkuv slide [4] (http://ulita.ms.mff.cuni.cz/mp/vyuka/PRG029/slides/html/PRG029-B-2005_files/v3_slide0189.html) a [5] (http://ulita.ms.mff.cuni.cz/mp/vyuka/PRG029/slides/html/PRG029-B-2005_files/v3_slide0199.html))
[edit]

Běhová podpora vyšších programovacích jazyků.

Yaghobove slidy (http://ulita.ms.mff.cuni.cz/pub/predn/pp/pp-08-rt.ppt)
  • Statická podpora a dynamická podpora.
  • Rozdělení paměti.
  • Stav paměti před spuštěním.
  • Konstruktory, destruktory globálních proměnných.
  • Volací konvence.
[edit]

Oddělený překlad, sestavení, řízení překladu.

slidy (http://ulita.ms.mff.cuni.cz/mff/sylaby/prg029.html) k přednášce PRG029 - Programování v C a C++
[edit]

Makroprocesory, skriptovací jazyky.

[edit]

Neprocedurální programování.

  • Neprocedurální, logické a funkcionální programování.
  • Prolog.
  • Haskell.
  • Lisp.
[edit]

Struktura překladače, lexikální, syntaktická analýza.

  • Lexikální analýza (token, pattern, lexém) (slidy Principy překladačů (http://ulita.ms.mff.cuni.cz/pub/predn/pp/pp-03-lasxa.ppt))
    • Pomocí konečného automatu
      • Chyba lexikální analýzy nastává když je ukončeno v nepříjmacím stavu (špatný vstup)
      • Řešení: ignorovat chybu, domyslet správn správný vstup
    • LA zdlouhavá -> Bufferování vstupu
    • Pro přenositelnost stačí měnit jen v LA
    • výstup - token (=vstup do syntaktické analýzy (=terminál))
    • pattern - regulární výraz, popisuje množinu řetězců pro určitý token
    • lexém (lexikální element) - odpovídá nějakému patternu nějakého tokenu
TokenLexémregulární výraz
whilewhilewhile
relop<,<=,=,<>,>,>=\<|\<=|=|\<>|>|>=
uint0, 123[0-9]+
  • Syntaktická analýza.
    • Pomocí zásobníkového automatu (BKG)
    • Zjišťuje, zda jsou slova na vstupu ze vstupního jazyka
    • Staví derivační strom, odstraňuje nejednoznačnosti jazyka (dangling else).
  • Sémantická analýza.
  • Generování mezikódu.
  • Optimalizace mezikódu.
  • Generování kódu.
  • Obsluha chyb.
  • Druhy jazyků (LR(0), LR(1), LR(k), SLR, LALR, GLR, LL(1), LL(k)).
slidy k přednášce principy překladačů (http://ulita.ms.mff.cuni.cz/pub/predn/pp/)
skripta k podobnému předmětu na slu.cz (http://axpsu.fpf.slu.cz/~vav10ui/prekl.html)
[edit]

Interpretované jazyky

(slidy Principy překladačů (http://ulita.ms.mff.cuni.cz/pub/predn/pp/pp-09-interp.ppt) (9))

  • Překlad do kódu abstraktního stroje.
  • Abstraktní stroj může běžet na různých OS (=přenositelnost)
  • Je to ale pomalejší
  • Překlad JIT (Just-in-time)
  • Dynamická alokace jen s garbage collectorem
  • Dnes typicky Java
[edit]

Generické programování a knihovny

[edit]

Návrhové vzory.

  • Diplomová práce na téma návrhové vzory [6] (http://objekty.vse.cz/Objekty/Vzory)
[edit]

Architektura počítačů a operačních systémů

Zkompilovaná verze textu (http://andree.matfyz.cz/statnice/Programovani_5.pdf) ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

[edit]

Architektury počítače

  • CWUT (http://www.student.cvut.cz/cwut/index.php/Architektury_po%C4%8D%C3%ADta%C4%8D%C5%AF_a_procesor%C5%AF.)
  • Seriál: Co se děje v počítači (http://www.root.cz/serialy/co-se-deje-v-pocitaci/)
[edit]

Procesory, multiprocesory

[edit]

Sběrnice, protokoly

  • Sběrnice (http://cs.wikipedia.org/wiki/Sběrnice)
[edit]

Vstupní a výstupní zařízení

[edit]

Architektury OS

História OS

Monolitický systém (Linux, windows), virtuálne stroje (Java, AS400), Mikrokernel

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-01.ppt)
slidy z Mississippi College (http://sandbox.mc.edu/~bennet/cs422/slides/ch1.pdf)
Wikipedia - operační systém (http://en.wikipedia.org/w/index.php?title=Operating_system&oldid=74329590)
Wikipedia - Jádro (http://en.wikipedia.org/w/index.php?title=Kernel_%28computer_science%29&oldid=74320046)
[edit]

Vztah OS a HW, obsluha přerušení

Druhy prístupu k HW (port CPU, memory-mapped)

Druhy zariadení (blokové / znakové)

Prístup (sekvenčný / náhodný)

Synchrónnosť (disk vs. sieťovka)

Zdieľanie (sieťovka vs. tlačiareň) + spooling

Rýchlosť, smer dát (RO/RW...)

V sw: abstrakcia, jednotné pomenovanie, mount, obsluha chýb

Prerušenie, polling, DMA

Vrstvy I/O (hw -> obsluha prerušenia -> ovládač -> IO subsystém -> userspace IO)

Obsluha prerušenia (uloženie kontextu cpu, potvrdenie radiču, obsluha prerušenia, preplánovanie, obnova kontextu)

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-07.ppt)
[edit]

Procesy, vlákna, plánování

Definície, vlastnosti, rozdiely.... (win vs. lin)

Stavy procesu, súvislosť s prerušeniami

Plánovanie ((ne)preemptívne) - ciele, kritériá, priority

Plánovacie algoritmy: FIFO, Round robin, Viacero front so spätnou väzbou; SMP, Realtime; Win. vs Linux

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-02.ppt)
[edit]

Synchronizační primitiva, vzájemné vyloučení

Aktívne vs. pasívne čakanie, podmienky;

Aktívne: Petersnove riešenie, TSL

Pasívne: Zámky, monitory, semafory, správy (mutexy)

Obedujúci filozofovia, Problém ospalého holiča

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-03.ppt)
[edit]

Zablokování a zotavení z něj

Druhy prostriedkov (odnímateľné? ...), práca s nimi, Coffmanove podmienky,

Riešenie zablokovania: Pštrosí algoritmus, Detekcia a zotavenie, vyhýbanie sa, prevencia

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-04.ppt)
[edit]

Organizace paměti, alokační algoritmy. Principy virtuální paměti, stránkování, algoritmy pro výměnu stránek, výpadek stránky, stránkovací tabulky, segmentace

Hierarchia (veľkosť vs. rýchlosť)

Swapping, Preklad adries

Algoritmy prideľovania: first fit, best/worst fit, buddy systém

Virtuálna pamäť, stránkovanie (viacúrovňové)

TLB, (inverzné) stránkovanie, segmenty (stránkovanie+segmenty), použité tabuľky

Výpadky => výmena: Optimálna stránka, NRU, FIFO, druhá šanca, Hodiny, LRU, random [7] (http://en.wikipedia.org/wiki/Page_replacement_algorithms)

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-05.ppt)
[edit]

Systémy souborů, adresářové struktury

Vlastnosti súborov, pomenovanie, štruktúra (lineárne vs. stromy vs. sekvenčné)

Prístup k súborom (sekvenčný, priamy, memory mapping)

Operácie so súbormi (copy, move...)

Adresáre (hierarchia: stromy, DAG, obecný graf)

Alokácia miesta pre súbory

NTFS, INODE, ext2...

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-06.ppt) / Technická univerzita Ostrava (http://homen.vsb.cz/~kod31/vyuka/opsys/ss5.html)
[edit]

Plánování pohybu hlav disků

FCFS, SSTF, LOOK, CLOOK

RAID (pěkné vysvětlení RAIDů je na [8] (http://www.netcorp.cz/storage_systems/raid_description.htm))

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-07.ppt)
[edit]

Bezpečnost

Ceile útokov, útočníci, autentikácia, vnútorné útoky (vírusy, trojany...), kryptografia (hash, crc, šifrovanie)

slidy (Yaghob) (http://ulita.ms.mff.cuni.cz/pub/predn/ZOS/zos-08.ppt)
[edit]

Sítě a internetové technologie

Zkompilovaná verze textu (http://andree.matfyz.cz/statnice/Programovani_6.pdf) ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

[edit]

ISO/OSI vrstevnatá architektura

  • Vrstevnatá architektura. (zdroje Jiří Peterka (http://www.earchiv.cz/l214/slide.php3?&l=3&me=2) / wikipedie (http://en.wikipedia.org/wiki/ISO/OSI_Reference_Model))
  • Komunikace mezi vrstvami (zdroje: Jiří Peterka (http://www.earchiv.cz/l214/slide.php3?&l=3&me=3))
  • 7 vrstev. (zdroje: Jiří Peterka (http://www.earchiv.cz/l214/slide.php3?l=3&me=21) / wikipedie (http://sk.wikipedia.org/wiki/OSI_model#Opis_vrstiev) / MUNI (http://www.fi.muni.cz/~xkruty/bc/multipage/ch01s01.html))
[edit]

TCP/IP.

  • TCP/IP vrstvy. (zdroje: Jiří Peterka (http://www.earchiv.cz/l214/slide.php3?&l=4&me=2) / wikipedie (http://en.wikipedia.org/wiki/Tcp/ip#The_layers))
[edit]

Bezpečnost, firewally.

  • Útoky.
  • Bezpečnost sítí obecně. (zdroj: Jiří Peterka (http://www.earchiv.cz/a98/a814k180.php3))
  • Firewall. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Firewall_%28networking%29))
  • NAT. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Network_address_translation))
  • Filtrování paketů, IDS, IPS. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Intrusion_prevention_system))
  • DMZ. (wikipedie (http://en.wikipedia.org/wiki/Demilitarized_zone_%28computing%29))
[edit]

Spojované a nespojované služby, spolehlivost

  • Spojované protokoly. Příklady. (zdroje: University of East London (http://homepages.uel.ac.uk/u0214757/H2H.html) / wikipedie (http://en.wikipedia.org/wiki/Connection-oriented_protocol))
  • Nespojované protokoly. Příklady. (zdroje: University of East London (http://homepages.uel.ac.uk/u0214757/H2H2.html)/ wikipedie (http://en.wikipedia.org/wiki/Connectionless_protocol) / inetdaemon (http://www.inetdaemon.com/tutorials/theory/concepts/connection-oriented_vs_connectionless.shtml))
  • TCP. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Transmission_Control_Protocol))
  • UDP. (zdroj: wikipedie (http://en.wikipedia.org/wiki/User_Datagram_Protocol))
  • IP. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Internet_Protocol))
[edit]

Modulace, kódování

Broadband (http://www.earchiv.cz/l214/slide.php3?&l=5&me=3) Druhy kódování (http://www.earchiv.cz/l214/slide.php3?&l=5&me=5) Manchester kód (http://www.earchiv.cz/l214/slide.php3?&l=5&me=4) Modulácia (http://www.earchiv.cz/l214/slide.php3?&l=5&me=8) Modulačná rýchlosť (http://www.earchiv.cz/l214/slide.php3?l=5&me=10) Prenosová rýchlosť (http://www.earchiv.cz/l214/slide.php3?&l=5&me=13) Šírka pásma (http://www.earchiv.cz/l214/slide.php3?&l=5&me=16) Shannonuv teorém (http://www.earchiv.cz/l214/slide.php3?&l=5&me=21)

[edit]

Topologie sítí

  • Sběrnicová topologie. (zdroje: site.the.cz (http://site.the.cz/index.php?id=16) / wikipedie (http://en.wikipedia.org/wiki/Bus_network) / ewa.cz (http://www.ewa.cz/pages1/711.htm#bus) / markonet.cz (http://www.markonet.cz/vyuka/principy/60site/sbernicova.html))
  • Hvězdicová topologie. (zdroje: site.the.cz (http://site.the.cz/index.php?id=17) / wikipedie (http://en.wikipedia.org/wiki/Star_topology) / wikipedie (http://en.wikipedia.org/wiki/Network_topology#Centralization) / ewa.cz (http://www.ewa.cz/pages1/711.htm#star) / markonet.cz (http://www.markonet.cz/vyuka/principy/60site/stromova.html))
  • Prstencová topologie. (zdroje: wikipedie (http://en.wikipedia.org/wiki/Ring_network) / wikipedie (http://en.wikipedia.org/wiki/Network_topology#Daisy_chains) / site.the.cz (http://site.the.cz/index.php?id=18) / ewa.cz (http://www.ewa.cz/pages1/711.htm#ring) / markonet.cz (http://www.markonet.cz/vyuka/principy/60site/kruhova.html))
  • Mesh. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Mesh_networking))
  • Ethernet. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Ethernet))
  • Token ring. (zdroj: wikipedie (http://en.wikipedia.org/wiki/Token_ring))
[edit]

HW a SW technická zařízení pro propojování sítí.

  • Síťová karta (NIC, WNIC). (zdroj: wikipedie (http://en.wikipedia.org/wiki/Network_card) a wikipedie (http://en.wikipedia.org/wiki/Wireless_network_interface_card))
  • Opakovač (repeater). (zdroje: FCIT (http://fcit.usf.edu/network/chap3/chap3.htm#Repeaters) / wikipedie (http://en.wikipedia.org/wiki/Repeater))
  • Rozbočovač (switch, starší ekvivalent je hub). (zdroje: FCIT (http://fcit.usf.edu/network/chap3/chap3.htm#Hubs) / wikipedie (http://en.wikipedia.org/wiki/Network_switch))
  • Bridge. (zdroje: FCIT (http://fcit.usf.edu/network/chap3/chap3.htm#Bridges) / wikipedie (http://en.wikipedia.org/wiki/Network_bridge))
  • Směrovač (router). (zdroje: FCIT (http://fcit.usf.edu/network/chap3/chap3.htm#Routers) / wikipedie (http://en.wikipedia.org/wiki/Router))
  • Wireless Access Point (WAP, taky AP). (zdroje: wikipedie (http://en.wikipedia.org/wiki/Wireless_access_point) / wikipedie (http://sk.wikipedia.org/wiki/Bezdr%C3%B4tov%C3%BD_pr%C3%ADstupov%C3%BD_bod))
  • Káble.
  • Software.
[edit]

Bezpečnost

  • IPSec (zdroj: earchiv (http://www.earchiv.cz/l215/slide.php3?l=2&me=32) Jiřího Peterky) (Pozor! zdroje od profesora Peterky nejsou dostačující, pokud vás zkouší pan Galamboš!)

FUQS (frenquently unexpected questions) od p. Galambose:
- Jaký port používá IPSEC? - žádný, funguje nad síťovou vrstvou.
- Jak uzel A pošle uzlu B packet, když mezi nima stojí gateways, musí uzel A se nějak domlouvit s gateway, aby gateway zajistila IPSEC? - ne, prostě se gateway pošle natvrdo IPSEC packet a gateway podle hlavičky rozpozná, co má dělat.
- jiný zákeřňáky... doporučuju si přečíst slidy p. Galaboše z jeho stránek (http://www.ksi.mff.cuni.cz/~galambos/swi106/part7.pdf)!(Soubor bohuzel uz neexistuje, zajimavy text jsem nasel tady:
An Illustrated Guide to IPsec (http://www.unixwiz.net/techtips/iguide-ipsec.html) ) (edit [4.9.2008]: súbor existuje, akurát je nutné ho zťahovať zo strojov v doméne mff.cuni.cz)
- pri googleni som našiel video z prednášky o IPSec(ČVUT 15.11.2003) (http://www.avc-cvut.cz/avc.php?id=1947), možno to niekomu uľahčí učenie

  • principy fungování AH, ESP
    • transport mode
    • tunnel mode
  • firewall
[edit]

Internetové a intranetové protokoly a technologie

  • RFC. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/RFC))
  • HTTP. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/HTTP))
  • DNS. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/Domain_Name_System))
  • FTP. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/File_Transfer_Protocol))
  • SMTP. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/Simple_Mail_Transfer_Protocol))
  • SSH. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/SSH)
  • IRC, ICQ, ...
  • Ethernet. (zdroj: wikipedie (http://cs.wikipedia.org/wiki/Ethernet))
  • Wi-Fi. (zdroj: wikipedie (http://sk.wikipedia.org/wiki/Wi-Fi)
[edit]

značkovací jazyky (XML, HTML)

  • XML. (zdroj: Academic Tutorials (http://www.academictutorials.com/xml/xml2.asp?page=3))
  • HTML.
Retrieved from "http://wiki.matfyz.cz/wiki/Bakal%C3%A1%C5%99sk%C3%A1_st%C3%A1tnice_-_Informatika_-_Z%C3%A1klady_informatiky_-_obor_Programov%C3%A1n%C3%AD"