Algorytmy i struktury danych 0800-ALGOSD

1. Algorytmy a struktury danych - uwagi ogólne.
2. Dynamiczne struktury danych: Listy, stosy, kolejki, kolejki priorytetowe, listy cykliczne, listy dwukierunkowe, wartownik. Budowa struktur i algorytmów operujące na różnych typach list.
3. Drzewa, drzewa binarne, drzewa przeszukiwań (z porządkiem), dwukierunkowe. Sposoby wykorzystywania struktur drzewiastych.
4. Grafy, sposoby reprezentacji, terminologia. Podstawowe sposoby manipulacji na grafach.
5. Definicje złożoności i sposoby jej wyznaczania.
6. Uwagi o typach algorytmów.
7. Algorytmy sortowania:
- Analiza algorytmów sortowania O(n^2)
- Analiza algorytmów sortowania O(n log n)
- Analiza algorytmów sortowania O(n)
8. Statystyki pozycyjne
9. Metody mnożenia macierzy
10. Programowanie dynamiczne
11. Problem mnożenia ciągu macierzy
12. Algorytm wyznaczania najdłuższego wspólnego podciągu
13. Algorytm triangulacji wielokąta
14. Algorytmy przeszukiwania grafów
15. Sortowanie topologiczne
16. Algorytmy wyznaczania minimalnych drzew rozpinających
17. Algorytmy wyznaczania najkrótszych ścieżek w grafach:
- Elementy wspólne algorytmów
- Algorytm Dijkstry
- Algorytm Bellmana-Forda
- Algorytm Floyda-Warshalla
18. Analiza i algorytmy drzew zbalansowanych na przykładzie drzew czerwono-czarnych.

Całkowity nakład pracy studenta

30H - wykład 30H - ćwiczenia 30H - laboratorium 135H - praca indywidualna

Efekty uczenia się - wiedza

Posiada wiedzę o szeregu podstawowych algorytmów w informatyce. Zna metody analizowania działania algorytmu. Posiada wiedzę o metodach oceny złożoności algorytmów. Posiada wiedzę o różnych struktura danych i potrafi jej używać. Zna podstawy teorii grafów. Zna różne sposoby konstrukcji algorytmów. W 4, 6, 10,

Efekty uczenia się - umiejętności

Potrafi implementować algorytmy i struktury danych. Umie dokonać analizy algorytmu. Umie znajdować błędy w programach Potrafi oszacować złożoność obliczeniową. Potrafi używać instrumentów matematyki do analizy algorytmów. Potrafi wykorzystać wiedzę z teorii grafów. Umie stworzyć nowe programy z wykorzystanie poznanych algorytmów lub opracować nowy algorytm. Umie używać narzędzi programistycznych. Potrafi dokonać analizy ekonomicznej dotyczącej czasu realizacji zadań informatycznych, a także związanych z tym kosztów. U 1, 2, 8, 13, 21

Efekty uczenia się - kompetencje społeczne

ma świadomość skutków wadliwie działających systemów informatycznych, które mogą doprowadzić do strat moralnych i finansowych, a nawet utraty zdrowia czy zagrożenia życia uznaje fundamentalne znaczenie wiedzy dla ludzkości, potrafi krytycznie ocenić posiadaną wiedzę oraz zna jej ograniczenia K 1, 6

Metody dydaktyczne

Wykład: prezentacja materiału i problemów, dyskusja Ćwiczenia: omawianie zagadnień i ich analiza, wspólne i indywidualne rozwiązywanie zadań. Analiza przypadków. Częściowo praca grupowa. Laboratoria: Nacisk na indywidualne rozwiązywanie problemów + pomoc eksperta. Dyskusja nad przykładami rozwiązań.

Metody dydaktyczne eksponujące

- symulacyjna (gier symulacyjnych)
- pokaz

Metody dydaktyczne podające

- wykład informacyjny (konwencjonalny)
- wykład problemowy
- pogadanka

Metody dydaktyczne poszukujące

- laboratoryjna
- klasyczna metoda problemowa
- projektu
- doświadczeń
- sytuacyjna
- studium przypadku
- giełda pomysłów
- ćwiczeniowa
- punktowana
- obserwacji

Metody dydaktyczne w kształceniu online

- metody ewaluacyjne
- metody wymiany i dyskusji
- metody rozwijające refleksyjne myślenie
- metody odnoszące się do autentycznych lub fikcyjnych sytuacji

Rodzaj przedmiotu

przedmiot obligatoryjny

Wymagania wstępne

Analiza matematyczna, Algebra, Matematyka dyskretna, Języki programowania, Programowanie strukturalne

Koordynatorzy przedmiotu

Norbert Jankowski

Kryteria oceniania

1. Bieżąca praca.
2. Kolokwia pisemne.
3. Zadania bieżące (listy zadań i programów).
4. Wejściówki (w zależności od potrzeb).
5. Zadania laboratoryjne
6. Egzamin pisemny.
Powyższe metody oceny weryfikują zakres programu jak i efekty kształcenia opisane powyżej.

Aby przystąpić do egzaminu trzeba mieć zdane ćwiczenia i laboratorium.

Szczegółowy sposób oceny laboratorium jest w dokumencie dotyczącym listy zadań. Tam też są określone ścisłe progi ocen.

Zaliczenie kolokwium:
minimum 50%, poniżej 2.0, od 50% (3.0) ocena skalowana liniowo do 5.0
Zaliczenie ćwiczeń:
średnia z kolokwiów pod warunkiem zaliczenia każdego z kolokwiów i zaliczenia wejściówek.

Ocena egzaminu:
minimum 50%, poniżej 2.0, od 50% (3.0) ocena skalowana liniowo do 5.0

W pracy bieżącej, na kolokwiach, na laboratoriach i egzaminie weryfikuje się wszystkie efekty uczenia się: wiedzy, umiejętności i kompetencje społeczne.

Literatura

A. V. Aho, J. E. Hopcroft, J. D. Ullman. Projektowanie i analiza algorytmów. Helion, Warszawa, 2003.
A. V. Aho, J. E. Hopcroft, J. D. Ullman. Projektowanie i analiza algorytmów. Państwowe Wydawnictwa Naukowe, Warszawa, 1983.
Niklaus Wirth. Algorytmy + Struktury Danych = Programy. Wydawnictwa Naukowo-Techniczne, Warszawa, wydanie 2, 1989.
T. H. Cormen, C. E. Leiserson, R. L Rivest. Wprowadzenie do algorytmów. Wydawnictwa Naukowo-Techniczne, Warszawa, 1997.
L. Banachowski, K. Diks, W. Rytter. Algorytmy i struktury danych. Wydawnictwa Naukowo-Techniczne, Warszawa, 1996.

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 0800-ALGOSD w USOSweb