INFO - Informacie o MFF UK

Programove a pocitacove systemy (IS: 642332)

Blok :  Programove a pocitacove systemy

Gestor: RNDr. Jan Sturc, CSc.

Predmet: Programove a pocitacove systemy.


1 Kompilatory

 1. Navrh a implementacia kompilatora rekurzivnym zostupom.
 2. Lexikalna analyza (scanner), Thomsonova metoda, navrhu konecneho
    automatu, priamy navrh automatov na rozpoznavanie retazcov - Aho
    Corasickovej metoda.
 3. Metody syntaktickej analyzy zhora dole (LL, rekurzivny zostup).
 4. Metody zdola hore, posunuvo-redukcna schema, operatorovo-precedencne
    metody, LR metody a ich modifikacie.
 5. Syntaxou riadeny preklad a atributove gramatiky. Poradie a sposob
    vyhodnocovania atributov. Pojem cirkularnej definicie a test na
    cirkularitu.
 6. Prax syntaxou riadenych prekladov, zdedene a syntetizovane atributy.
    L-atributy. Lex a Yacc.
 7. Kontrola typov. Striktne typovanie, strukturalna ekvivalencia typov.
    Polymorficke typy a unifikacia.
 8. Podpora kompilatora pocas behu. Pridelovanie pamati. Aktivacne zaznamy.
    Mechanizmy odovzdavania parametrov.
 9. Medzijazyk, formy medzijazyka. Projekt UNCOL.
10. Optimalizacia na urovni medzijazyka. Optimalizacia vyrazov - dag.
    Odstranenenie opakovanych a zbytocnych vypoctov. Optimalizacia cyklov.
11. Metody globalnej optimalizacie, intervalova analyza, T1-T2-redukcia a
    riesenie rovnic toku dat.
12. Generovanie kodu, strategie pridelovania registrov, optimalizacia poctu
    registrov. Kukatkova optimalizacia.

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

2 Databazy

1. Fyzicka organizacia dat

1.1. Zakladne typy dat a typove konstruktory, v programovacich jazykoch.
     Polymorficke typy.
1.2. Abstraktne datove typy. Mnozina, zasobnik, front, prioritny front.
1.3. Implementacia typu mnozina: pomocou vyhladavacich stromov, hasovania.
1.4. Efektivna implementacia prioritneho frontu.
1.5. Implementacia vyhladavacich typov v dvojurovnovej pamati, B-stromy,
     B^*-stromy, dynamicke hasovanie. Indexovo-sekvencne subory ISAM, VSAM.
     Invertovane subory.
1.6. Triedenie. Metody vonkajsieho triedenia.
1.7. Strukturovane programovanie pre spracovanie dat - Jacksonova metoda.

2. Databazy

 2.1. Zakladne pojmy, trojschemova architektura.
 2.2. Modelovanie reality v databazach, entitno-relacny model, relacny
      model, navigacne modely - sietovy a hierarchicky.
 2.3. Zakladne pojmy relacneho modelu. Relacna algebra, relacny kalkul.
      Funkcne zavislosti a kluce.
 2.4. Relacne jazyky SQL, QBE. Prax formulovania dotazov v tychto jazykoch.
 2.5. Teoria navrhovania relacnych databaz. BCNF a 3NF nelamajuca
      zavislosti. Algoritmy pre vyplyvanie medzi zavislostami. Uzatvarajuca
      procedura. Algoritmus pre BCNF a 3NF nelamajucu zavislosti.
 2.6. Zaklady navigacnych a objektovych databaz. Bachmanove diagramy. Navrh
      sietovej databazy. Codasyl DBTG. Programovanie dotazov v sietovych
      databazach.
 2.7. Datalog a negacia v databazach. Zakladny princip byrokracie
      (predpoklad uzavreteho sveta).
 2.8. Spracovanie transakcii, seriovatelnost, zamky, dvojfazovy protokol.
      Journaling, optimisticke strategie synchronizacie transakcii.
      Bezpecnost dat.
 2.9. Optimalizacia dotazov. Optimalizacia selekcii, vypocet prirodzenych
      spojeni a kartezskych sucinov. Algoritmus pre optimalizaciu vyrazov
      relacnej algebry. Polospojenia a optimalizacia v distribuovanych
      bazach dat. Acyklicke hypergrafy a optimalizacia redukciou
      hypergrafu.
