Gráfalgoritmusok

Téma ismertetése

• Általános
  

  Általános

  • Hírfórum
  • VÉGSŐ-JEGY ÖSSZETÉTELE:
    

    • 20% (parciális)
      
    • 30% (laborjegy)
      
    • 50% (vizsgajegy)
    • elmélet papíron
      
    • gyakorlat PC előtt

    2021-2022 tanévtől kezdve ha valakinek a van legalább két 4-e, a kollokvium és parciális elméleti dolgozatai és gyakorlatai között, az automatikusan nem ment át, még ha az átlagok meg is engednék.
    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
      
      

    
    
  • Jelenlét 2019 URL
• Kollokvium A és B csoport - 2020 Január 6-án Hétfőn
  

  Kollokvium A és B csoport - 2020 Január 6-án Hétfőn

  Nem vehető fel
• Parciális A és B csoport 2019 November 4 hétfő
  

  Parciális A és B csoport 2019 November 4 hétfő

  Nem vehető fel
• Előadás - jegyzet
  

  Előadás - jegyzet

  • Gráfalgoritmusok URL
• 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
    

  • 1. ELŐADÁS Tananyag
  • tesztadat 2 Tananyag
  • Tesztadatok Tananyag
  • 1. labor Tananyag
  • Útmutató a Prüfer kód visszafejtéséhez URL
• 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
    

  • 2. ELŐADÁS Tananyag
  • 2. labor Tananyag
  • ellista Tananyag
  • 14 csomópont 17 él Tananyag
  • 6 szint, 171 csomópont Tananyag
  • 7 szint, 424 csomópont Tananyag
  • 8 szint, 1038 csomópont Tananyag
  • 9 szint, 2537 csomópont Tananyag
  • 10 szint, 6338 csomópont Tananyag
  • 11 szint, 15768 csomópont Tananyag
• 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)
    

  • 3. ELŐADÁS Tananyag
  • 3 labor az A és B csoportok számára Tananyag
  • Karate klub kinagyítva Tananyag
  • A karateklub éllistája Tananyag
• 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

  Gráfok színezése
  

  • kromatikus szám
    
  • klikk-szám
  • alsó/felső becslések a kromatikus-számra
    
  • perfekt gráfok
  • 4/5-szín tételek
    

  • 4. ELŐADÁS Tananyag
  • 4. labor Tananyag
  • Az előadáson bemutatott példa éllistája Tananyag
• 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
    

  • 5. ELŐADÁS Tananyag
  • A genetikai állomány és a gráfelmélet kapcsolata. Euler kör - videók URL
  • A szociális hálók titkos hatása, TED előadás - videó URL
• 6.HÉT
  

  6.HÉT

  • 6. ELŐADÁS Tananyag

    Minimális feszítőfa
    

  • 5. labor Tananyag

    Elvágó élek/pontok
    

  • Elvágó élek és pontok labor Tananyag
  • Éllista Tananyag
  • Az algoritmusok hatásai világunkban, TED előadás - videó URL
• 7. HÉT
  

  7. HÉT

  • 7. ELŐADÁS Tananyag

    Egy pontból induló legrövidebbút algoritmusok (VITERBI, DIJKSTRA, BELLMAN-FORD)
    

  • 6. labor Tananyag

    Kruskal és Prim algoritmusok
    

• 8. HÉT
  

  8. HÉT

  • 8.ELŐADÁS Tananyag

    Legrövidebb utak minden pont-pár között (FLOYD algoritmusa)

    Kritikus út módszere
    

  • 7. labor Tananyag

    Viterbi, Dijkstra, Bellman-Ford, Bellman-Ford-More
    

  • Vizsgafeladat 2020 Tananyag
  • Éllista Tananyag
• 9. HÉT
  

  9. HÉT

  • 8. labor Tananyag

    FLOYD algoritmusa; Kritikus út tevékenység gráfban
    

• 10. HÉT
  

  10. HÉT

  • 9. előadás Tananyag

    Ford-Fulkerson algoritmus (maximális folyam)
    

  • Ford Fulkerson algoritmus Tananyag
• 11. HÉT
  

  11. HÉT

  • 11. előadás Tananyag

    Euler/Hamilton gráfok (Utazó ügynök problémája)
    

    Bio-informatikai alkalmazások

    (https://www.coursera.org/learn/genome-sequencing/lecture/hN1E9/)
    

  • 11. labor Tananyag

    Maximális párosítás páros gráfokban (Ford-Fulkerson alkalmazás)
    

  • 9. labor Tananyag

    Mini projekt: a MIT oktatóinak társszerzői gráfja
    

• 12. HÉT
  

  12. HÉT

  • 12. labor Tananyag

    Euler zárt-vonal; Hamiton út turné-gráfban