Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych (E)
Koordynator przedmiotu:
Jan OGRODZKI
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Telekomunikacja
Grupa przedmiotów:
Przedmioty techniczne
Kod przedmiotu:
AISDE
Semestr nominalny:
3 / rok ak. 2012/2013
Liczba punktów ECTS:
3
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
80
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
  • Ćwiczenia0h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Matematyka w zakresie wykładanym na sem 1,2 studiów I stopnia na WEiTI. Podstawy programowania w zakresie jak wyżej.
Limit liczby studentów:
120
Cel przedmiotu:
- ukształtowanie zrozumienia tego, że dobór algorytmu do rozwiązania konkretnego problemu powinien uwzględniać zarówno ocenę poprawności semantycznej jak i złożoności obliczeniowej - zapoznanie z najefektywniejszymi obliczeniowo algorytmami do rozwiązywania takich problemów jak: sortowanie, wyszukiwanie wzorca, przetwarzanie słowników, analiza właściwości grafów - ukształtowanie podstawowych umiejętności w zakresie analitycznej i komputerowej analizy złożoności czasowej pesymistycznej, optymistycznej i oczekiwanej algorytmów oraz w zakresie doboru algorytmów do problemów pod kątem minimalizacji tych złożoności
Treści kształcenia:
-problemy abstrakcyjne, teoria algorytmów, złożoność obliczeniowa - wybrane algorytmy teorio-liczbowe - algorytmy rekurencyjne i iteracyjne - sortowanie przez wstawianie, selekcję, scalanie, szybkie, metoda liczników częstości i pozycyjne - implementacja i przetwarzanie słowników: tablice nieuporządkowane, tablice uporządkowane, drzewa binarne, tablice indeksowane kluczem, tablice z mieszaniem - algorytmy grafowe: przeszukiwanie wszerz, przeszukiwanie w głąb, poszukiwanie minimalnych ścieżek, badanie cykliczności, spójności, silnej spójności, minimalne ścieżki w grafach ważonych
Metody oceny:
- ocena sumatywna wiedzy i umiejętności wykazanych w pisemnej kartkówce przed zajęciami laboratoryjnymi (bez korzystania z notatek) - ocena sumatywna wiedzy i umiejętności wykazanych w sprawozdaniu z zajęć laboratoryjnych wykonanego podczas zajęć (z pomocą notatek, podręczników i biblioteki oprogramowania) - ocena sumatywna wiedzy i umiejętności wykazanych na kolokwium i egzaminie pisemnym (bez korzystania z notatek) - ocena formatywna przed kolokwium i egzaminem na podstawie rozmów podczas konsultacji
Egzamin:
tak
Literatura:
T.Adamski, J.Ogrodzki, Wprowadzenie do algorytmów komputerowych i struktur danych, Oficyna Wydawnicza PW, Warszawa, 2005 T.Adamski, J.Ogrodzki, K. Opalska, Zbiór zadań z algorytmów komputerowych i struktur danych, Oficyna Wydawnicza PW, Warszawa, 2011 T.H. Cormen, C.E.Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa, 1997
Witryna www przedmiotu:
www.studia.elka.pw.edu.pl/priv/12L/AISDE.C
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt W1
Student, który zaliczył przedmiot potrafi podać definicje takich pojęć z zakresu teorii algorytmów jak: problem abstrakcyjny, algorytm, złożoność czasowa, złożoność pamięciowa, złożoność pesymistyczna, optymistyczna, oczekiwana, klasa złożoności, oszacowanie asymptotyczne złożoności, iteracja, rekurencja, drzewo rekurencji, równanie rekurencyjne, drzewo równania rekurencyjnego oraz przykłady tych pojęć.
Weryfikacja: Kolokwium, kartkówki przed laboratorium
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:

Profil ogólnoakademicki - umiejętności

Efekt U1
Wykonać analizę analityczną złożoności algorytmów omawianych na wykładzie i pokrewnych, porównać je pod kątem złożoności i wybrać algorytmy najefektywniejsze w klasie danych
Weryfikacja: Kolokwium, egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt U2
Wykonać analizę komputerową złożoności algorytmów omawianych na wykładzie i pokrewnych oraz porównać te algorytmy pod jej kątem
Weryfikacja: Sprawozdanie z laboratorium
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt U3
Zilustrować zasadę działania algorytmu wypisując jego wyniki pośrednie po kolejnych etapach dla przykładowych danych
Weryfikacja: Kolokwium, kartkówki przed laboratorium, egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe: