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.
     
    
    

    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

  Pontozás
  

  Gyakorlat: A pontozás 3-tól indul, a maximum elérhető pontszám 10 pont. 

  - A kódot meg kell tudni magyarázni – kizáró feltétel. 

  -1 helyes eredmény 1 mintafájlra 7 pont 
  

  -működő program, helyes alapalgoritmussal de valamilyen okból az eredmény nem jön ki, 5 pont 

  Elmélet: 6-8 elméleti kérdés. Ebből 1 számítás.
  

  A pontozás 4-től indul, maximálisan elérhető pontszám 10 pont

  A kollokvium végső jegye a gyakorlat és az elmélet számtani középarányosa. 
  

  Az elmélet kidolgozása után neki lehet fogni a gyakorlatnak. A gyakorlat befejezése után a vizsgázó elhagyja a termet, és a folyosón várakozik, amíg a sor nem kerül rá.
  

  Az elméletre és a gyakorlatra szánt idő összesen 1 óra és 40 perc.
  

  
  

  • Tesztfájl az A csoport részére Tananyag
  • Első tesztfajl a B csoport részére Tananyag
  • Második tesztfajl a B csoport részére Tananyag
  • Kollokvium tételek Tananyag
• Parciális A és B csoport 2019 November 4 hétfő
  

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

  Pontozás

  Gyakorlat: A pontozás 3-tól indul, a maximálisan elérhető pontszám 10 pont.

       - A kódot meg kell tudni magyarázni – kizáró feltétel.

       -10 pontért mindkét mintafájlon helyes eredményt kell felmutatni

       -1 helyes eredmény 1 mintafájlra - 7 pont

       - működő program, helyes alapalgoritmussal, de mindkét fájlra helytelen eredmény - 5 pont

  Elmélet: A pontozás 1-től indul, maximálisan elérhető pontszám 10 pont

  
  

  A parciális dolgozat végső jegye a gyakorlat és az elmélet számtani középarányosa.

  Aki nem jelenik meg a parciálison, annak jegye 2-es. Parciálist az A és B csoport csak  november 4-11 között írhat.
• 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
• 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
  • Első példa az előadásról 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
    

• 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