Algorytmy II

Algorytmy i struktury danych, Języki programowania. Programowanie obiektowe.

Wykład: 30H

ćwiczenia: 15H

Laboratoria: 45H

Praca indywidualna: 100H

Zaawansowana znajomość i umiejętność wykorzystania ważnych algorytmów.

Pogłębiona analiza złożoności algorytmów.

Umiejętność wybory algorytmu do problemu i struktur danych.

Elementy pracy zespołowej.

Wiedza o zaawansowanych struktura danych i algorytmach.

Posługiwanie się językami programistycznymi.

W 1, 2, 5

Umiejętność zaawansowanej analizy algorytmu.

Umiejętność wykorzystania algorytmów.

Umiejętność oceny złożoności algorytmów.

Umiejętność podziału problemu na podproblemy.

Umiejętność implementacji zaawansowanych algorytmów i struktur danych.

Umiejętność posługiwania się złożonymi strukturami danych

U 5, 7

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

K 2

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

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

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

- metody integracyjne
- metody odnoszące się do autentycznych lub fikcyjnych sytuacji
- metody oparte na współpracy
- metody rozwijające refleksyjne myślenie
- metody wymiany i dyskusji

Jest to cykl zajęć (wykład, ćwiczenia i laboratorium) poświęcone bardziej zaawansowanej części algorytmów ale także struktur danych.

Poruszane są też ważne aspekty związane ze złożonością obliczeniową.

Na zagadnienia wykładu, ćwiczeń i laboratoriów składają się:

1. Algorytmy z powrotami

a. Problem skoczka szachowego

b. Problem ośmiu hetmanów

c. Ogólny algorytm z powrotami

d. Wieże Hanoi, permutacje, kombinacje (z/bez powtórzeń)

2. Problemy plecakowe (ciągłe i dyskretne)

3. Algorytmy i struktury danych dla operacji zbiorowych

a. Algorytmy i struktury naiwne

b. Haszowanie (zbiory i słowniki)

c. Drzewa zrównoważone

d. Listy z dowiązaniami

e. Problem Unio-Find

4. Silnie spójne składowe grafu

5. Cykle Eulera i Hamiltona

6. Problem maksymalnego przepływu

7. Klasy złożoności

8. Kopce Fibonacciego

9. Automaty i wyrażenia regularne

10. Wyszukiwanie wzorców

a. Algorytm naiwny

b. Algorytmy szybkie, automaty

c. Drzewa sufiksowe

11. Problem spełnialności reguł logicznych

12. Geometria obliczeniowa - podstawy

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.

A. V. Aho, J. D. Ullman.

Wykłady z informatyki z przykładami w języku C.

Helion, Warszawa, 2003.

L. Banachowski, K. Diks, W. Rytter.

Algorytmy i struktury danych.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1996.

M. M. Sysło, N. Deo, J. Kowalik.

Algorytmy optymalizacji dyskretnej.

Państwowe Wydawnictwa Naukowe, Warszawa, 1993.

D. Harel.

Rzecz o istocie informatyki. Algorytmika.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1992.

L. Banachowski, A. Kreczmar, W. Rytter.

Analiza algorytmów i struktur danych.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1989.

L. Banachowski, A. Kreczmar.

Elementy analizy algorytmów.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1982.

D. E. Knuth.

Sztuka Programowania, wolumen I–III.

Wydawnictwa Naukowo–Techniczne, 2002.

1. Bieżąca praca. W 1, 2, 5, U 5, 7, K 2

2. Kolokwia pisemne. W 1, 2, 5, U 5, 7, K 2

3. Zadania bieżące (listy zadań i programów). W 1, 2, 5, U 5, 7, K 2

4. Wejściówki (w zależności od potrzeb). W 1, 2, 5, U 5, 7, K 2

5. Egzamin pisemny lub zadania koncepcyjne. W 1, 2, 5, U 5, 7, K 2

Powyższe metody oceny weryfikują zakres programu jak i efekty kształcenia opisane powyżej.

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

Ocena ćwiczeń jest składową oceny kolokwium (podstawa oceny), pracy bieżącej, i innych dodatkowych zadań.

W przypadku egzaminu poprzez zadania koncepcyjne ocena jest średnią oceny wykonanych zadań egzaminacyjnych (które muszą być zrobione), oceny z ćwiczeń i laboratorium.

Ocena laboratorium: minimalnie trzeba wykonać około 80% zadań (zależne od bieżącej listy zadań), zadania są oceniane na podstawie jakości realizacji poszczególnych zadań. Ocena jest średnią ocen poszczególnych zadań. W przypadku braku rozwiązania wszystkich zadań ocena jest pomniejszana: 1% wszystkich zadań = 0.1 oceny (np. brak 10% zadań = ocena o 1.0 w dół).

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