Snov

Reševanje problemov

• Reševanje problemov
  • Predpogoji za reševanje problemov
  • Osnovni principi pri reševanju problemov

Algoritem

• Algoritem
  • Razvoj algoritma
  • Analiza algoritma
  • Preverjanje algoritma
• Psevdokoda

Abstraktni podatkovni tip

• Abstraktni podatkovni tip

Osnovni abstraktni podatkovni tipi

• Seznam
• Množica
• Vrsta
• Sklad

Časovna zahtevnost algoritma

• Časovna zahtevnost algoritma
  • Velikostni red časovne zahtevnosti
  • Amortizirana analiza časovne zahtevnosti
  • Ocena dejanskega časa izvajanja
  • Razlike med razredi zahtevnosti

Rekurzija-iteracija

• Rekurzija

• Fakulteta
• Hanojski stolpi

• Iteracija
• Spreminjanje repne rekurzije v iteracijo
• Spreminjanje rekurzije v iteracijo s skladom

Drevesa

• Drevesa
  • Abstraktni podatkovni tip drevo
  • Definicija abstraktnega podatkovnega tipa drevo
  • Implementacije dreves
  • Binarna drevesa
  • Predstavitev izrazov z binarnimi drevesi

Metode načrtovanja algoritmov

• Metode načrtovanja algoritmov
  • Prostor stanj
  • Problem trgovskega potnika
  • Deli in vladaj

Strategije iskanja optimalne rešitve

• Strategije iskanja optimalne rešitve
  • lzčrpno preiskovanje
    • Iskanje v širino
    • Iskanje v globino
    • Iterativno poglabljanje
  • Omejeno izčrpno iskanje (razveji in omeji)
  • Metoda "najprej najboljši

Dinamično programiranje

• Dinamično programiranje
  • Reševanje TSP z dinamičnim programiranjem
  • Optimalna binarna iskalna drevesa
    • Abstraktni podatkovni tip slovar
    • Binarno iskalno drevo
    • Gradnja optimalnih binarnih iskalnih dreves
  • Algoritem CYK
    • Kontekstno neodvisne gramatike
    • Normalna oblika po Chomskem
    • Gradnja drevesa izpeljav od spodaj navzgor
  • Kritična pot
    • Abstraktni podatkovni tip graf
    • Analiza kritične poti

Strategije iskanja približnih rešitev

• Strategije iskanja približnih rešitev
  • Požrešno iskanje
    • TSP s trikomiško neenakostjo
    • Abstraktni podatkovni tip prioritetna vrsta
    • Abstraktni podatkovni tip disjunktne množice
    • Iskanje najkrajših poti v usmerjenem grafu
    • Minimalno vpeto drevo
  • Iskanje v snopu
  • Lokalna optimizacija
  • Gradientno iskanje

Stohastični preiskovalni algoritmi

• Stohastični preiskovalni algoritmi
  • Simulirano ohlajanje
  • Genetski algoritmi

Dokazovanje pravilnosti programov

• Dokazovanje pravilnosti programov
  • Pravila izpeljevanja pogojev
  • Parcialna pravilnost programa
  • Totalna pravilnost programa
  • Primeri dokazovanja pravilnosti programa

stari del članka

Urejena snov iz hitrih zapiskov

• Reševanje problemov
• Dinamično programiranje

Hitri zapiski

