- Nazwa przedmiotu:
- Podstawy algorytmiki
- Koordynator przedmiotu:
- dr inż. Andrzej Czerepicki, Wydział Transportu Politechniki Warszawskiej, Zakład Systemów Informatycznych i Mechatronicznych w Transporcie
- Status przedmiotu:
- Fakultatywny ograniczonego wyboru
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Transport
- Grupa przedmiotów:
- Obieralne
- Kod przedmiotu:
- Semestr nominalny:
- 8 / rok ak. 2017/2018
- Liczba punktów ECTS:
- 2
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 60 godzin, w tym: praca na wykładach 18 godz., studiowanie literatury przedmiotu 18 godz., konsultacje 2 godz., udział w egzaminach 2 godz., przygotowanie się do egzaminu z wykładu 20 godz.
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 1,0 pkt ECTS (22 godz., w tym: praca na wykładach 18 godz., konsultacje 2 godz., udział w egzaminach 2 godz.)
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 0
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia0h
- Laboratorium0h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Brak
- Limit liczby studentów:
- Brak
- Cel przedmiotu:
- Zapoznanie studentów z podstawowymi strukturami danych oraz bazowymi algorytmami operującymi na tych strukturach. Nabycie wiedzy praktycznej z zakresu implementacji często używanych algorytmów z wykorzystaniem wybranego języka programowania. Oszacowanie kosztów pamięciowych oraz czasowych rozwiązania zadania z wykorzystaniem wybranego algorytmu. Dobór najlepszego algorytmu rozwiązującego sformułowany problem oraz jego uzasadnienie.
- Treści kształcenia:
- Wstęp do algorytmów. Podstawowe zasady analizy algorytmów: poprawność, złożoność obliczeniowa algorytmu, koszt algorytmu. Elementarne struktury danych: stosy, kolejki, listy. Podstawowe techniki i struktury: metoda dziel i zwyciężaj, metoda zachłanna, programowanie dynamiczne, iteracja, rekurencja. Algorytmy sortowania: algorytm bąbelkowy, sortowanie zaawansowane. Złożoność problemu sortowania. Algorytmy wyszukiwania: wyszukiwanie liniowe i binarne. Wyszukiwanie zaawansowane. Drzewa poszukiwań binarnych, haszowanie. Złożoność algorytmów wyszukiwania. Drzewa. Drzewa AVI oraz binarne. Realizacja oraz złożoność algorytmów wykorzystujących drzewa. Grafy. Rodzaje grafów oraz metody ich reprezentacji w komputerze. Algorytmy grafowe: problem wyszukiwania ścieżki, algorytm Dijkstry. Algorytmy grafowe w transporcie. Algorytmy tekstowe: problem wyszukiwania wzorca w tekście, algorytm K-M-P. Tekstowe struktury danych. Słowniki i drzewa sufiksowe. NP-zupełność. Pojęcie NP. Problemy NP-trudne oraz NP-zupełne, oraz ich zastosowanie w rozwiązywaniu problemów logistycznych.
- Metody oceny:
- Egzamin odbywa się w postaci testu zamkniętego składającego się z 15 pytań i przeprowadzanego na komputerze. Każde pytanie posiada tylko jedną poprawną odpowiedź. Ocena końcowa zależy od liczby poprawnych odpowiedzi wg skali: 5.0 (>90%), 4.5 (>80%), 4.0 (>70%), 3.5 (>60%), 3.0 (>50%), 2.0 (<50%)
- Egzamin:
- tak
- Literatura:
- 1) L.Banachowski, K.Dicks, W.Rytter, „Algorytmy i struktury danych”, WNT, 2001
2) Piotr Wróblewski, „Algorytmy, struktury danych i techniki programowania”, Helion, 1997
3) R.Neapolitan, K.Naimipour, „Podstawy algorytmów z przykładami w C++”, Helion, 2004
- Witryna www przedmiotu:
- http://www.simt.wt.pw.edu.pl/dydaktyka/
- Uwagi:
- Przedmiot z uchwalonego przez Radę Wydziału wykazu dodatkowych przedmiotów obieralnych na rok akademicki 2017/2018.
O ile nie powoduje to zmian w zakresie powiązań danego modułu zajęć z kierunkowymi efektami kształcenia w treściach kształcenia mogą być wprowadzane na bieżąco zmiany związane z uwzględnieniem najnowszych osiągnięć naukowych.
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt W01
- Zna elementarne struktury danych oraz ich zastosowanie
Weryfikacja: Zaliczenie w postaci testu na komputerze
Powiązane efekty kierunkowe:
Tr1A_W06
Powiązane efekty obszarowe:
T1A_W02, InzA_W05
- Efekt W02
- Zna podstawowe metody algorytmiczne
Weryfikacja: Zaliczenie w postaci testu na komputerze
Powiązane efekty kierunkowe:
Tr1A_W06
Powiązane efekty obszarowe:
T1A_W02, InzA_W05
- Efekt W03
- Zna metody oceny złożoności algorytmu oraz obliczenia jego kosztów
Weryfikacja: Zaliczenie w postaci testu na komputerze
Powiązane efekty kierunkowe:
Tr1A_W06
Powiązane efekty obszarowe:
T1A_W02, InzA_W05
Profil ogólnoakademicki - umiejętności
- Efekt U01
- Potrafi dobrać strukturę danych właściwą do postawionego zadania
Weryfikacja: Zaliczenie w postaci testu na komputerze
Powiązane efekty kierunkowe:
Tr1A_U01
Powiązane efekty obszarowe:
T1A_U01
- Efekt U02
- Potrafi wykorzystać wybraną strukturę w algorytmie
Weryfikacja: Zaliczenie w postaci testu na komputerze
Powiązane efekty kierunkowe:
Tr1A_U11
Powiązane efekty obszarowe:
T1A_U09, InzA_U02
- Efekt U03
- Potrafi przeanalizować działanie algorytmu
Weryfikacja: Zaliczenie w postaci testu na komputerze
Powiązane efekty kierunkowe:
Tr1A_U11
Powiązane efekty obszarowe:
T1A_U09, InzA_U02
Profil ogólnoakademicki - kompetencje społeczne
- Efekt K01
- Rozumie rolę algorytmiki w rozwiązywaniu współczesnych problemów w transporcie oraz potrzebę podnoszenia swoich kwalifikacji w tym obszarze informatyki
Weryfikacja:
Powiązane efekty kierunkowe:
Tr1A_K01
Powiązane efekty obszarowe:
T1A_K01
- Efekt K02
- Potrafi wykorzystać zdobytą wiedzę do zespołowego rozwiązania problemów informatycznych w transporcie
Weryfikacja:
Powiązane efekty kierunkowe:
Tr1A_K04, Tr1A_K03
Powiązane efekty obszarowe:
T1A_K04, T1A_K03