Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych
Koordynator przedmiotu:
__
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Geoinformatyka
Grupa przedmiotów:
Obowiązkowe
Kod przedmiotu:
1060-GI000-ISP-1006
Semestr nominalny:
1 / rok ak. 2015/2016
Liczba punktów ECTS:
2
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Udział w zajęciach, wykłady: 15 godzin, Udział w zajęciach, ćwiczenia: 15 godzin, Zapoznanie z literaturą: 6 godzin, Sprawozdania, raporty z zajęć, prace domowe: 10 godzin, Przygotowanie do kolokwium: 12 godzin, Udział w konsultacjach: 2 godziny
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1,1 punktu ECTS: Udział w zajęciach, wykłady: 15 godzin, Udział w zajęciach, ćwiczenia: 15 godzin, Udział w konsultacjach: 2 godziny
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
0,9 punktu ECTS: Udział w zajęciach, ćwiczenia: 15 godzin, Sprawozdania, raporty z zajęć, prace domowe: 10 godzin, Udział w konsultacjach: 2 godziny
Formy zajęć i ich wymiar w semestrze:
  • Wykład15h
  • Ćwiczenia15h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Limit liczby studentów:
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z podstawowymi algorytmami scalania, sortowania i wyszukiwania stosowanymi w informatyce. W ramach przedmiotu przekazana jest wiedza o różnych technikach projektowania algorytmów (np. "dziel i zwyciężaj"), sposobach wyznaczania ich złożoności oraz ugruntowana umiejętność formułowania algorytmów w języku programowania.
Treści kształcenia:
1. Podstawowe pojęcia: sposoby opisu algorytmów, schematy blokowe, techniki tworzenia algorytmów, rekurencja, dziel i zwyciężaj 2. Analiza algorytmów: poprawność algorytmów, złożoność obliczeniowa 3. Podstawowe struktury danych 4. Algorytmy wyszukiwania i scalania 5. Elementarne metody sortowania: przez selekcję, wstawianie 6. Quick sort 7. Sortowanie przez scalanie 8. Sortowanie przez kopcowanie 9. Wyszukiwanie i drzewa binarne 10. Zrównoważone drzewa binarne 11. Tablice hashujące 12. Wyszukiwanie danych przestrzennych
Metody oceny:
Ocena z wykładu: 2 kolokwia, czas trwania około 30 minut; progi zaliczenia: 2 [0%-50%], 3 [50%-60%], 3.5 [60%-70%], 4 [70%-80%], 4.5 [80%-90%], 5 [90%-100%]; możliwość poprawienia obu kolokwiów w sesji - jeden termin poprawkowy; krótkie kartkówki z ostatniego wykładu - dodatkowe punkty na kolokwium, sumarycznie 10%; ocena końcowa: średnia z obu kolokwiów z zaokrągleniem w górę. Ocena z ćwiczeń: ćwiczenia samodzielne z analizy i implementacji algorytmów; poprawne rozwiązanie ćwiczenia: ocena 3, jakość kodu programu lub raportu: oceny 4 i 5; oddanie ćwiczenia po terminie: -0.5 oceny za każdy rozpoczęty tydzień; brak ćwiczenia: ocena 2; ocena końcowa to średnia ważona z oddanych ćwiczeń z zaokrągleniem w górę.
Egzamin:
nie
Literatura:
"Algorytmy, struktury danych i techniki programowania", Wydanie IV, Piotr Wróblewski, Helion; "Algorytmy", Robert Sedgewick, Wydanie IV, Kevin Weyne, Helion; "Wprowadzenie do algorytmów", Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwo Naukowe PWN
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się

Profil praktyczny - wiedza

Efekt GI.ISP-1006_W01
zna podstawowe pojęcia i techniki dotyczące projektowania i analizy algorytmów stosowanych w informatyce, rozumie zasadę działania rekurencji oraz techniki „dziel i rządź”
Weryfikacja: Kolokwium
Powiązane efekty kierunkowe: K_W04
Powiązane efekty obszarowe: T1P_W03, T1P_W04, T1P_W06
Efekt GI.ISP-1006_W02
zna złożoność czasową podstawowych algorytmów sortowania i wyszukiwania z uwzględnieniem przypadków szczególnych
Weryfikacja: Kolokwium
Powiązane efekty kierunkowe: K_W04
Powiązane efekty obszarowe: T1P_W03, T1P_W04, T1P_W06
Efekt GI.ISP-1006_W03
zna podstawowe struktury danych oraz przykłady algorytmów, które je wykorzystują
Weryfikacja: Kolokwium
Powiązane efekty kierunkowe: K_W04
Powiązane efekty obszarowe: T1P_W03, T1P_W04, T1P_W06

Profil praktyczny - umiejętności

Efekt GI.ISP-1006_U01
potrafi oszacować złożoność obliczeniową prostego algorytmu
Weryfikacja: Kolokwium
Powiązane efekty kierunkowe: K_U01
Powiązane efekty obszarowe: T1P_U01, T1P_U13
Efekt GI.ISP-1006_U02
potrafi formułować algorytmy w języku programowania i dobierać odpowiednie struktury danych
Weryfikacja: Ćwiczenia - implementacja programów wykorzystujących poznane zagadnienia teoretyczne
Powiązane efekty kierunkowe: K_U01, K_U02, K_U15
Powiązane efekty obszarowe: T1P_U01, T1P_U13, T1P_U02, T1P_U12, T1P_U09, T1P_U14, T1P_U15, T1P_U16, T1P_U18
Efekt GI.ISP-1006_U03
potrafi zastosować wybrane algorytmy w zakresie sortowania i wyszukiwania do rozwiązania bardziej złożonych problemów programistycznych
Weryfikacja: Ćwiczenia - implementacja programów wykorzystujących poznane zagadnienia teoretyczne
Powiązane efekty kierunkowe: K_U01, K_U02, K_U15
Powiązane efekty obszarowe: T1P_U01, T1P_U13, T1P_U02, T1P_U12, T1P_U09, T1P_U14, T1P_U15, T1P_U16, T1P_U18

Profil praktyczny - kompetencje społeczne

Efekt GI.ISP-1006_K01
potrafi uzupełniać i doskonalić nabytą wiedzę i umiejętności z zakresu struktur danych i algorytmów operujących na tych strukturach
Weryfikacja: Kolokwium, ćwiczenia
Powiązane efekty kierunkowe: K_K01
Powiązane efekty obszarowe: T1P_K01
Efekt GI.ISP-1006_K02
potrafi przeanalizować problem, wybrać i przedyskutować odpowiednią metodę rozwiązania
Weryfikacja: Kolokwium, ćwiczenia
Powiązane efekty kierunkowe: K_K04
Powiązane efekty obszarowe: T1P_K03, T1P_K04