- Nazwa przedmiotu:
- Podstawy algorytmiki
- Koordynator przedmiotu:
- dr hab. 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. 2020/2021
- 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..30 pytań i przeprowadzanego na komputerze. Pytania obejmują każdy z efektów kształcenia w zakresie wiedzy. W celu uzyskania oceny pozytywnej należy udzielić > 50% poprawnych odpowiedzi dla każdego z efektów kształcenia. 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, 2006
2) C.S. Horstmann. Java. Podstawy. Wydanie XI, Helion, 2019
- Witryna www przedmiotu:
- https://epw.pw.edu.pl
- Uwagi:
- Przedmiot z uchwalonego przez Radę Wydziału wykazu dodatkowych przedmiotów obieralnych na rok akademicki 2019/2020.
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
- Charakterystyka W01
- Zna elementarne struktury danych oraz ich zastosowanie
Weryfikacja: Indywidualne zadanie zaliczeniowe na kolokwium wykonywane na komputerze, wymagane jest uzyskanie co najmniej 50% wartości punktów przypisanych do danego efektu
Powiązane charakterystyki kierunkowe:
Tr1A_W06
Powiązane charakterystyki obszarowe:
I.P6S_WG
- Charakterystyka W02
- Zna podstawowe metody algorytmiczne
Weryfikacja: Komputerowy test składający się z pytań zamkniętych, wymagana jest poprawna odpowiedź na co najmniej 50% z liczby pytań odnoszących się do danego efektu
Powiązane charakterystyki kierunkowe:
Tr1A_W06
Powiązane charakterystyki obszarowe:
I.P6S_WG
- Charakterystyka W03
- Zna metody oceny złożoności algorytmu oraz obliczenia jego kosztów
Weryfikacja: Komputerowy test składający się z pytań zamkniętych, wymagana jest poprawna odpowiedź na co najmniej 50% z liczby pytań odnoszących się do danego efektu
Powiązane charakterystyki kierunkowe:
Tr1A_W06
Powiązane charakterystyki obszarowe:
I.P6S_WG
Profil ogólnoakademicki - kompetencje społeczne
- Charakterystyka K01
- Jest gotów do krytycznej oceny odbieranych treści i własnej wiedzy. Umie identyfikować i rozstrzygać problemy związane z realizacją określonego przez siebie lub innych zadania z wykorzystaniem odpowiednich algorytmów
Weryfikacja: Ocena aktywności podczas zajęć - wymagane jest rozwiązanie co najmniej jednego zadania podczas zajęć praktycznych
Powiązane charakterystyki kierunkowe:
Tr1A_K01
Powiązane charakterystyki obszarowe:
I.P6S_KK