- Nazwa przedmiotu:
- Algorytmy i struktury danych I
- Koordynator przedmiotu:
- dr inż. Paweł Kotowski
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Informatyka
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- Semestr nominalny:
- 3 / rok ak. 2012/2013
- Liczba punktów ECTS:
- 6
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 1. godziny kontaktowe - 60 godz. w tym
a. obecność na wykładach – 30 godz.
b. obecność na ćwiczeniach– 30 godz.
2. przygotowanie do zajęć –90 godz., w tym
a. konsultacje – 5 godz.
b. przygotowanie się do ćwiczeń – 15 godz.
c. przygotowanie się do kolokwiów – 40 godz.
d. Przygotowanie się do egzaminu i obecność na egzaminie – 30 godz.
Razem nakład pracy studenta 150 godz. = 6 pkt. ECTS
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 1. obecność na wykładach i ćwiczeniach – 60 godz.
2. konsultacje– 5 godz.
Razem 65 godz., 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:
- Podstawy programowania
- Limit liczby studentów:
- Bez limitu
- 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:
- 1. Wprowadzenie
Podstawowe struktury danych
Poprawność, złożoność i metody projektowania algorytmów
2. Sortowanie
Sortowanie wewnętrzne przez porównania, sortowanie pozycyjne
Sortowanie przez zliczanie
Sortowanie zewnętrzne
Zadanie wyboru
3. Wyszukiwanie
Wyszukiwanie w tablicach
Drzewa wyszukiwań BST, AVL optymalne, samoorganizujące się
Wyszukiwanie pozycyjne
Drzewa Bayera, 2-3 i 2-3-4 drzewa
Kodowanie mieszające
4. Kolejki priorytetowe
Kopce złączalne
Kolejki dwumianowe
5. Algorytmy UNION-FIND
Reprezentacja listowa
Reprezentacja drzewiasta
- Metody oceny:
- Na ocenę końcową wpływają:
2 kolokwia semestralne (2x20 pkt)
egzamin końcowy (40pkt)
egzamin ustny
Warunkiem koniecznym dopuszczenia do egzaminu ustnego jest uzyskanie 40 pkt.
Istnieje możliwość zwolnienia z egzaminu pisemnego w przypadku uzyskania z ćwiczeń 35 pkt.
- Egzamin:
- tak
- Literatura:
- A.V. Aho, J.E. Hopcroft, J.D.Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, 1983.
L.Banachowski, K.Diks, W.Rytter, Algorytmy i struktury danych, WNT, 1997
R Sedgevick, Algotytmy w C++, Wydawnictwo RM, 1999
- Witryna www przedmiotu:
- brak
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt W01
- Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną i szczegółową w zakresie podstawowych struktur danych oraz algorytmów
Weryfikacja: Kolokwium Egzamin
Powiązane efekty kierunkowe:
K_W04, K_W08
Powiązane efekty obszarowe:
T1A_W03, T1A_W04
- Efekt W02
- Zna podstawowe metody, techniki i narzędzia stosowane do analizy złożoności obliczeniowej algorytmów
Weryfikacja: Kolokwium Egzamin
Powiązane efekty kierunkowe:
K_W10
Powiązane efekty obszarowe:
T1A_W07
Profil ogólnoakademicki - umiejętności
- Efekt U01
- Ma umiejętność formułowania algorytmów i ich programowania z użyciem przynajmniej jednego z popularnych narzędzi
Weryfikacja: Kolokwium Egzamin
Powiązane efekty kierunkowe:
K_U11, K_U23
Powiązane efekty obszarowe:
T1A_U09, T1A_U14, T1A_U15, T1A_U09, T1A_U16
- Efekt U02
- Potrafi ocenić złożoność obliczeniową algorytmów
Weryfikacja: Kolokwium Egzamin
Powiązane efekty kierunkowe:
K_U14
Powiązane efekty obszarowe:
T1A_U09, T1A_U15
- Efekt U03
- Potrafi zidentyfikować i wykorzystać dyskretne struktury danych do analizy i rozwiązywania problemów
Weryfikacja: Kolokwium Egzamin
Powiązane efekty kierunkowe:
K_U04
Powiązane efekty obszarowe:
T1A_U09