UL/FRI/VSP-RI/OAPS2/HitriZapiski/2006-02-16:Igors

Predavanje 16.02.2006

Igor Kononenko (govorilne ure: četrtek 10¹⁵) dr. Marko Robnik Šikonja dr. Matjaž Kukar

Domača stran prof. Igorja Kononenka

na predavanja prihajajte ob 7³⁰, potem imamo 65 minut predavanj, 20 minut odmora in zopet 65 minut predavanj. Avditorne in laboratorijske vaje se začnejo čez 2 tedna.

Na avditornih vajah bomo reševali metode

Na laboratorijskih vajah bo potrebno narediti 2 seminarski nalogi 1. seminarska naloga bo na temo rekurzije in iteracije 2. seminarska naloga bo na temo kombinatorične got.

Če nimate vaj, pisnega izpita ne morete delati.

na pisnem izpitu se pišejo naloge, ki jih bomo delali na avditornih vajah. - Simulacija algoritmov - dokazovanje pravilnosti programov

Na pisni izpit lahko prinesete literaturo (katerokoli), vendar po besedah profesorja ne bo pomagalo, saj ne bo časa. Komunikacija na izpitu je kot vedno prepovedana.

Ustni izpit: vprašal bo kogarkoli, karkoli od snovi

Literatura: Algoritmi in podatkovne strukture II (APS II), Založba FE in FRI, 2004 Avtorja: Igor Kononenko in Marko Robnik Šikonja

Na koncu učbenika je tudi zbirka nalog skupaj z rešitvami, ki so bile na izpitih.

Literature v angleščini na to temo je veliko. Cormen in sodelavci: Introduction to algorithms, MIT Press Cobiss link

Aho A.V, Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms, Addison Weslez, 1984 Cobiss link

Snov:

- metode reševanja problemov => razvoj algoritmov - tehnike načrtovanja algoritmov => preiskovalni algoritmi - sistematični pristop: abstraktni podatkovni tipi (tukaj je potrebno poskrbeti za varnost!)

reševanje problemov: 1. Rekurzija - Iteracija 2. Algoritem:

  - načrtovanje
  - analiza

3.

  - Deli in vladaj
  - izčrpno preiskovanje (širina, globina, iterativno pogl.)
  - omejeno izčrpno
  - najprej najboljši (best first search)
  - dinamično programiranje (lahko uporabimo samo če je problem vnaprej definiran)
  - požrešni algoritem
  - lokalna optimizacija (ena izmed najboljših metod
  - stohastični algoritem
    - simuliranje ohlajanje
    - genetski algoritmi (boj za preživetje - evolucija)
      kodiranje
      ---------------     ---------------
      |//////|      |     |      |//////|
      ---------------     ---------------
             \                   /
               \               /
                ---------------
                |//////|//////|
                ---------------

4. Dokazovanje algoritmov

  Programer je pri pregledu svojih algoritmov subjektiven, saj vidi tisto kar je mislil napisati in ne tisto kar je dejansko napisal.
  Zato je dobro, če ti algoritme pregleda nekdo drug.

REŠEVANJE PROBLEMOV

KAJ -> KAKO Začeli bomo z reševanjem problemov na splošno in ne specifično v programiranju.

sistematični pristop k problemu

- predpogoji
  - pomnenje
    - kratkoročni
      7 kazalci   ] ciklanje!
      osveževanje ]
      
    - dolgoročni
      neomejen
      počasen
      dostop/adresa (asociacije) ] porazdelitev
                     globalno    ]
      umetne nevronske mreže
      asociativne nevronske mreže
    - zunanji
      še počasnejši od dolgoročnega
      zato potrebujemo notacijo
      simboli
      slike, grafi pomagajo spominu (s tem si olajšamo algoritme)
  - procesiranje
    - zaporedno
      zavestno, logično, počasno (simbolni) (leva možganska polobla)
    - vzporedno
      podzavestno, intuitivno, hitro (numerični) (desna možganska polobla)
  - učenje - inteligenca - zavest
    spreminja se znanje:
      - simbolno (logično)
      - intuitivno
    bolje:
      - hitreje
      - natančneje
      - ceneje
    
- osnovni principi

Teorija izračunljivosti

algoritmi: Turingovi stroji rekurzivne funkcije gramatike tipa 0 predikatni račun 1.reda simbolni g.?

|N| = števna neskončnost = |Q| (racionalna) (diskretni svet) 2^|N| = |R| (continuum) (iracionalna vendar realna) = neštevna neskončnost (zvezni svet)

ali je svet zvezen? nikoli ne bomo dokazali

OBJEKTIVNO opisljivo racionalni diskretni merljivo materialni svet znanost posredna izkušnja

SUBJEKTIVNO neopisljivo zvezni, realni nemerljivo zavest duhovnost, mistiki neposredna izkušnja