- Nazwa przedmiotu:
- Algorytmy i struktury danych 1
- Koordynator przedmiotu:
- Dr inż. Paweł Kotowski
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Informatyka i Systemy Informacyjne
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- 1120-IN000-ISP-0021
- Semestr nominalny:
- 3 / rok ak. 2018/2019
- Liczba punktów ECTS:
- 5
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 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 1 – strukturalne
- Limit liczby studentów:
- Ćwiczenia – 30 os. /grupa
- 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, Algotytmy w C++, Wydawnictwo RM, 1999
- Witryna www przedmiotu:
- e.mini.pw.edu.pl
- 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:
K_W04, K_W08
Powiązane charakterystyki obszarowe:
- 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:
K_W10
Powiązane charakterystyki obszarowe:
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:
K_U11, K_U23
Powiązane charakterystyki obszarowe:
- Charakterystyka U02
- Potrafi ocenić złożoność obliczeniową algorytmów
Weryfikacja: ocena z kolokwiów, ocena z egzaminu
Powiązane charakterystyki kierunkowe:
K_U14
Powiązane charakterystyki obszarowe:
- 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:
K_U04
Powiązane charakterystyki obszarowe: