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:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0021
Semestr nominalny:
3 / rok ak. 2015/2016
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 – 85 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 – 30 godz. Razem 150 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 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 kom-puterowych. Po ukończeniu kursu studenci powinni posiadać praktyczne umiejętności opracowywania oraz oceny efektywnych algorytmów, wyko-rzystują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 dwu-mianowe, 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 pozy-cyjne. 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 egza-minu 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

Efekt 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 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: ocena z kolokwiów, ocena z egzaminu
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: ocena z kolokwiów, ocena z egzaminu
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: ocena z kolokwiów, ocena z egzaminu
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: ocena z kolokwiów, ocena z egzaminu
Powiązane efekty kierunkowe: K_U04
Powiązane efekty obszarowe: T1A_U09