Drukuj Eksport do pliku (MS Word)
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:
7 / rok ak. 2015/2016
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 godziny, 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 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 2015/2016. 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_K03, Tr1A_K04
Powiązane efekty obszarowe: T1A_K03, T1A_K04