Téma ismertetése

  • Általános

  • Kollokvium - Január 11-én Pénteken 8:30 tól.

    A jelenlétben pirossal megjelölt diákokat hiányzásaik miatt nem fogadjuk a vizsgán.

    A rózsaszínnel jelölt diákok január 10-ig legalább egy pluszfeladatot (Bellman-Ford, Ford-Fulkerson, Euler kör meghatározása) be kell mutassanak, ahhoz, hogy vizsgázhassanak.

    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. 

    -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 valamilyen okból az eredmény nem jön ki, 5 pont 

    Elmélet: 10-12 elméleti kérdés. Ebből 2 számítás.

    A pontozás 2-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 2 óra és 30 perc.


    • Parciális

      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 3-tól indul, maximálisan elérhető pontszám 10 pont

           -1,2,3 kérdésekre helyes válasz 2 pont, 4-es kérdés 1 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 csak  november 19-23 között lehet írni.

    • Előadás - jegyzet

    • 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

      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

      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

      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
    • 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
    • 7. HÉT

    • 8. HÉT

    • 9. HÉT

    • 10. HÉT

    • 11. HÉT

    • 12. HÉT