< Nazad na kurseve

Učimo algoritme

Nauči najefikasnije moguće procedure da se obavi neka radnja. Nauči da meriš složenost algoritama. Nauči algoritme sortiranja i pretrage, koji su presudni kod velikih podataka.

Preduslov za ovaj kurs je poznavanje struktura podataka.

Uvod

• Šta je algoritam?
• Svakodnevni algoritmi

Složenost algoritama

• Složenost algoritama
• Tablica složenosti algoritama
• Zapis složenosti (asimptotska notacija)
• Cena računskih operacija

Algoritmi računanja

• Euklidov algoritam (najveći zajednički delilac)
• Eratostenovo sito (niz prostih brojeva)
• Rusko seljačko množenje
• Naivno množenje
• Određivanje prostog broja
• Srednja vrednost uglova

Algoritmi pretrage

• Algoritmi pretrage
• Linearna pretraga (redom)
• Binarna pretraga (podelom)
  • Vežba: pogađanje zamišljenog broja
• Nalaženje krajnjih vrednosti niza
• Najduža uzastopna sekvenca
• Jedini broj bez para

Algoritmi sortiranja

• Algoritmi sortiranja
• Ređanje mehurićima (bubble sort)
• Ređanje izborom (selection sort)
• Ređanje umetanjem (insertion sort)
• Šelovo ređanje (Shell sort)
• Ređanje spajanjem (merge sort)
• Brzo ređanje (quicksort)
• Ređanje hrpom (heapsort)

Rekurzivni algoritmi

• Šta je rekurzija?
• Rekurzivna funkcija
  • Faktorijel funkcija
  • Fibonačijev niz
  • Kule Hanoja
  • Računanje rekurzijom
  • Poravnanje niza
• Uzajamna rekurzija
• Loše strane rekurzije

Traženje puta i grafovski algoritmi

• Pretraga u dubinu
  • Primer: problem osam dama
• Pretraga u širinu
• Sudar i skretanje
• Dajkstrin algoritam
• A* algoritam

Algoritmi sa strukturama podataka

• Algoritmi sa matricama
• Rotiranje matrice
• Algoritam za proveru uparenih zagrada (stog)
• Algoritam za vraćanje kusura (rečnik)

Ostali algoritmi

• Igra života
• Problem stabilnih parova
• Algoritam uparivanja čarapa