Weekly outline

  • Algoritmi in podatkovne strukture 1

    Namen predmeta je izpopolniti in utrditi znanje iz programiranja (predvsem rekruzije), naučiti se načrtovati algoritme in analizirati njihovo časovno zahtevnost, spoznati osnovne abstraktne podatkovne tipe, kot so seznam, množica, sklad, vrsta, preslikava, drevo, slovar, prioritetna vrsta, disjunktne množice in (ne)usmerjeni graf,  in operacije na njih ter osnovne in učinkovite implementacije le teh.

  • 1 October - 7 October

    Začetek predavanj:
    -  Pregled predmeta in študentskih obveznosti
    - rekurzija (faktoriela, Fibonacci, maximalno ptevilo, potenciranje, višina drevesa, izračun izraza, hanoi)
    - ADT stack (brez implementacije)
    - repna rekurzija: hanoi, faktoriela?
    - Fibonacci iterativno (dinamično programiranje)


    Laboratorijske vaje začnejo v naslednjem tednu 

     

    • 8 October - 14 October

      Predavanja:

      - splošna shema za spreminjanje rekurzije v iteracijo s skladom
      - primer permutacije
      - časovna zahtevnost algoritmov
         - asimptotična (velikostni red) (notacija veliki O, poenostavljanje funkcij, primeri, rekurenčne enačbe za rekurzivne algoritme)

      Laboratorijske vaje: rekurzija


      • 15 October - 21 October

        PREDAVANJA:

          - dejanski čas, primeri
           - razmerja med funkcijami
        - Abstraktni podatkovni tip
        - seznami: ADT List,  abstract class List
             - primer: vsota seznama števil (iterativno in rekurzivno)
             - implementacija: enosmerni seznam s kazalci
             - dvosmerni seznam s kazalci, polje, kurzorji
         

         

        - Laboratorijske vaje: rekurzija

        • 22 October - 28 October

          PREDAVANJA:

          - ADT SET
          - ADT QUEUE
          - ADT STACK
          - Reševanje problemov
          - Reševanje problemov z algoritmi


          Laboratorijske vaje: linearni seznam

          • 29 October - 4 November

            PREDAVANJA zaradi praznika odpadejo

            TA TEDEN VAJE BODO, vendar preusmerjene skupine v sredo in četrtek na druge dneve!

            Laboratorijske vaje: sklad in vrsta

             

            • 5 November - 11 November

              PREDAVANJA:

              - pregled strategij preiskovanja (optimalne, suboptimalne, stohastične, DN binomski koef.),
              - razvoj algoritmov
              - primer razvoja algoritma: križišče, barvanje grafov, greedy



              • 12 November - 18 November

                PREDAVANJA:

                - ADT Preslikava,  zgoščene tabele, Javanske zbirke
                - preskočni seznami
                - drevesa: ADT TREE, height, izpisi


                • 19 November - 25 November

                  PREDAVANJA:

                  - Implementacije dreves (polje, kazalci)
                  - binarna drevesa
                  - izrazna drevesa, evaluate
                  - kontekstno neodvisne gramatike
                  - gradnja izraznega drevesa s pomočjo stream-tokenizerja

                  Laboratorijske vaje: 

                  - preslikava


                  • 26 November - 2 December

                    PREDAVANJA:

                    - ADT slovar,
                     - BST, enojne rotacije, insert v koren in v list
                    - brisanje iz BST, 
                    - lomljena drevesa
                    - rdeče-črna drevesa

                    Laboratorijske vaje:

                    - drevesa s kazalci

                    • 3 December - 9 December

                      PREDAVANJA:

                      - AVL-drevesa
                      - 2-3 drevesa, B drevesa

                      - ADT prioritetna vrsta

                      - kopica,  decrease key, gradnja kopice v linearnem času

                      - heapsort,  dokaz spodnje meje Omega(n log n) = Omega(log n!)



                      Laboratorijske vaje:
                      - zagovor prve seminarske naloge

                      • 10 December - 16 December

                        TA TEDEN NI PREDAVANJ


                        LABORATORIJSKE VAJE:

                        - binarna iskalna drevesa

                        • 17 December - 23 December

                          PREDAVANJA:

                          - ADT disjunktne množice

                          - implementacija z gozdom disjunktnih množic

                          - usmerjeni grafi, ADT DIGRAPH
                          - seznam sosednosti

                          -  neusmerjeni grafi; ADT GRAPH

                          - kritična pot


                          Laboratorijske vaje: RČ drevo, AVL drevo, B-drevo

                          • 24 December - 30 December

                            Vesele praznike in SREČNO v Novem letu!

                            • 31 December - 6 January

                              PREDAVANJA:

                              - Algoritem Dijkstra za gradnjo drevesa najkrajših poti

                              - Minimalno vpeto drevo (MST)
                              - Primov algoritem za MST

                              - Kruskalov algoritem za MST


                              Laboratorijske vaje:

                              - vstavljanje elementov v kopico in odstranjevanje minimalnega elementa iz kopice
                              - vstavljanje v koren BST
                              - usmerjeni graf (programerski del)

                              • 7 January - 13 January

                                PREDAVANJA:

                                - dokazovanje pravilnosti programov:
                                   parcialna in totalna pravilnost, zančna invarianta, primeri


                                • 14 January - 20 January


                                  LABORATORIJSKE VAJE:
                                  -zagovori 2. seminarske naloge