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:
M1ASD
Semestr nominalny:
3 / rok ak. 2012/2013
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba godzin: 160 Podana liczba godzin obejmuje: uczestnictwo studenta w zajęciach (wykład 30h, ćwiczenia 30h, laboratoria 15h, konsultacje 5h) – 80 godzin. praca samodzielna: zapoznanie się z materiałem przedstawionym na zajęciach oraz zalecaną literaturą, rozwiązanie zalecanych zadań, przygotowanie wstępnych kodów niezbędnych w zajęciach laboratoryjnych, przygotowanie do sprawdzianów i egzaminu – 80 godzin.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
3
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1 (laboratoria 15h, przygotowania do laboratoriów 15h)
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Przedmiotu poprzedzające: Podstawy programowania Matematyka dyskretna. Wymagania wstępne: Biegła znajomość podstaw programowania, umiejętność programowania w języku wysokiego poziomu (np., C++, C#) Znajomość podstaw matematyki dyskretnej, w szczególności teorii grafów, równań rekurencyjnych, funkcji tworzących.
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Zapoznanie studentów z podstawowymi technikami programowania, popularnymi algorytmami i strukturami danych o istotnym znaczeniu w zastosowaniach praktycznych, oraz metodami analizy algorytmów pod względem ich poprawności i złożoności.
Treści kształcenia:
Podstawy analizy algorytmów: ich semantyczna poprawność i złożoność obliczeniowa (czasowa i pamięciowa). Podstawowe techniki programowania: rekursja, metoda „dziel i zwyciężaj”, metoda zachłanna, programowanie dynamiczne, zastępowanie rekursji algorytmami iteracyjnymi przy wykorzystaniu struktury stosu. Problem porządkowania: algorytmy sortowania wewnętrznego (algorytm sortowania szybkiego, algorytm sortowania przez kopcowanie, elementarne algorytmy sortowania), algorytmy sortowania plików, analiza tych algorytmów. Problem selekcji: algorytm Hadiana–Sobela, algorytm Hoore’a, algorytm selekcji liniowej, analiza tych algorytmów. Struktury słownikowe: listy, drzewa poszukiwań binarnych, drzewa AVL, B–drzewa, drzewa Patricia; ich zastosowania. Metody wyszukiwania w zbiorze nieuporządkowanym: funkcje mieszające i metody usuwania kolizji Metody reprezentacji grafów i podstawowe algorytmy grafowe (metody przeszukiwania grafu, algorytmy wyznaczania cykli, 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:
tak
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:
brak
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt ASD_W_01
Ma wiedzę w zakresie podstaw algorytmiki: podstawowe struktury danych: stosy, kolejki, kopce, słowniki (listy, drzewa BST, AVL, PATRICIA, B-drzewa). podstawowe techniki programowania i ich zastosowania: metoda „dziel i zwyciężaj”, metoda zachłanna, programowanie dynamiczne, metody z nawracaniem algorytmy sortowania (wewnętrznego, zewnętrznego) algorytmy selekcji podstawowe metody haszowania. wybrane algorytmy grafowe.
Weryfikacja: Sprawdziany pisemne, Egzamin (część pisemna I ustna)
Powiązane efekty kierunkowe: ML_W16
Powiązane efekty obszarowe: X1A_W01, X1A_W03, X1A_W04
Efekt ASD_W_02
Zna podstawowe metody teoretycznej analizy algorytmów w zakresie semantycznej poprawności oraz czasowej i pamięciowej złożoności obliczeniowej.
Weryfikacja: Sprawdziany pisemne, Egzamin (część pisemna I ustna)
Powiązane efekty kierunkowe: ML_W15
Powiązane efekty obszarowe: X1A_W01, X1A_W04, X1A_W05
Efekt ASD_W_03
Zna i rozumie pojęcia z zakresu relacji porządku (częściowego, liniowego), grafów i ich typów i własności, równań rekurencyjnych.
Weryfikacja: Sprawdziany pisemne, Egzamin (część pisemna I ustna)
Powiązane efekty kierunkowe: ML_W09
Powiązane efekty obszarowe: X1A_W01, X1A_W03

Profil ogólnoakademicki - umiejętności

Efekt ASD_U1
Potrafi przedstawić poprawne rozumowanie matematyczne i powiązać wybrane problemy matematyczne (rachunek zdań, indukcja matematyczna, rekurencja) dla potrzeb rozwiązania i analizy problemu algorytmicznego.
Weryfikacja: Sprawdziany pisemne, Egzamin (część pisemna I ustna)
Powiązane efekty kierunkowe: ML_U09
Powiązane efekty obszarowe: X1A_U01, X1A_U02
Efekt ASD_U_02
Posiada umiejętność analizy algorytmu w zakresie semantycznej poprawności złożoności obliczeniowej (czasowej i pamięciowej).
Weryfikacja: Sprawdziany pisemne, Egzamin (część pisemna I ustna)
Powiązane efekty kierunkowe: ML_U16
Powiązane efekty obszarowe: X1A_U01, X1A_U04
Efekt ASD_U_03
Potrafi samodzielnie zapisać w pseudokodzie rozwiązanie prostych problemów algorytmicznych i je zaimplementować w języku programowania. wykorzystać dostępne klasy, struktury, funkcje dla rozwiązania prostych problemów algorytmicznych.
Weryfikacja: LABORATORIUM (ZALICZENIE)
Powiązane efekty kierunkowe: ML_U16
Powiązane efekty obszarowe: X1A_U01, X1A_U04

Profil ogólnoakademicki - kompetencje społeczne

Efekt ASD_KS_01
Rozumie potrzebę uczenia się przez całe życie
Weryfikacja: EGZAMIN
Powiązane efekty kierunkowe: ML_KS01
Powiązane efekty obszarowe: X1A_K01
Efekt ASD_KS_02
Potrafi współdziałać i pracować w grupie, przyjmując w niej różne role.
Weryfikacja: ĆWICZENIA
Powiązane efekty kierunkowe: ML_KS02
Powiązane efekty obszarowe: X1A_K02
Efekt ASD_KS_03
Rozumie potrzebę podnoszenia kompetencji zawodowych i osobistych
Weryfikacja: WYKŁAD, ĆWICZENIA
Powiązane efekty kierunkowe: ML_KS03
Powiązane efekty obszarowe: X1A_K03