Algorytmy i struktury danych

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

przedmiot obligatoryjny

30H - wykład

30H - ćwiczenia

30H - laboratorium

135H - praca indywidualna

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,

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

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

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ń.

- pokaz
- symulacyjna (gier symulacyjnych)

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

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

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

Przedmiot omawia szereg zagadnień dotyczących różnych sposobów reprezentacji danych, konstrukcji algorytmów i analizę wybranych algorytmów. Prezentowane są także zagadnienia związane ze złożonością obliczeniową i ich analizą.

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.

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.

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.