Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych
Koordynator przedmiotu:
dr inż. Jacek Bernard 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. 2021/2022
Liczba punktów ECTS:
2
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
50 godzin, w tym: 1) Liczba godzin kontaktowych: 32 godziny: a) udział w zajęciach, wykłady: 15 godzin, b) udział w zajęciach, ćwiczenia: 15 godzin, c) uczestnictwo konsultacjach: 2 godziny. 2) Praca własna studenta: 18 godzin: a) prace domowe, ćwiczenia programistyczne, sprawozdania: 10 godzin, b) zapoznanie się z literaturą: 2 godziny, c) przygotowanie do kolokwium: 6 godzin.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
32 godziny = 1,28 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:
27 godzin = 1,08 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:
Znajomość matematyki na poziomie szkoły średniej
Limit liczby studentów:
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z podstawowymi algorytmami stosowanymi w informatyce, w tym sortowania i wyszukiwania. 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 obliczeniowej oraz ugruntowana umiejętność formułowania algorytmów w języku programowania.
Treści kształcenia:
Wykład: 1. Podstawowe pojęcia: sposoby opisu algorytmów, schematy blokowe, techniki tworzenia algorytmów, przykłady algorytmów iteracyjnych i rekurencyjnych 2. Technika dziel i zwyciężaj, wyszukiwanie binarne 3. Złożoność obliczeniowa algorytmów: czasowa i pamięciowa; pesymistyczna, optymistyczna i oczekiwana 4. Notacja O(), przykładowe złożoności obliczeniowe algorytmów 5. Podstawowe struktury danych: zmienne, wskaźniki, rekordy, tablice i listy 6. Abstrakcyjne struktury danych: kolejka, stos i kolejka priorytetowa 7. Algorytm wyszukiwania i scalania 8. Elementarne metody sortowania: bąbelkowe, przez wybieranie, przez wstawianie 9. Sortowanie Shella, sortowanie przez scalanie rekurencyjne i wstępujące 10. Sortowanie szybkie, sortowanie szybkie z trójpodziałem 11. Sortowanie rekordów, sortowanie stabilne, tablica częściowo posortowana, sortowanie hybrydowe, sortowanie systemowe 12. Drzewa poszukiwań binarnych, operacje na drzewach 13. Równoważenie drzew poszukiwań binarnych – algorytm DSW, drzewa samoorganizujące się: splay, AVL i czerwono-czarne, tablice haszujące, tablica asocjacyjna   Ćwiczenia: 1. Analiza algorytmów poznanych na wykładzie 2. Testy algorytmów dla różnych rodzajów danych wejściowych 3. Empiryczna analiza złożoności obliczeniowej algorytmów 4. Samodzielna implementacja 4 zadań algorytmicznych
Metody oceny:
Ocena z wykładu: - 2 kolokwia, do zdobycia 100 punktów (2x50). - Progi ocen: 2 [0-50], 3 [50-60], 3.5 [60-70], 4 [70-80], 4.5 [80-90], 5 [90-100]. - Warunek otrzymania pozytywnej oceny - minimum 20pkt z każdego kolokwium oraz suma minimum 50pkt. - Możliwość poprawienia obu kolokwiów - jeden termin poprawkowy. Ocena z ćwiczeń: - 5 zadań do samodzielnego wykonania: 4 problemu algorytmiczne oraz 1 zadanie dotyczące analizy empirycznej algorytmów. - Oceniana jest 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 zdobycia 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 uzyskanie pozytywnych ocen z wykładu i z ćwiczeń.
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