• 16.02.2006 (Igors)
• 23.02.2006 (Igors)
• 23.02.2006 (B-D_)
• 02.03.2006 (B-D_)
• 02.03.2006 (Igors)
• 02.03.2006 (frin)
• 09.03.2006 (B-D_)
• 16.03.2006 (B-D_)
• 23.03.2006 (B-D_)
• 30.03.2006 (B-D_)
• 06.04.2006 (B-D_)
• 13.04.2006 (B-D_)
• 20.04.2006 (B-D_)
• 11.05.2006 (B-D_)
• 18.05.2006 (B-D_)
• 25.05.2006 (B-D_

Vaje

• 27.02.2006 (Igors)
• 27.02.2006 (B-D_)
• 27.03.2006 (B-D_)
• 03.04.2006 (B-D_)
• 10.04.2006 (B-D_)
• 24.04.2006 (B-D_)
• 08.05.2006 (B-D_)
• 15.05.2006 (B-D_)
• 29.05.2006 (B-D_)

Izvorna koda

ArithmeticExprNode.java

Vozlišče binarnega drevesa za aritmetične izraze

ArithmeticExprTree.java

Drevo za izračun aritmetičnega izraza

BSTree.java

Binarno iskalno drevo

BSTreeNode.java

Vozlišče binarnega iskalnega drevesa

CriticalPath.java

Določanje kritične poti v grafu

CYK.java

Algoritem CYK

Dictionary.java

Definicija abstraktnega slovarja

DiGraphAdj.java

Usmerjen graf implementiran s s seznamom sosedov

DiGraph.java

Usmerjen graf

DisjointSetForest.java

Disjunktne množice implementirane kot gozd

DisjointSet.java

Disjunktne množice

DisjointSubset.java

Disjunktna podmnožica

EdgeAdj.java

Povezava implementirana s seznamom sosedov

Edge.java

Povezava v grafu

Fibonacci.java

Izračun Fibonaccijeve vrste na dva načina

GeneticProblem.java

Definicija problema za genetski algoritem

Heap.java

Prioritetna vrsta implementirana s kopico

HeapPos.java

Prioritetna vrsta, kjer lahko spreminjamo prioritete implementirana s kopico

HeapPosNode.java

Element prioritetne vrste, kjer lahko zmanjšujemo ključ

KEdge.java

Povezava grafa predstavljenega s seznamoma vozlišč in povezav

KGraph.java

Graf z eksplicitno predsatvitvijo vozlišč in povezav

KGraphList.java

Implementacija grafa predstavljenega s seznamoma vozlišč in povezav

KVertex.java

Vozlišče grafa predstavljenega s seznamoma vozlišč in povezav

ListArray.java

Seznam s poljem

List.java

Abstraktni razred seznam

ListLinked.java

Implementacija seznama s kazalci

ListLinkedNode.java

Element seznama s kazalci

MinimumSpanningTree.java

Algoritmi za minimalno vpeto drevo

OptimalBSTree.java

Optimalno binarno iskalno drevo

PQDecrease.java

Prioritetna vrsta, kjer lahko zmanjšamo ključ

Pravilnost.java

Dokazovanje pravilnosti programov

PriorityQueue.java

Prioritetna vrsta

QueueArray.java

Vrsta s poljem

Queue.java

Vrsta

QueueLinked.java

Vrsta povezana s kazalci

RekurzijaIteracija.java

Poglavje o rekurziji in iteraciji

Search.java

Algoritmi za preiskovanje prostora stanj

SearchState.java

Stanje za preiskovanje v prostoru stanj

Set.java

Množica

SetLinked.java

Množica s kazalci

ShortestPaths.java

Dijkstrin algoritem za drevo najkrajših poti

StackArray.java

Sklad s poljem

Stack.java

Stack

TreeArray.java

Drevo s poljem

TreeArrayNode.java

Vozlišče za drevo s poljem

Tree.java

Drevo (podatkovna struktura)

TreeLSRS.java

Drevo v predstavitvi levi sin, desni brat

TreeLSRSnode.java

Vozlišče drevesa v predstavitvi levi sin, desni brat

TreeNode.java

Vozlišče drevesa

TSPgeneticProblem.java

Problem trgovskega potnika pripravljen za reševanje z genetskim algoritmom

TSPproblem.java

Definicija problema trgovskega potnika

TSPsolutionState.java

Stanje v prostoru rešitev za problem trgovskega potnika

TSPstate.java

Stanje za problem trgovskega potnika

UGraphAdj.java

Neusmerjen graf s seznamom sosedov

UGraph.java

Neusmerjen graf

VertexAdj.java

Vozlišče grafa s seznamom sosedov

Vertex.java

Vozlišče grafa