Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych
Koordynator przedmiotu:
dr Anna M. Radzikowska
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
3 / rok ak. 2011/2012
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Podstawy programowania (znajomość języka C).
Limit liczby studentów:
Cel przedmiotu:
Zapoznanie studentów z podstawowymi algorytmami (sortowanie, wybór,  algorytmy grafowe) i strukturami danych (listy, drzewa, reprezentacja grafów)  oraz metodologią analizy algorytmów.
Treści kształcenia:
1. Systematyzacja podstawowych struktur danych: lista, drzewo, kopiec, kolejka, stos, graf. 2. Podstawy analizy algorytmów: poprawność algorytmu, metoda niezmienników dowodzenia ich poprawności, złożoność algorytmów. 3. Problem sortowania; algorytmy elementarne sortowania, algorytm sortowania szybkiego, algorytm sortowania przez kopcowanie, sieci sortowania, analiza tych algorytmów. 4. Problem selekcji: drzewa turniejowe i algorytm Hadiana-Sobela, algorytm Hoore’a, algorytm selekcji liniowej, analiza tych algorytmów. 5. Struktury listowe i drzewiaste: listy, drzewa poszukiwań binarnych, drzewa AVL, B-drzewa, drzewa Patricia; zastosowanie omówionych struktur danych w konstrukcji algorytmów spełniających określone warunki czasowe/pamięciowe. 6. Metody wyszukiwania w zbiorze nieuporządkowanym: funkcje mieszające i metody usuwania kolizji 7. Metody reprezentacji grafów i podstawowe algorytmy grafowe (metody przeszukiwania grafu, algorytmy wyznaczania cykli Hamiltona i Eulera, metody znajdowania najkrótszych ścieżek) .
Metody oceny:
Obecność na ćwiczeniach jest obowiązkowa, dopuszczalne są maksimum 2 nieusprawiedliwione nieobecności na zajęciach. W trakcie semestru student może uzyskać 30 punktów z 2 prac kontrolnych oraz punkty za aktywność na ćwiczeniach. W ostatnim tygodniu semestru przewidziane jest 1 kolokwium poprawkowe. Dla dopuszczenie do egzaminu  wymagane jest uzyskanie min. 15 punktów. Egzamin obejmuje część pisemną i ustną. Za część pisemną można uzyskać max. 30 punktów. Ocena ostateczna z przedmiotu jest łączną oceną uzyskaną na ćwiczeniach i na egzaminie. 
Egzamin:
Literatura:
1. Banachowski L.,Diks K.,Rytter W.: Algorytmy i struktury danych, Wydawnictwo Naukowo-Techniczne, Warszawa 1996. 2. Banachowski L., Kreczmar A.: Elementy analizy algorytmów, Wydawnictwo Naukowo-Techniczne, Warszawa 1982. 3. Cormen T.H., Leiserson C.E., Rivest R.L.: Wprowadzenie do algorytmów, Wydawnictwo Naukowo-Techniczne, Warszawa 1998. 4. Sedgewick R.: Algorithms in C.
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się