2.10. Deduktivne databazy. Logika s funkcnymi symbolami. Vypocet
      SLD-rezoluciou, naivny a seminaivny vypocet logiskych programov.
      Unifikacia. Stromy pravidiel a cielov (Rule/Goal trees). Vazby
      (Binding patterns).
2.11. Optimalizacia dotazov vyhodnocovanych seminaivnym algoritmom. Magicke
      predikaty. Zjednodusenia  a efektivnost metody magickych predikatov.
      Zovseobecnene magicke predikaty.
2.12. Optimalizacia konjunktivnych dotazov. Inkluzia (containment) a
      ekvivalencia konjunktivnych dotazov. Konjunktivne dotazy s
      aritmetickymi predikatmi. Optimalizacia za predpokladu slabej
      ekvivalencie. Dotazy so zjednoteniami a rekurziou.
2.13. Optimalizacia linearnej rekurzie. Lava a prava rekurzia.
      Komutativnost pravidiel. Techniky pocitania (counting techniques).
      Vypocet tranzitivneho uzaveru.

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

3 Softverove inzinierstvo

1. Uvod
1.1. Vodopadovy model procesu vyvoja softveru.
1.2. Inkrementalny model procesu vyvoja softveru.

2. Strategicke planovanie informacneho systemu
2.1. Strategicke planovanie IS: co to je a preco je potrebne.
2.2. Charakteristika postupu pre strategicke planovanie navrhovaneho CCTA:
     popis piatich hlavnych etap.

3. SSADM
3.1. Charakteristika jednotlivych etap (0--6) SSADM.
3.2. Trojschemova architektura.

4. Booch.

5. Semantika a pouzitie diagramov (netreba vediet ich notaciu).

6. Makro a mikro proces O-O vyvoja.

7. OOSE
7.1. Semantika a pouzitie diagramov (netreba vediet ich notaciu).
7.2. Postup vyvoja systemu.

8. UML
 8.1. Metamodel UML.
 8.2. Organizacia diagramov.
 8.3. Genericka notacia.
 8.4. Diagramy statickej struktury (diagramy tried a staticke diagramy
      objektov).
 8.5. Use case diagramy.
 8.6. Sekvencne diagramy.
 8.7. Diagramy kolaboracie.
 8.8. Stavove diagramy.
 8.9. Diagram aktivit.
8.10. Diagram komponentov.
8.11. Diagramy rozlozenia.
8.12. Postup aplikacie UML.

9. Dalsie etapy vyvoja softveru
9.1. Kohezia a zviazanost modulov.
9.2. Opakovane pouzitie (reuse).
9.3. Testovanie.
9.4. Postup pri implementacii a integracii.

10. Riadenie projektov, PRINCE
10.1. Co je to projekt (v zmysle PRINCE) a prehlad otazok, ktorym treba pri
      riadeni projektov venovat pozornost.
10.2. Organizacna struktura.
10.3. Planovanie a odhadovanie.
10.4. Analyza rizika.
10.5. Zabezpecenie kvality.

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

4 Hypermedialne Systemy

1. Uvod.

2. Text
2.1. Principy.
2.2. Systemy.

3. Hypertext a hypermedia
3.1. Definicie.
3.2. Porovnanie s inymi aplikaciami.
3.3. Historia.
3.4. Modely.
3.5. Pouzitie.
3.6. Navigovanie.

4. Hypermedialne systemy
4.1. Architektura.
4.2. Uzly.
4.3. Spojenia.
4.4. Otvoreny hypertext.

5. Hypermedia a Internet
5.1. Internet.

6. Wide Area Information Servers (WAIS)
6.1. Gopher.
6.2. World Wide Web (WWW).
6.3. Hyper-G/HyperWave.

7. Navrh hypermedialnych aplikacii
7.1. Proces navrhovania hypertextu.
7.2. Kognitivne principy navrhovania.
7.3. Relationship Management Methodology (RMM).

