S Y L A B U S P R Z E D M I O T U
NAZWA PRZEDMIOTU: Algorytmy i struktury danych
Kod przedmiotu: .......................................................................................................................................................................
Podstawowa jednostka organizacyjna (PJO) (prowadząca kierunek studiów): Wydział Cybernetyki
Kierunek studiów: Informatyka
Specjalność: wszystkie specjalności kierunku Informatyka
Rodzaj studiów: studia pierwszego stopnia
Forma studiów: studia stacjonarne
Język realizacji: polski
Sylabus ważny dla naborów od roku akademickiego 2008/2009
1. REALIZACJA PRZEDMIOTU
Osoby prowadzące zajęcia:
dr hab. inż. Andrzej Walczak
dr hab. inż. Kazimierz Worwa
dr inż. Marcin Wierzbicki
mgr inż. Hugo Dworak
mgr inż. Paweł Moszczyński
mgr inż. Sławomir Wysocki
mgr inż. Piotr Kędzierski
PJO/instytut/katedra/zakład Wydział Cybernetyki
Instytut Systemów Informatycznych
Zakład Inżynierii Oprogramowania
2. ROZLICZENIE GODZINOWE
semestr |
forma zajęć, liczba godzin/rygor |
punkty |
|||||
|
razem |
wykłady |
ćwiczenia |
laboratoria |
projekt |
seminarium |
|
II |
60x |
20 |
10 |
20+ |
|
|
5 |
razem |
60 |
30 |
10 |
20 |
|
|
5 |
3. PRZEDMIOTY WPROWADZAJĄCE WRAZ Z WYMAGANIAMI WSTĘPNYMI
Wprowadzenie do programowania Wymagania wstępne: rozumienie roli algorytmów, umiejętność implementacji algorytmów w postaci programów komputerowych, znajomość zasad tworzenia programów z wykorzystaniem paradygmatu programowania strukturalnego; opanowanie efektywnego zarządzania procesem tworzenia programu komputerowego; umiejętność programowania w języku C, z wykorzystaniem typów wskaźnikowych.
Matematyka dyskretna 1 Wymagania wstępne: znajomość rachunku zdań, rachunku predykatów i rachunku zbiorów; umiejętność posługiwania się terminologią logiki, teorii mnogości, relacji i funkcji do interpretowania pojęć z zakresu informatyki; opanowanie technik rekurencyjnych i kombinatorycznych do rozwiązywania problemów o charakterze informatycznym; znajomość podstawowych pojęć z zakresu teorii grafów i sieci.
.
4. ZAŁOŻENIA I CELE PRZEDMIOTU
nauczenie umiejętności konstruowania algorytmów z wykorzystaniem podstawowych technik algorytmicznych: dziel i rządź, programowanie dynamiczne, algorytmy zachłanne, przeszukiwanie z nawrotami, heurystyki;
nauczenie podstaw analizy i oceny złożoności obliczeniowej algorytmów;
zapoznanie z podstawowym algorytmami przetwarzania danych: sortowania, selekcji, wyszukiwania;
zapoznanie z podstawowym algorytmami grafowymi;
nabycie umiejętności definiowania i implementacji abstrakcyjnych struktur danych: list, kolejek, drzew, grafów.
5. METODY DYDAKTYCZNE
wykłady i zajęcia laboratoryjne prowadzone są w blokach 2-godzinnych.;
wykłady prowadzone są z wykorzystaniem środków audiowizualnych. do każdego wykładu studenci otrzymują wykorzystywane przez wykładowcę materiały w postaci elektronicznej (prezentacje MS PowerPoint);
na każdych ćwiczeniach laboratoryjnych studenci mają za zadanie indywidualne opracowanie (napisanie i uruchomienie) programu w języku C, będącego rozwiązaniem zadania sformułowanego przez prowadzącego zajęcia;
6. TREŚCI PROGRAMOWE
lp |
temat/tematyka zajęć |
liczba godzin |
||||
|
|
wykł. |
ćwicz. |
lab. |
proj. |
semin. |
Techniki projektowania algorytmów. Technika „dziel i rządź”. Programowanie dynamiczne. Algorytmy zachłanne. Przeszukiwanie z nawrotami. Heurystyki. |
2 |
|
|
|
|
|
Złożoność obliczeniowa algorytmów. Pojęcie złożoności obliczeniowej: złożoność czasowa, złożoność pamięciowa. Asymptotyczna złożoność czasowa: O-notacja, ၗ-notacja, ၑ-notacja. Złożoność optymistyczna, pesymistyczna i średnia. Złożoność zamortyzowana. Ocena złożoności obliczeniowej algorytmów iteracyjnych. Ocena złożoności obliczeniowej algorytmów rekurencyjnych. |
4 |
4 |
|
|
|
|
Listy. Rodzaje struktur listowych. Podstawowe operacje na listach. Metody implementacja list. |
2 |
2 |
4 |
|
|
|
Kolejki. Kolejka LIFO (stos). Kolejka FIFO. Kolejka priorytetowa. Podstawowe operacje na kolejkach. Implementacja kolejek. |
2 |
|
2 |
|
|
|
Drzewa binarne. Implementacja drzew binarnych. Podstawowe operacje na drzewach binarnych. Drzewa BST. Drzewa AVL. Drzewa czerwono-czarne. Kopce. |
6 |
4 |
4 |
|
|
|
Drzewa wielokierunkowe. Pojecie i własności B-drzewa. Podstawowe operacje na B-drzewach. Rodzina B-drzew. |
2 |
|
|
|
|
|
Algorytmy sortowania wewnętrznego. Sortowanie przez wstawianie. Sortowanie przez wybieranie. Sortowanie przez zamianę. Sortowanie przez kopcowanie. Sortowanie szybkie. Sortowanie Shella. Analiza złożoności algorytmów sortowania. |
4 |
|
4 |
|
|
|
Algorytmy sortowania zewnętrznego. Sortowanie przez podział. Sortowanie przez łączenie. |
2 |
|
2 |
|
|
|
Podstawowe algorytmy grafowe. Reprezentacja grafów. Przeszukiwanie wszerz. Przeszukiwanie w głąb. Wyznaczanie najkrótszych dróg. |
4 |
|
4 |
|
|
|
Tablice z haszowaniem. Haszowanie. Tablice z adresowaniem bezpośrednim. Tablice z haszowaniem. Funkcje haszujące. Metody usuwania kolizji. |
1 |
|
|
|
|
|
Problemy obliczeniowo trudne Klasy złożoności problemów. NP-zupełność. NP-zupełność i redukowalność. Nierozstrzygalność. |
1 |
|
|
|
|
|
RAZEM |
30 |
10 |
20 |
|
|
|
7. LITERATURA
Podstawowa:
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Wprowadzenie do algorytmów. WNT, Warszawa, 2005.
Drozdek A.: C++. Algorytmy i struktury danych. Wydawnictwo Helion, Gliwice, 2004.
Harris S., Ross J.: Algorytmy od podstaw. Wydawnictwo Helion, Gliwice, 2006.
Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych. WNT, Warszawa, 2006.
Uzupełniająca:
Aho A.V., Hopcroft J.E., Ullman J.D.: Algorytmy i struktury danych. Wydawnictwo Helion, Gliwice, 2003.
Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów. Wydawnictwo Helion, Gliwice, 2003.
Kotowski P.: Algorytmy + struktury danych = abstrakcyjne typy danych. Wydawnictwo BTC, Warszawa, 2006.
Loudon K.: Algorytmy w C.: Wydawnictwo Helion, Gliwice, 2003.
Wirth N.: Algorytmy + struktury danych = programy. WNT, Warszawa, 2004.
Wróblewski P.: Algorytmy, struktury danych i techniki programowania. Wydawnictwo Helion, Gliwice, 2006.
8. FORMA I WARUNKI ZALICZANIA PRZEDMIOTU
przedmiot zaliczany jest na podstawie zaliczenia ćwiczeń laboratoryjnych i egzaminu;
egzamin przeprowadzany jest w postaci pisemnego testu wielokrotnego wyboru;
warunkiem dopuszczenia do egzaminu jest uzyskanie pozytywnej oceny z ćwiczeń laboratoryjnych;
ocena z ćwiczeń laboratoryjnych uwzględnia wyniki pracy studenta na ćwiczeniach rachunkowych;
w ramach ćwiczeń laboratoryjnych student może uzyskać do 20 pkt.; na każdych ćwiczeniach laboratoryjnych student powinien opracować (napisać i uruchomić) program, będący rozwiązaniem zadania sformułowanego przez prowadzącego zajęcia; za poprawny, napisany w trakcie zajęć program student otrzymuje 2 pkt.; za każdy poprawny program oddany z opóźnieniem (na kolejnych zajęciach) student otrzymuje 1 pkt.;
w ramach ćwiczeń rachunkowych student może uzyskać do 10 pkt., w tym:
0 - 5 pkt. z odpowiedzi ustnych i/lub sprawdzianów pisemnych, wg ustaleń prowadzącego ćwiczenia;
0 - 5 pkt. z kolokwium końcowego;
przeliczenie łącznej sumy punktów, uzyskanych na ćwiczeniach rachunkowych i laboratoryjnych na ocenę odbywa się następująco:
Suma punktów |
< 16 |
16 - 18 |
19 - 21 |
22 - 24 |
25 - 27 |
> 27 |
Ocena |
2 |
3 |
3,5 |
4 |
4,5 |
5 |
1
kierownik jednostki organizacyjnej odpowiedzialnej za przedmiot
.................................................
prof. dr hab. inż. Andrzej AMELJAŃCZYK
"Z A T W I E R D Z A M"
Dziekan Wydziału ......
prowadzącego kierunek studiów
……………………………………………………………
dr hab. inż. Ryszard Antkiewicz, prof. nzdw. WAT
Warszawa, dnia ..........................
autor sylabusa
..........................................................
dr hab. inż. Kazimierz WORWA , prof. ndzw. WAT