Téma ismertetése
- Általános
Általános
VÉGSŐ-JEGY ÖSSZETÉTELE:
- 20% (parciális)
- 30% (laborjegy)
- 50% (vizsgajegy)
- elmélet papíron
- gyakorlat PC előtt
Továbbá, ha a kollokvium jegye (elmélet és gyakorlat átlaga) 5-nél kisebb, akkor szintén nem ment át a vizsgán, Akinek valamelyik jegye 5-nél kissebb, azt a vizsgát meg kell ismételnie.
Az előadás-jelenlétet, az idén (2019-20 / I), mint pozitív korrekciós tényezőt használjuk fel a labor-tevékenységhez. A részletek végett, hogy ki jöhet kollokviumra/vizsgára a szesszióban, és ki csak pótvizsgára, érdeklődjetek a labor-tanárnőnél v. tanárnál.ŐSZI PÓTVIZSGA:- Mindenki "tiszta lappal" indul. Nem "menthetők át" vizsgajegy-elemek tavaszról, nyárról vagy előző évekről. Csak az számít, ahogy akkor teljesítesz.
- A vizsga (2020. augusztus 31, 9 óra) ONLINE zajlik majd.
- LINK: meet.google.com/faw-dxvv-vcv
- 20% (parciális)
- Előadás - jegyzet
Előadás - jegyzet
- 1. HÉT
1. HÉT
- Alapfogalmak (pont, él, összefüggő komponensek, út/vonal/séta, kör, távolság...)
- Valós hálózatok (óriás komponens, kisvilág tulajdonság...)
- Gráfok ábrázolása a memóriában (éllista, szomszédsági mátrix, szomszédsági lista)
- PRÜFER kód
- 2. HÉT
2. HÉT
Szélességi bejárás (BFS) és alkalmazásai
ÉL-ek fokuszban:
- erős és gyenge kötések
- gráf-particionálás gyenge kötések mentén
- Girvan-Newman algoritmus
- 3. HÉT
3. HÉT
PONT-ok fokuszban
- homofília
- szelekció, szocializáció
- affiliációs hálózatok (páros gráfok; BFS-alkalmazás)
- szegregáció (Schelling modell)
- 4. HÉT
4. HÉT
KLIKK-ek fokuszban:
- pozitív/negatív kapcsolatok
- kiegyensúlyozott +/- hálózatok
- gyengén kiegyensúlyozott +/- hálózatok
- majdnem kiegyensúlyozott +/- hálózatok
- kromatikus szám
- klikk-szám
- alsó/felső becslések a kromatikus-számra
- perfekt gráfok
- 4/5-szín tételek
- 5. HÉT
5. HÉT
DFS és alkalmazásai
- elvágó pontok
- APTA és GAPR algoritmusok (terror-hálózatok)
- valós vs. véletlen gráfok
- 6.HÉT
6.HÉT
Minimális feszítőfa
Elvágó élek/pontok
- 7. HÉT
7. HÉT
Egy pontból induló legrövidebbút algoritmusok (VITERBI, DIJKSTRA, BELLMAN-FORD)
Kruskal és Prim algoritmusok
- 8. HÉT
8. HÉT
Legrövidebb utak minden pont-pár között (FLOYD algoritmusa)
Kritikus út módszere
Viterbi, Dijkstra, Bellman-Ford, Bellman-Ford-More
- 9. HÉT
9. HÉT
FLOYD algoritmusa; Kritikus út tevékenység gráfban
- 10. HÉT
10. HÉT
Ford-Fulkerson algoritmus (maximális folyam)
- 11. HÉT
11. HÉT
Euler/Hamilton gráfok (Utazó ügynök problémája)
Bio-informatikai alkalmazások
(https://www.coursera.org/learn/genome-sequencing/lecture/hN1E9/)
Maximális párosítás páros gráfokban (Ford-Fulkerson alkalmazás)
Mini projekt: a MIT oktatóinak társszerzői gráfja
- 12. HÉT
12. HÉT
Euler zárt-vonal; Hamiton út turné-gráfban