kontakt

Wydział Fizyki i Astronomii,
pl. Maxa Borna 9,
50-204 Wrocław,

Sekretariat Instytutu Fizyki Teoretycznej
tel.: 71 375 94 08
71 375 95 66, 71 375 92 86

Sekretariat Instytutu Fizyki Doświadczalnej
tel. 71 375 93 02

Sekretariat Instytutu Astronomii
tel.: 71 337 80 60, 71 372 93 73, 71 337 80 61

Dziekanat
tel.: 71 375 94 04

godziny otwarcia dziekanatu:
9:00-13:00
(w środy nieczynny)

Algorytmy i struktury danych

Kod przedmiotu: 11.3-4-ASD/4
Rok i semestr: II rok (4 semestr)
ECTS: 4 pkt
Metody dydaktyczne:
Treści merytoryczne przedmiotu:
Najprostsze algorytmy: Euklidesa NWD, sito Erastotenesa. Podstawowe struktury danych: tablica, lista, drzewo BST. Algorytmy rekurencyjne (operacje na drzewach). Twierdzenie o rekursji uniwersalnej. Algorytmy sortujące: insertion sort, heapsort, mergesort, quicksort, ,przez zliczanie, pozycyjne. Zasada Dziel i Zwyciężaj: zastosowanie w algorytmach merge-sort, quicksort. Haszowanie: łańcuchowe, otwarte, warianty h. otwartego. Struktury słownikowe: Drzewa poszukiwań binarnych BST (z implementacja), Drzewa czerwono-czarne, B-drzewa, Kopce złączalne (dwumianowe). Programowanie dynamicznie: triangulacja optymalna. Algorytmy zachłanne na przykładzie generatora kodów Huffmana. Grafy: implementacje przez macierz sąsiedztwa, oraz listy sąsiadów. Algorytmy: Kruskala i Prima (MST) oraz Dijkstry.
Założenia i cele przedmiotu:
Po zakończeniu nauki w ramach tego przedmiotu student powinien znać wybrane algorytmy oraz techniki projektowania algorytmów i oceny ich złożoności. Powinien posiadać umiejętność implementacji wybranych algorytmów w języku C++.
Forma i warunki zaliczenia zajęć:
  • Konwersatorium Laboratorium komputerowe - praca samodzielna w domu nad rozwiązaniami. Prezentowanie rozwiązań w trakcie ćwiczeń. Praca nad niektórymi zadaniami w trakcie zajęć pod kierunkiem prowadzącego. Ocena na podstawie aktywności na zajęciach i ocen z kolokwiów
  • Wykład Egzamin pisemny Możliwość zdawania egzaminu w języku angielskim.
Wykaz literatury podstawowej:
  • Cormen Leiserson, Rivest - "Wstęp do Algorytmów"
  • N. Wirth, Algorytmy + Struktury Danych = Programy
C. Juszczak © 2010-2013 - Wydział Fizyki i Astronomii, Uniwersytet Wrocławski