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. 2020/2021
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. Złożoność obliczeniowa algorytmów: czasowa i pamięciowa, rząd funkcji, notacja O() 3. Podstawowe struktury danych: tablica, lista 4. Abstrakcyjne struktury danych: kolejka, stos, tablica asocjacyjna, kolejka priorytetowa 5. Algorytmy wyszukiwania i scalania 6. Elementarne metody sortowania: bąbelkowe, przez wybieranie, przez wstawianie 7. Sortowanie Shella, Sortowanie szybkie, Sortowanie przez scalanie 8. Sortowanie stabilne, tablica częściowo posortowana, sortowanie hybrydowe, sortowanie systemowe 9. Drzewa poszukiwań binarnych, operacje na drzewach 10 Równoważenie drzew poszukiwań binarnych, drzewa samoorganizujące się 11. Tablice haszujące 12. Tablica asocjacyjna
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. 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. 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