| Przedmiot: |
Algorytmy i struktury danych I |
| Kierunek: |
Informatyka, I stopień [6 sem], stacjonarny, ogólnoakademicki, rozpoczęty w: 2012 |
| Rok/Semestr: |
II/3
|
| Liczba godzin: |
30,0 |
| Nauczyciel: |
Krzaczkowski Jacek, dr |
| Forma zajęć: |
wykład |
| Rodzaj zaliczenia: |
egzamin |
| Punkty ECTS: |
6,0 |
| Godzinowe ekwiwalenty punktów ECTS (łączna liczba godzin w semestrze): |
| 0 |
Godziny kontaktowe z prowadzącym zajęcia realizowane w formie konsultacji |
| 30,0 |
Godziny kontaktowe z prowadzącym zajęcia realizowane w formie zajęć dydaktycznych |
| 0 |
Przygotowanie się studenta do zajęć dydaktycznych |
| 0 |
Przygotowanie się studenta do zaliczeń i/lub egzaminów |
| 0 |
Studiowanie przez studenta literatury przedmiotu |
|
| Poziom trudności: |
średnio zaawansowany
|
| Wstępne wymagania: |
Umiejętność programowania. |
| Metody dydaktyczne: |
- dyskusja dydaktyczna
- wykład informacyjny
- wykład konwersatoryjny
|
| 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.
|
| Forma oceniania: |
- ćwiczenia praktyczne/laboratoryjne
- egzamin pisemny
|
| 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.
|