8. Adaptivne hypermedia.



5 Pocitacove siete

 1. Telekomunikacie - verejne a sukromne moznosti - koncept prenosu
    informacii v  minulosti a dnes - integracne trendy.

 2. Siete - topologia a geografia - zakladne typy sieti - siete s
    redundanciou - siete bez redundancie  - priklady siete viacerych typov
    - viacurovnove LAN.

 3. Informacne toky (information streams) - zdroje, cielove uzly, prepinaci
    system - jednosmerne a obojsmerne spojenia - konferencie.

 4. Komunikacne kanaly (communication channels) - multiplexovanie -
    virtualne okruhy - uzly s jednosmernou premavkou - uzly s dvojsmernou
    premavkou.

 5. Schema jednoducheho komunikacneho modelu.

 6. Sietovy software - technika strukturovaneho sietoveho softwaru -
    koncepcia vrstiev - protokoly - virtualna komunikacia - fyzicka
    komunikacia - interface.

 7. Vseobecne zavery z oblasti pocitacovych sieti, ktore musia byt
    zakomponovane do viacvrstvovej sietovej architektury.

 8. Adresovanie - pravidla pre prenos udajov - sprava chyb - postupnost
    (naslednost) sprav - problem rychleho odosielatela a pomaleho prijemcu
    - neschopnost akceptovat spravy lubovolnej dlzky - efektivny prenos
    malych sprav - multiplexovanie a demultiplexovanie - smerovanie.

 9. Rozhrania a sluzby - entity - entity rovny s rovnym - poskytovatel
    sluzby - pouzivatel sluzby - vztah medzi vrstvami a rozhraniami -
    Service Access Points (SAP's) -  Interface Data Unit.

10. Spojovane sluzby (connection-oriented services).

11. Nespojovane sluzby (connectionless services).

12. Kvalita sluzby - spolahliva spojovana sluzba  - nespolahliva (t.j.
    nepotvrdzovana) nespojovana sluzba - potvrdzovana datagramova sluzba.

13. Sluzbove  primitiva (service primitives).

14. Referencne modely - ciele a nebezpecenstva - ARPANET, SNA, DNA - Open
    Systems Architecture - norma ISO 7498.

15. TCP/IP - referencny model.

16. Porovnanie OSI a TCP/IP referencneho modelu.

17. Kritika  OSI  modelu a protokolov.

18. Kritika  TCP/IP  referencneho  modelu.

19. Teoreticke zaklady pre datovu komunikaciu - Nyquistovo tvrdenie a
    Shannonove odhady.

20. Prenosove media - vodiace media - nevodiace media - magneticke media -
    krutena dvojlinka - koaxialny kabel - opticke vlakna - siete z
    optickych vlakien - ring, star - porovnanie optickych a metalickych
    kablov

21. Sietove komponenty - techniky prepojovania sieti - charakter kabelaze -
    strukturovana kabelaz.

22. Datove prenosy, UART, USRT, synchronizacia.

23. Bezdrotovy prenos (wireless transmission).

24. Elektromagneticke spektrum - radiove vysielanie (prenosy) - mikrovlnne
    vysielanie (prenosy) - infracervene a milimetrove vlny - svetelne
    prenosy.

25. Telefonny system - modemy - standardy - konstelacne vzorky - modulacne
    techniky.

26. Dialkove vedenia a multiplexovanie.

27. SDH - SONET architektura - definicia ramcov v SDH.

28. Prepinanie (switching) - casovanie udalosti pri jednotlivych typoch
    prepinania.

29. ISDN - system pre domace a firemne vyuzitie.

30. Synchronny a asynchronny prenosovy rezim - ATM -  zakladny ATM - switch
    - knockout switch - banyan switch.

31. Linkova vrstva - MAC - IEEE standardy 802 pre LAN - FDDI - Fast
    Ethernet.

32. Sietova vrstva - interna organizacia sietovej vrstvy -  priklad prenosu
    packetov cez siet - uzly a smerovacie tabulky - porovnanie virtualnych
    kanalov a datagramov - smerovanie - algoritmy smerovania - riadenie
    upchatia siete.

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