Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 1000-213bASD Kod Erasmus / ISCED: 11.302 / (0612) Database and network design and administration
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obowiązkowe dla II roku informatyki
Przedmioty obowiązkowe dla III roku JSIM - wariant 3I+4M
Przedmioty obowiązkowe dla III roku JSIM - wariant 3M+4I
Punkty ECTS i inne: 7.00
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Wymagania (lista przedmiotów):

Matematyka dyskretna 1000-212bMD
Wstęp do programowania (podejście funkcyjne) 1000-211bWPF
Wstęp do programowania (podejście imperatywne) 1000-211bWPI

Skrócony opis:

Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. Doskonalenie praktycznych umiejętnosci w projektowaniu i programowaniu poprawnych i wydajnych algorytmow oraz w posługiwaniu się gotowymi bibliotekami algorytmów i struktur danych.

Pełny opis:

Podstawowe zasady analizy algorytmów

Metody projektowania wydajnych algorytmów

Sortowanie

Selekcja

Kolejki priorytetowe

Wyszukiwanie i słowniki

Problem "Find-Union" i jego zastosowania

Algorytmy grafowe

Wyszukiwanie wzorca w tekstach

Tekstowe struktury danych

Literatura:

L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo - Techniczne, 2006.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, PWN, 2012.

Efekty kształcenia:

Wiedza

1. Ma uporządkowaną, podbudowaną matematycznie wiedzę z zakresu metod projektowania wydajnych algorytmów i struktur danych oraz ich analizowania pod katem poprawności i złożoności obliczeniowej. (K_W01, K_W02, K_W04)

2. Zna i charakteryzuje pod kątem złożoności i zastosowań najważniejsze algorytmy sortowania, selekcji, wyszukiwania, tekstowe i grafowe. (K_W02, K_W04)

3. Ma wiedzę na temat podstawowych abstrakcyjnych struktur danych (listy, stosy, kolejki, słowniki, kolejki priorytetowe, zbiory, zbiory rozłączne, teksty, grafy) i ich wydajnych implementacji. (K_W02, K_W04, K_W05)

4. Zna biblioteki algorytmów i struktur danych. (K_W09)

5. Ma podstawową wiedzę dotyczącą własności intelektualnej związanej z wykorzystywaniem i modyfikowaniem dostępnych algorytmów i struktur danych. (K_W12)

Umiejętności

1. Potrafi projektować wydajne algorytmy i analizować je pod kątem złożoności obliczeniowej. (K_U01, K_U07)

2. Rozróżnia pojęcia złożoności obliczeniowej problemu od złożoności obliczeniowej algorytmu oraz potrafi oceniać trudności obliczeniowe problemów algorytmicznych i algorytmów. Rozumie znaczenie modelu obliczeń. (K_U01,K_U07)

3. Potrafi właściwie dobrać i zastosować metody projektowania algorytmów oraz znane algorytmy i struktury danych w projektowanych przez siebie rozwiązaniach problemów algorytmicznych. (K_U02, K_U06, K_U07)

4. Potrafi praktycznie implementować zaprojektowane przez siebie algorytmy z wykorzystaniem bibliotek algorytmicznych. (K_U05, K_U09, K_U22, K_U23, K_U25, K_U28)

5. Potrafi testować swoje programy pod kątem złożoności obliczeniowej (K_U25)

6. Potrafi samodzielnie pozyskiwać i wykorzystywać zgodnie z prawem informację na temat algorytmów i struktur danych i ich implementacji. (K_U02, K_U04, K_U30).

7. Potrafi zaprezentować zaprojektowane przez siebie algorytmy i struktury danych w sposób zrozumiały przez innych. (K_U04, K_U29)

Kompetencje

1. Zna ograniczenia własnej wiedzy algorytmicznej i rozumie potrzebę ciągłego dokształcania. (K_K01)

2. Rozumie potrzebę systematycznej pracy i dotrzymywania terminów wykonywanych zadań. (K_K02, K_K05)

3. Rozumie i docenia znaczenie uczciwości intelektualnej w zakresie korzystania z cudzego oprogramowania. Zachowuje się etycznie podczas realizacji projektów algorytmicznych. (K_K03)

4. Samodzielnie potrafić odnaleźć i wykorzystać różnego rodzaju informacje dotyczące algorytmiki, także w językach obcych. (K_K04)

Metody i kryteria oceniania:

Na końcową ocenę składają się oceny cząstkowe za pracę podczas laboratoriów i ćwiczeń oraz za egzamin. Laboratorium polega na zrealizowaniu szeregu projektów programistycznych, których celem jest zaprojektowanie i zaimplementowanie wydajnych algorytmów dla wybranych problemów algorytmicznych. Na ćwiczeniach projektuje się i analizuje teoretycznie algorytmy i struktury danych pod kątem ich złożoności obliczeniowej. Wiedza i umiejętności zdobywane na ćwiczeniach są weryfikowane podczas dwóch klasówek. Osoby z zaliczonym laboratorium i ćwiczeniami przystępują do egzaminu, który składa się z trzech części: praktycznej - weryfikującej praktyczne umiejętności projektowania i implementowania wydajnych algorytmów, testowej - sprawdzającej encyklopedyczną wiedzę podaną na wykładzie oraz zadaniowej - weryfikującą umiejętności zastosowania wiedzy podanej na wykładzie i ćwiczeniach.

Szczegółowe zasady oceniania są podawane studentom z każdą edycją przedmiotu.

Zajęcia w cyklu "Semestr zimowy 2017/18" (w trakcie)

Okres: 2017-10-01 - 2018-01-26
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Krzysztof Diks
Prowadzący grup: Krzysztof Ciebiera, Krzysztof Diks, Małgorzata Gałązka, Mirosław Kowaluk, Adam Malinowski, Paweł Parys, Juliusz Straszyński, Łukasz Sznuk, Tomasz Waleń, Wiktor Zuba, Anna Zych-Pawlewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.