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:
7 / 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 30 godz., zapoznanie się ze wskazaną literaturą 10 godz., konsultacje 3 godz., przygotowanie się do egzaminu 15 godz., udział w egzaminach 2 godz.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1,5 pkt ECTS (35 godzin, w tym: praca na wykładach 30 godz., konsultacje 3 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:
http://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: 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 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ęć - wymagana jest co najmniej jedna poprawna odpowiedź na pytania kontrolne
Powiązane charakterystyki kierunkowe: Tr1A_K01
Powiązane charakterystyki obszarowe: I.P6S_KK