Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych 1
Koordynator przedmiotu:
Dr inż. Paweł Kotowski
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Inżynieria i Analiza Danych
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0231
Semestr nominalny:
3 / rok ak. 2020/2021
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe – 65 godz. w tym a) obecność na wykładach – 30 godz. b) obecność na ćwiczeniach – 30 godz. c) konsultacje – 5 godz. 2. praca własna studenta – 80 godz., w tym a) przygotowanie się do ćwiczeń – 15 godz. b) przygotowanie się do kolokwiów – 40 godz. c) przygotowanie się do egzaminu i obecność na egzaminie – 25 godz. Razem 135 h, co odpowiada 5 pkt. ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1. obecność na wykładach – 30 godz. 2. obecność na ćwiczeniach – 30 godz. 3. konsultacje – 5 godz. Razem 65 h, co odpowiada 2 pkt. ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
.
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Programowanie obiektowe
Limit liczby studentów:
.
Cel przedmiotu:
Celem przedmiotu jest uzyskanie wiedzy na temat podstawowych struktur danych oraz metod projektowania i oceny efektywnych algorytmów komputerowych. Po ukończeniu kursu studenci powinni posiadać praktyczne umiejętności opracowywania oraz oceny efektywnych algorytmów, wykorzystujących proste i złożone struktury danych.
Treści kształcenia:
Wprowadzenie. Podstawowe struktury danych. Poprawność, złożoność i metody projektowania algorytmów. Kolejki priorytetowe. Kopiec i dwukopiec, Kopce złączalne. Kolejki dwumianowe, Kopce Fibonacciego. Słowniki. Wyszukiwanie w tablicach. Drzewa wyszukiwań BST, AVL, drzewa czerwono-czarne, optymalne, samoorganizujące się. B‑drzewa, 2-3 i 2-3-4 drzewa. Wyszukiwanie pozycyjne. Kodowanie mieszające. Algorytmy UNION-FIND. Reprezentacja listowa. Reprezentacja drzewiasta. Sortowanie. Sortowanie wewnętrzne przez porównania. Sortowanie pozycyjne. Sortowanie przez zliczanie. Sortowanie zewnętrzne. Zadanie wyboru.
Metody oceny:
Na ocenę końcową wpływają: 2 kolokwia semestralne (2x20 pkt), egzamin końcowy (40 pkt) i egzamin ustny. Warunkiem koniecznym dopuszczenia do egzaminu pisemnego jest uzyskanie min 10 pkt. z każdego kolokwium. Warunkiem koniecznym dopuszczenia do egzaminu ustnego jest uzyskanie min. 20 pkt. z egzaminu pisemnego. Istnieje możliwość zwolnienia z egzaminu pisemnego w przypadku uzyskania z ćwiczeń 35 pkt.
Egzamin:
tak
Literatura:
1. A.V. Aho, J.E. Hopcroft, J.D.Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, 1983. 2. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 1997. 3. R. Sedgevick, Algorytmy w C++, Wydawnictwo RM, 1999.
Witryna www przedmiotu:
.
Uwagi:
.

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01
Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną i szczegółową w zakresie podstawowych struktur danych oraz algorytmów
Weryfikacja: ocena z kolokwiów, ocena z egzaminu
Powiązane charakterystyki kierunkowe: DS_W08
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka W02
Zna podstawowe metody, techniki i narzędzia stosowane do analizy złożoności obliczeniowej algorytmów
Weryfikacja: ocena z kolokwiów, ocena z egzaminu
Powiązane charakterystyki kierunkowe: DS_W08
Powiązane charakterystyki obszarowe: I.P6S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka U01
Ma umiejętność formułowania algorytmów i ich programowania z użyciem przynajmniej jednego z popularnych narzędzi
Weryfikacja: ocena z kolokwiów, ocena z egzaminu
Powiązane charakterystyki kierunkowe: DS_U25
Powiązane charakterystyki obszarowe: I.P6S_UW
Charakterystyka U02
Potrafi ocenić złożoność obliczeniową algorytmów
Weryfikacja: ocena z kolokwiów, ocena z egzaminu
Powiązane charakterystyki kierunkowe: DS_U14
Powiązane charakterystyki obszarowe: I.P6S_UW
Charakterystyka U03
Potrafi zidentyfikować i wykorzystać dyskretne struktury danych do analizy i rozwiązywania problemów
Weryfikacja: ocena z kolokwiów, ocena z egzaminu
Powiązane charakterystyki kierunkowe: DS_U13
Powiązane charakterystyki obszarowe: I.P6S_UW

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K01
Rozumie znaczenie wiedzy matematycznej w opisie procesów, tworzeniu modeli, zapisie algorytmów i innych działaniach w obszarze informatyki oraz potrzebę zasięgania opinii ekspertów
Weryfikacja: ocena z kolokwiów, ocena z egzaminu
Powiązane charakterystyki kierunkowe:
Powiązane charakterystyki obszarowe: