Algoritmusok jegyzet

Listák programozási tételei

Elemi feladatok

Az elemi listakezelési feladatok problémamegoldás szempontjából két fő csoportra bonthatók:

• Amikor végig kell nézni a listát:
  • Összesítések (reduce)
    • Megszamolas (count)
    • Összegzés (sum)
    • Maximumkeresés (max)
  • Másolás (map, select)
  • Kiválogatás (filter, where)
  • Csoportosítás (group by)
• És amikor nem:
  • Kiválasztás
  • Keresés
  • Eldöntés

Rendezetlen halmazok programozási tételei

• Ismétlődések eltávolítása (unique)
• Elemvizsgálat -> Eldöntés
• Részhalmazvizsgálat -> Eldöntés
• Unió
• Metszet
• Különbség

Rendezések és keverések:

Rendezések

A rendezések sebesség szempontjából két fő csoportra bonthatók:

• Lassú rendezések: egy $n$ elemű $n^2$ idő alatt rendeznek.
  • Minimumkiválasztásos rendezés (selection sort)
  • Buborékos rendezés (bubble sort)
  • Beszúró rendezés (insertion sort)
  • Héjrendezés (shell sort)
• Gyorsabb rendezések: egy $n$ elemű tömböt $n\cdot \log_2 n$ idő alatt rendeznek.
  • Gyorsrendezés (quick sort)
  • Összefésüléses rendezés (merge sort)
  • Kupac-rendezés (heap sort)

Keverések

• Fisher-Yates-keverés (Fisher-Yates shuffle)

Mohó algoritmusok

Rendezett listák programozási tételei

• Logaritmikus keresés (binary search)
• Rendezett halmazok elemvizsgálata
• Rendezett halmazok részhalmazvizsgálata
• Rendezett halmazok uniója (összefésülés, merge)
• Rendezett halmazok metszete
• Rendezett halmazok különbsége

mátrixok programozási tételei

• Amikor végig kell nézni a mátrixot:
  • Összesítések (reduce)
    • Megszamolás (count)
    • Összegzés (sum)
    • Maximumkeresés (max)
  • Másolás (map, select)
  • Kiválogatás (filter, where)
  • Csoportosítás (group by)
• És amikor nem:
  • Kiválasztás
  • Keresés
  • Eldöntés

Kiválasztási függvények programozási tételei

• Visszalépéses eldöntés
• Visszalépéses keresés
• Visszalépéses kiválogatás
• Visszalépéses maximumkiválasztás

Dinamikus programozás

• Dinamikus programozás

Mátrixok

• Összesítések (reduce)
  • Megszamolas
  • Összegzés
  • Maximumkeresés
• Másolás
• Kiválogatás
• Kiválasztás
• Keresés
• Eldöntés

Gráfalgoritmusok

• Programozási tételek gráfokon (szélességi (breadth first search, BFS) és mélységi bejárás (Depth first search, DFS))
  • Amikor végig kell nézni a gráfot:
    • Összesítések
    • Csoportosítás
    • Kiválogatás
  • És amikor nem:
    • Eldöntés
    • Keresés
• Feszítőfák
  • Szélességi és mélységi bejárás feszítőfája (honnan-vektor)
  • Kruskal-algoritmus
  • Jarník-Prim algoritmus
• Legrövidebb út
  • Szélességi bejárással (honnan-vektor)
  • Dijkstra-algoritmus
  • Floyd-Warshall-algoritmus