Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych
Koordynator przedmiotu:
Jacek Marciniak
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. 2019/2020
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, złożoność obliczeniowa 3. Podstawowe struktury danych: tablica, lista, drzewo binarne 4. Abstrakcyjne struktury danych: kolejka, stos, tablica asocjacyjna, kolejka priorytetowa 5. Algorytmy wyszukiwania i scalania 6. Elementarne metody sortowania: bąbelkowe, przez selekcję, przez wstawianie 7. Sortowanie szybkie 8. Sortowanie przez scalanie 9. Sortowanie przez kopcowanie 10. Wyszukiwanie i drzewa binarne 11. Zrównoważone drzewa binarne 12. Tablice haszujące
Metody oceny:
Ocena z wykładu - 2 kolokwia, do zdobycia 50 punktów z każdego. - Progi zaliczenia: 2 [0-50pkt], 3 [50-60pkt], 3.5 [60-70pkt], 4 [70-80pkt], 4.5 [80-90pkt], 5 [90-100pkt]. - Warunek otrzymania pozytywnej oceny - minimum 20pkt z każdego kolokwium i sumy 50pkt z obu. - Możliwość poprawienia obu kolokwiów - jeden termin poprawkowy. - Krótkie kartkówki z ostatniego wykładu - dodatkowe 5 punktów na każde kolokwium. Ocena z ćwiczeń - Ćwiczenia samodzielne z analizy i implementacji algorytmów. - Oceniana poprawność rozwiązania, wybór odpowiednich algorytmów oraz jakość kodu programu lub raportu. - Ćwiczenia oceniane są w skali punktowej. Liczba punktów do zdobycia zależy od złożoności ćwiczenia. - Maksymalnie do zdobycie 100 punktów. - Ocena końcowa według takich samych kryteriów jak dla wykładu. - Każdy dzień spóźnienia obniża maksymalną wartość punktową ćwiczenia. Ocena końcowa z przedmiotu: - Ocena oparta o średnią wartość punktów z wykładów i ćwiczeń według kryteriów oceny jak dla wykładu - Warunkiem uzyskania oceny pozytywnej jest zaliczenie wykładu i ćwiczeń na oceny pozytywne
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

Charakterystyka 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 charakterystyki kierunkowe: K_W04
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka 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 charakterystyki kierunkowe: K_W04
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka GI.ISP-1006_W03
zna podstawowe struktury danych oraz przykłady algorytmów, które je wykorzystują
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: K_W04
Powiązane charakterystyki obszarowe: I.P6S_WG

Profil praktyczny - umiejętności

Charakterystyka GI.ISP-1006_U01
potrafi oszacować złożoność obliczeniową prostego algorytmu
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: K_U01
Powiązane charakterystyki obszarowe: I.P6S_UW
Charakterystyka 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 charakterystyki kierunkowe: K_U01, K_U02, K_U15
Powiązane charakterystyki obszarowe: I.P6S_UW, I.P6S_UO
Charakterystyka 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 charakterystyki kierunkowe: K_U01, K_U02, K_U15
Powiązane charakterystyki obszarowe: I.P6S_UW, I.P6S_UO

Profil praktyczny - kompetencje społeczne

Charakterystyka 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 charakterystyki kierunkowe: K_K01
Powiązane charakterystyki obszarowe: I.P6S_KK
Charakterystyka GI.ISP-1006_K02
potrafi przeanalizować problem, wybrać i przedyskutować odpowiednią metodę rozwiązania
Weryfikacja: Kolokwium, ćwiczenia
Powiązane charakterystyki kierunkowe: K_K04
Powiązane charakterystyki obszarowe: I.P6S_KO, I.P6S_KR