Politechnika
Warszawska

Katalog
ECTS

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-0231

Semestr nominalny:

3 / rok ak. 2022/2023

Liczba punktów ECTS:

5

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

1. godziny kontaktowe – 68 h w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 30 h c) konsultacje – 5 h d) obecność na egzaminie – 3 h 2. praca własna studenta – 60 godz., w tym a) przygotowanie się do ćwiczeń – 15 h b) przygotowanie się do kolokwiów – 30 h c) przygotowanie się do egzaminu – 15 h Razem 128 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. 4. obecność na egzaminie – 3 h Razem 68 h, co odpowiada 3 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 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:

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:

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: K_K02
Powiązane charakterystyki obszarowe: