Algorytmy i struktury danych

obowiązkowe

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

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.

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

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.

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.

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

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.

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

6. Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie programowania, algorytmów i złożoności, architektury systemów komputerowych, systemów operacyjnych, technologii sieciowych, języków i paradygmatów programowania, baz danych, inżynierii oprogramowania (K_W02).

7. Zna podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i rządź, programowanie z nawrotami, poprawność, metoda niezmienników, złożoność obliczeniowa) (K_W04).

8. Zna podstawowe struktury danych i wykonywane na nich operacje (reprezentacja danych liczbowych, arytmetyka i błędy zaokrągleń, tablice, napisy, zbiory, rekordy, pliki, wskaźniki i referencje, struktury wskaźnikowe, listy, stosy, kolejki, drzewa i grafy)

Umiejętności

1. Potrafi projektować, analizować pod kątem poprawności i złożoności obliczeniowej oraz programować algorytmy; wykorzystywać podstawowe techniki algorytmiczne i struktury danych (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ń.

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.

4. Potrafi praktycznie implementować zaprojektowane przez siebie algorytmy z wykorzystaniem bibliotek algorytmicznych.

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

6. Potrafi samodzielnie pozyskiwać i wykorzystywać zgodnie z prawem informację na temat algorytmów i struktur danych i ich implementacji.

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

8. Potrafi zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań o średnim poziomie złożoności (K_U01).

9. Potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02).

10. Samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09).

Kompetencje społeczne

1. Student jest gotów do krytycznej oceny posiadanej wiedzy i odbieranych treści (K_K01).

2. Student jest gotów do pracy z zachowaniem uczciwości intelektualnej w działaniach własnych i innych osób; przestrzegania zasad etyki zawodowej i wymagania tego od innych oraz dbałości o dorobek i tradycje zawodu informatyka (K_K02).

3. Student jest gotów do uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03).

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.