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 (x egzamin, + zaliczenie, # projekt)						punkty ECTS
		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:

1. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Wprowadzenie do algorytmów. WNT, Warszawa, 2005.

2. Drozdek A.: C++. Algorytmy i struktury danych. Wydawnictwo Helion, Gliwice, 2004.

3. Harris S., Ross J.: Algorytmy od podstaw. Wydawnictwo Helion, Gliwice, 2006.

4. Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych. WNT, Warszawa, 2006.

Uzupełniająca:

1. Aho A.V., Hopcroft J.E., Ullman J.D.: Algorytmy i struktury danych. Wydawnictwo Helion, Gliwice, 2003.

2. Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów. Wydawnictwo Helion, Gliwice, 2003.

3. Kotowski P.: Algorytmy + struktury danych = abstrakcyjne typy danych. Wydawnictwo BTC, Warszawa, 2006.

4. Loudon K.: Algorytmy w C.: Wydawnictwo Helion, Gliwice, 2003.

5. Wirth N.: Algorytmy + struktury danych = programy. WNT, Warszawa, 2004.

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

---