8107620766

Nazwa przedmiotu:	ALGORYTMY I ZŁOŻONOŚĆ
Kod:	1 lOO-AZOOII
Forma przedmiotu:	30 godz. wykładu +30 godz. laboratorium komputerowego
Ilość punktów ECTS:	5
Język wykładowy:	Polski
Sposób zaliczenia:	egzamin pisemny + zaliczenie laboratorium
Cele przedmiotu:	Celem przedmiotu jest zapoznanie studentów z metodami projektow ania i analizy algorytmów. Omówione zostaną zagadnienia zw iązane z pojęciem złożoności obliczeniowej. W trakcie zajęć przedstaw ione zostaną podstawowe algorytmy i struktury danych dolyczące takich zagadnień jak: sortowanie, wyszukiwanie, elementarne i dynamiczne struktury danych, słowniki.
Umiejętności wstępne:
Treści przedmiotu:	1.    Podstawy analizy algorytmów : poprawność algorytmów i metody jej dow odzenia a.    pojęcie złożoności obliczeniowej b.    analiza najgorszego przypadku c.    analiza probabilistyczna 2.    Metody projektowania algoiytmów a.    „dziel i zwyciężaj" b.    algorytmy zachłanne e. programowanie dynamiczne 3.    Podstawowe algorytmy sortowania a.    metody klasyczne b.    QuickSort, HeapSort oraz MergeSort c.    metody sortowania o złożoności liniowej (RadisSort. CountingSort) 4.    Abstrakcyjne struktury danych: a.    listy b.    stosy i kolejki c.    kolejki priorytetowe 5.    Algorytmy wyszukiwania i selekcji a.    algorytm Hoare' b.    - wyszukiwania sekwencyjne c.    wyszukiwanie binarne d.    - drzewa BST
Literatura:	[ 1 ]. Algorytmy w C++, Sedgewick R., Read Me 1999 [2] . Algorytmy i struktury danych. L. Banachowski, K. Diks, W. Ryner, Wydawnictwa Naukowo - Techniczne, 2006. [3] . Wprowadzenie do algorytmów. Thomas H. Corrncn, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004 [41. Struktury danych w języku C. Drozdek, Simon D.L. - WNT, 2003
Koordynator:	Prof. dr hab. Goldstein Stanisław
Data aktualizacji:	2009/01/28

Course name:

Algorithms and Complexity

Course contents:

1.    Analysis of algorithms: -    The algorithms and methods of command -    The concept of computational complexity -    Worst case analysis -    Probabilistic analysis 2.    The methods of designing algorithms -    "Divide and conąuer" -    Greedy algorithms -    Dynamie programming 3.    The basie algorithms for sorting -    Methods of classic -    QuickSort, HeapSort and MergeSort -    Linear sorting methods (RadixSort, CountingSort) 4.    Abstract data types: -    The list -    Stacks and queues -    Priority queues 5.    Search and selection: -    Hoare'a algorithm -    Sequential search -    Binary search -BSTtrees

13