| Przedmiot: |
Algorytmy i struktury danych I |
| Kierunek: |
Informatyka, I stopień [6 sem], stacjonarny, ogólnoakademicki, rozpoczęty w: 2013 |
| Rok/Semestr: |
II/3
|
| Liczba godzin: |
30,0 |
| Nauczyciel: |
Krzaczkowski Jacek, dr |
| Forma zajęć: |
laboratorium |
| Rodzaj zaliczenia: |
zaliczenie na ocenę |
| Poziom trudności: |
średnio zaawansowany
|
| Wstępne wymagania: |
Umiejętność programowania.
|
| Metody dydaktyczne: |
- ćwiczenia laboratoryjne
- dyskusja dydaktyczna
- e-learning
- warsztaty grupowe
- z użyciem komputera
|
| Zakres tematów: |
-
Podstawy teorii złożoności obliczeniowej(maszyna Turinga, notacje O i Ω,operacje dominujące).
-
Przeszukiwanie zbioru potencjalnych rozwiązań (backtracking,generowanie wszystkich permutacji etc).
-
Listy (listy w tablicach, listy wskaźnikowe).
-
Proste algorytmy sortujące (sortowanie przez wstawianie, sortowanie przez wybór, sortowanie bąbelkowe, szacowanie złożoności tych algorytmów).
-
Metoda ,,dziel i zwyciężaj'': mergesort, quicksort, wyszukiwanie binarne, bisekcja.
-
Abstrakcyjne struktury danych: kolejka, stos, kolejka priorytetowa (implementacja tablicowa, listowa, algorytmy).
-
Drzewa, przechodzenie drzew.
-
Kopce, kolejka priorytetowa, heapsort.
-
Programowanie dynamiczne (problem plecakowy, wyszukiwanie najdłuższego wspólnego podciągu).
-
Algorytmy zachłanne (problem wydawania reszty, problem plecakowy, problem wyboru zajęć, problem rozstawienia wież na szachownicy,kodowanie Huffmana).
-
Dolne ograniczenie na złożoności algorytmów sortujących przez porównywanie. Sortowanie w czasie liniowym i nie tylko (sortowanie kubełkowe, counting sort, sortowanie pozycyjne).
-
Grafy, przechodzenie grafów w głąb i wszerz, najkrótsze ścieżki w grafie (alg. Dijkstry).
|
| Forma oceniania: |
- końcowe zaliczenie ustne
- ocena ciągła (bieżące przygotowanie do zajęć i aktywność)
- zaliczenie praktyczne
|
| Literatura: |
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, ,,Wprowadzenie do algorytmów'', WNT, Warszawa 2004
-
Donald E. Knuth, ,,Sztuka programowania t. 1-3'', WNT, Warszawa 2002
-
C.H. Papadimitriou, ,,Złożoność obliczeniowa'',WNT, Warszawa 2002.
|
| Modułowe efekty kształcenia: |
| 01 |
potrafi programować w co najmniej dwóch językach wysokiego poziomu oraz projektować i tworzyć aplikacje użytkowe (w tym aplikacje sieciowe i aplikacje wykorzystujące serwery bazodanowe) |
| 02 |
zna podstawowe narzędzia matematyki wyższej i potrafi ich użyć w zastosowaniach informatycznych |
| 03 |
zna teoretyczne podstawy informatyki |
| 04 |
potrafi formułować pytania i oryginalne sądy dotyczące zagadnień informatycznych oraz dziedzin pokrewnych, potrafi mówić o tematach fachowy w sposób zrozumiały dla laików |
|
