Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych
Koordynator przedmiotu:
dr Anna M. Radzikowska
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-MA000-LSP-0231
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 – 83 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 30 h c) obecność na laboratoriach – 15 h d) obecność na egzaminie – 3 h e) konsultacje – 5 h 2. praca własna studenta – 50 h; w tym a) przygotowanie do ćwiczeń i do kolokwiów – 15 h b) przygotowanie do zajęć laboratoryjnych – 15 h b) zapoznanie się z literaturą – 10 h c) przygotowanie do egzaminu – 10 h Razem 133 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 h 2. obecność na ćwiczeniach – 30 h 3. obecność na laboratoriach – 15 h 4. obecność na egzaminie – 3 h 4. konsultacje – 5 h Razem 83 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:
1. obecność na laboratoriach – 15 h 2. przygotowanie do zajęć laboratoryjnych – 15 h Razem 30 h, co odpowiada 1 pkt. ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Przedmioty poprzedzające: - Programowanie - Matematyka dyskretna Wymagania wstępne: - Znajomość programowania strukturalnego i obiektowego, umiejętność programowania w języku C i C++ (ewentualnie C#) - Znajomość podstaw matematyki dyskretnej, w szczególności teorii grafów, kombinatoryki, równań rekurencyjnych.
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z podstawami algorytmiki oraz metodami analizy programów pod względem ich poprawności i złożoność obliczeniowej.
Treści kształcenia:
1. Wprowadzenie do algorytmiki, podstawowe struktury danych. 2. Metody analizy złożoności obliczeniowej (czasowej, pamięciowej) algorytmów. 3. Sortowanie: a. Algorytmy sortowanie wewnętrzne: sortowanie szybkie, sortowanie przez kopcowanie, sortowanie przez scalanie, elementarne algorytmy sortowania (sortowanie przez wybór, sortowanie przez wstawianie, sortowanie przez binarne wstawki, sortowanie bąbelkowe). b. Sortowanie plików. 4. Selekcja: algorytm Hoare’a, algorytm Hadiana-Sobela, algorytm ‘’magicznych piątek”. 5. Struktury słownikowe a. Rozwiązania listowe. b. Drzewa: drzewa wyszukiwani binarnych (BST), zrównoważone drzewa BST (drzewa AVL), optymalne drzewa BST, B-drzewa, drzewa PATRICIA. 6. Metody haszowania. 7. Grafy: a. Metody reprezentacji grafów i digrafów b. Metody obchodzenia grafów (DFS, BFS) c. Algorytm Dijkstry znajdowania najkrótszych ścieżek z danego wierzchołka d. Algorytm Robertsa-Foresa wyznaczania cykli Hamiltona. e. Problem mostów królewieckich. 8. Algorytmy z nawracaniem (problem komiwojażera, problemy szachowe i optymalizacyjne, problemy kliki i kolorowania grafu)
Metody oceny:
Ćwiczenia (40p): • 2 kolokwia (20p i 10p) • aktywność na zajęciach 10p. Do zaliczenia ćwiczeń wymagane jest uzyskanie min. 21p. Laboratoria (20p) obejmują 6 zadań ocenianych i 1 zadanie nieoceniane. Z zadań ocenianych: cztery oceniane są na 3p oraz dwa na 4p. Do zaliczenia laboratoriów wymagane jest uzyskanie min. 11p. Egzamin obejmuje część pisemną i część ustną. Egzamin pisemny (40p), w tym • 10 pytań testu wielokrotnego wyboru (20p) • 2 zadania problemowe po 10p każde. Do części pisemnej przystępuje student, który uzyskał zaliczenia ćwiczeń i zaliczenie laboratoriów. Jeśli student uzyskał z ćwiczeń min. 30p i min.11p z laboratoriów, to może być zwolniony z części pisemnej egzaminu z oceną wejściową na egzamin ustny: od 41p – 3,0; od 45p – 4,0; od 50p – 4,5; od 55p – 5,0. Osoby, które przystąpiły do egzaminu pisemnego, otrzymują oceną łączną za egzamin pisemny, ćwiczenia i laboratoria wynikającą z sumarycznej liczby punktów: od 51p – 3,0; od 61p – 3,5; od 71p – 4,0; od 81p – 4,5; od 91p – 5,0. Studenci, którzy po egzaminie pisemnym uzyskali ocenę min. 4,0 mogą być zwolnieni z egzaminu ustnego – wówczas ocena z przedmiotu jest uzyskaną dotąd oceną. Egzamin ustny zdaje student, który: • odpowiedział prawidłowo na min. 2 spośród 3 wylosowanych pytań • prawidłowo rozwiązał wylosowany problem. Studenci, którzy nie uzyskali zwolnienia z egzaminu ustnego (bądź zrezygnowali z możliwości zwolnienia) uzyskują ocenę łączną z przedmiotu: • 75% oceny uzyskanej na podstawie ćwiczeń, laboratoriów i/lub egzaminu pisemnego • 25% oceny uzyskanej z egzaminu ustnego.
Egzamin:
tak
Literatura:
1. L. Banachowski, K. Diks, W. Rytter: Algorytmy I Struktury Danych. Wydawnictwo Naukowo-Techniczne, 1996. 2. A. A. Aho, J. E. Hopcroft, J. D. Ullman: Projektowanie i analiza algorytmów. Wydawnictwo HELION, 2003. 3. A. A. Aho, J. E. Hopcroft, J. D. Ullman: Algorytmy I Struktury Danych. Wydawnictwo HELION, 2003. 4. T. C. Cormen, C. E. Leiserson, R. R. Rivest, C. Stein: Wprowadzenie do algorytmów. Wydawnictwo Naukowo PWN, 2013. 5. R. Sedgewick: Algorytmy w C++. Oficyna Wydawnicza README, 1999.
Witryna www przedmiotu:
e.mini.pw.edu.pl
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt ASD_W01
Ma wiedzę w zakresie podstaw algorytmiki: • podstawowe struktury danych: stosy, kolejki, kopce, słowniki (listy, drzewa BST, AVL, PATRICIA, B-drzewa). • podstawowe techniki programowania i ich zastosowania: metoda „dziel i zwyciężaj”, metoda zachłanna, programowanie dynamiczne, metody z nawracaniem • algorytmy sortowania (wewnętrznego, plików) • algorytmy selekcji • wybrane algorytmy grafowe • podstawowe metody haszowania.
Weryfikacja: • Kolokwia, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_W16
Powiązane efekty obszarowe: X1A_W01, X1A_W03, X1A_W04
Efekt ASD_W02
Ma wiedzę w zakresie podstaw programowania, w tym programowania deklaratywnego i obiektowego. Zna podstawowe metody teoretyczne analizy algorytmów w zakresie semantycznej poprawności oraz czasowe i pamięciowej złożoności obliczeniowej.
Weryfikacja: • Kolokwia, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_W15
Powiązane efekty obszarowe: X1A_W01, X1A_W04, X1A_W05

Profil ogólnoakademicki - umiejętności

Efekt ASD_U1
Potrafi w sposób zrozumiały, przedstawić poprawne rozumowanie matematyczne, formułować twierdzenia i definicje, posługuje się rachunkiem zdań i kwantyfikatorów, językiem teorii mnogości, indukcją matematyczną, rekurencją.
Weryfikacja: • Kolokwia, • Zadania laboratoryjne, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_U09
Powiązane efekty obszarowe: X1A_U01, X1A_U02
Efekt ASD_U02
Potrafi analizować poprawność prostych algorytmów oraz ich złożoność czasową i pamięciową oraz testować (debugging) zaimplementowany przez siebie kod źródłowy.
Weryfikacja: • Kolokwia, • Zadania laboratoryjne, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_U16
Powiązane efekty obszarowe: X1A_U01, X1A_U04
Efekt ASD_U03
Potrafi formułować w postaci pseudokodu rozwiązania prostych problemów algorytmicznych (w szczególności zagadnień dot. działań na tablicach i macierzach) oraz je implementować, używając wybranego deklaratywnego języka programowania.
Weryfikacja: • Kolokwia, • Zadania laboratoryjne, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_U16
Powiązane efekty obszarowe: X1A_U01, X1A_U04

Profil ogólnoakademicki - kompetencje społeczne

Efekt ASD_K01
Rozumie potrzebę uczenia się przez całe życie.
Weryfikacja: • Kolokwia, • Zadania laboratoryjne, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_KS01
Powiązane efekty obszarowe: X1A_K01
Efekt ASD_K02
Potrafi współdziałać i pracować w grupie, przyjmując w niej różne role
Weryfikacja: • Kolokwia, • Zadania laboratoryjne, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_KS02
Powiązane efekty obszarowe: X1A_K02
Efekt ASD_K03
Rozumie potrzebę podnoszenia kompetencji zawodowych i osobistych.
Weryfikacja: • Kolokwia, • Zadania laboratoryjne, • Egzamin (pisemny, ustny), • Udział w dyskusjach, odpowiedzi ustne, aktywność na ćwiczeniach.
Powiązane efekty kierunkowe: ML_KS03
Powiązane efekty obszarowe: X1A_K03