Informatika1-2012/Gyakorlat6

A MathWikiből
(Változatok közti eltérés)
(Feladatok)
 
(egy szerkesztő 10 közbeeső változata nincs mutatva)
1. sor: 1. sor:
==Gráfok==
+
==Bevezetés==
 
+
===Bevezetés===
+
 
* Csúcsok, és közöttük futó élek
 
* Csúcsok, és közöttük futó élek
 
* Irányított vs. irányítatlan gráfok
 
* Irányított vs. irányítatlan gráfok
11. sor: 9. sor:
 
* Klikk, teljes gráf
 
* Klikk, teljes gráf
 
* Összefüggő gráf
 
* Összefüggő gráf
* ...
+
* szomszédsági mátrix vs listás ábrázolás
  
===Gráfok Sage-ben===
+
==Gráfok Sage-ben==
  
 
* szótáras megadás <code> d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} </code>
 
* szótáras megadás <code> d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} </code>
25. sor: 23. sor:
 
* Nagyon sok beépített függvény van, most ezekkel nem foglalkozunk, mert a célunk saját algoritmusok írása.
 
* Nagyon sok beépített függvény van, most ezekkel nem foglalkozunk, mert a célunk saját algoritmusok írása.
  
===Feladatok===
+
==Feladatok==
 +
 
 +
[https://docs.google.com/document/d/1sn7MQl8hyO0ixGrzFWusmmqFbv1x_rwyDEP2PFUHpXA/edit?pli=1 Google doc]
 +
 
 +
===Gráfok===
  
 
====Páros gráfok====
 
====Páros gráfok====
32. sor: 34. sor:
 
* Segítség: <code> L.count(1) </code> megadja, hogy az "1" elem hányszor szerepel egy listában. Ez nagyon áttételes ötlet, nem innen kell elindulni.
 
* Segítség: <code> L.count(1) </code> megadja, hogy az "1" elem hányszor szerepel egy listában. Ez nagyon áttételes ötlet, nem innen kell elindulni.
 
* Sokféle megoldás van! Lehet szabadon gondolkodni, ötletelni.
 
* Sokféle megoldás van! Lehet szabadon gondolkodni, ötletelni.
 
+
====Mélységi keresés====
====Floyd-Warshall algoritmus====
+
*Implementáld rekurzív algoritmussal a mélységi keresést.
 +
http://en.wikipedia.org/wiki/Depth-first_search
 +
====Szélességi keresés====
 +
*Implementáld rekurzív algoritmussal a szélességi keresést.
 +
http://en.wikipedia.org/wiki/Breadth-first_search
  
 
====Dijkstra algoritmus====
 
====Dijkstra algoritmus====
 
+
* Implementáld a Dijkstra algoritmust
====Rekurzív algoritmusok====
+
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
 
+
===Egyéb Rekurzív algoritmusok===
* Elméleti, órán elhangzott anyag ismétlése
+
* Elméleti, órán elhangzott anyag ismétlése, két egyszerű algoritmus kipróbálása.
 +
* http://wiki.math.bme.hu/view/Informatika1-2012/Eloadas4
 +
=== A gráfok lehetnek nagyon nagyok!===

A lap jelenlegi, 2012. október 9., 07:55-kori változata

Tartalomjegyzék

Bevezetés

  • Csúcsok, és közöttük futó élek
  • Irányított vs. irányítatlan gráfok
  • Súlyozott vs. súlyozatlan gráfok
  • Szomszédsági mátrix, "Laplace" mátrix
  • Út, legrövidebb út
  • Átmérő
  • Páros gráfok
  • Klikk, teljes gráf
  • Összefüggő gráf
  • szomszédsági mátrix vs listás ábrázolás

Gráfok Sage-ben

  • szótáras megadás d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]}
  • mátrixos megadás M = Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ])
  • Graph, DiGraph
  • gyors layout: G.show()
  • fokszám: G.degree(), G.degree(5)
  • élek : G.edges()
  • szomszédok: G.neighbors(5)
  • utak: G.distance(2,5),G.diameter()
  • Nagyon sok beépített függvény van, most ezekkel nem foglalkozunk, mert a célunk saját algoritmusok írása.

Feladatok

Google doc

Gráfok

Páros gráfok

  • Írj bipartiteGraph(G) függvényt, mely egy bemenő irányított gráfról eldönti, hogy az páros-e.
  • Segítség: L.count(1) megadja, hogy az "1" elem hányszor szerepel egy listában. Ez nagyon áttételes ötlet, nem innen kell elindulni.
  • Sokféle megoldás van! Lehet szabadon gondolkodni, ötletelni.

Mélységi keresés

  • Implementáld rekurzív algoritmussal a mélységi keresést.

http://en.wikipedia.org/wiki/Depth-first_search

Szélességi keresés

  • Implementáld rekurzív algoritmussal a szélességi keresést.

http://en.wikipedia.org/wiki/Breadth-first_search

Dijkstra algoritmus

  • Implementáld a Dijkstra algoritmust

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Egyéb Rekurzív algoritmusok

A gráfok lehetnek nagyon nagyok!

Személyes eszközök