ALGORYTMY I STRUKTURY DANYCH

PJWSTK, semestr letni 2003,
Grażyna Mirkowska

Spis Treści

Data ostatnich zmian :  marzec, 2003

Organizacja

Wykład Algorytmy i Struktury Danych odbywać się będzie w poniedziałki o godz.17:15-18:45. Wykładowi towarzyszą ćwiczenia tablicowe. Co dwa tygodnie, w ramach cwiczeń, odbywać się będzie krótki sprawdzian, na którym można zdobyć 5 punktów. Na dziesiątych ćwiczeniach odbędzie się kolokwium (za 30 punktów). Aktywność na ćwiczeniach jest brana pod uwagę przy zaliczaniu ćwiczeń. Obecność na ćwiczeniach jest obowiązkowa.  
Studenci są zobowiązani do zrealizowania, do końca maja, wybranego projektu. Projekty będą realizowane poza ćwiczeniami w grupach 3 osobowych. Za projekt można uzyskać do 15 punktów. Wszystkie projekty biorą  udział w konkursie na najlepszy projekt . 

Zaliczenie ćwiczeń jest uwarunkowane uzyskaniem co najmniej 40 punktów .

Wykład zakończy się egzaminem (= 40 punktów)

Ocena.
Pozytywna ocena z przedmiotu ASD wymaga zaliczenia ćwiczeń oraz uzyskania z egzaminu co najmniej połowy punktów.
Ocena końcowa zależy od liczby uzyskanych z egzaminu punktów następująco:
< 20 -----> ndst
20-23 -----> dost
24-27 -----> dost+
28-31-----> dobry
32-35-----> dobry+
36- 40 -----> bardzo dobry 
Osoby, które zdobedą pierwsze miejsce w konkursie na najlepszy projekt zostaną zwolnione z egzaminu z oceną o 1/2 stopnia mniejszą niż uzyskana na zaliczenie ćwiczeń

SPIS TRESCI

Cwiczenia laboratoryjne

Co drugie zajęcia rozpoczynać się będą krótkim sprawdzianem dotyczącym pojęć i algorytmów omawianych na pracowni lub na wykładzie.


Tematy realizowane 

Uwagi
cw01 Problem maksymalnych sum. Różne metody rozwiązania. Koszty algorytmów. Analiza poprawności rozwiązań.
cw02  Notacja asymptotyczna
cw03  Problem wyszukiwania : wyszukiwanie binarne i sekwencyjne
cw04  Problemy wyszukiwania: min-max i kty co do wielkości. Algorytm Turniej
cw05  Algorytm Hoare (wyszukiwania ktego elementu). Struktury danych :stos, kolejka.
cw06  
cw07  
cw08  
cw09  
cw10  


SPIS TRESCI

WYKŁADY


Data

Tematy zrealizowane

Uwagiagi
W01 03-03-03 Wprowadzenie. Omówienie tematyki wykładu.
Problemy algorytmiki. Poprawnosć algorytmu.Koszt algorytmu. Notacja asymptotyczna.
W02

Problemy wyszukiwania w dowolnym i w uporządkowanym ciągu. Badanie kosztu średniego. Wyszukiwanie binarne.
W03

Problem wyszukiwania min-max i drugi co do wielkości.
Optymalnośc rozwiązania. Algorytm turniej.
W04  
 cd. wyszukiwanie -Algorytm Hoare. Podstawowe struktury danych: listy stosy, kolejki.
W05


W06


W07


W08


W09


W10


W11


W12


w13


W14


W15


SPIS TRESCI
========================================================================================================

PROJEKTY



REGULAMIN


1.    Projekty będą realizowane w trzyosobowych zespołach.
2.    Rola każdej osoby w zespole powinna być wyraźnie określona i uzgodniona z prowadzącym asystentem.
3.    Projekty powinny być zrealizowane do końca maja.
4.    Projekty biorą udział w konkursie w jednej z  6 kategorii tematycznych. 
5.    Pierwszą nagrodą w konkursie jest zwolnienie z egzaminu, z oceną o pół stopnia niższą niż uzyskana na zaliczenie ćwiczeń
      (pierwsza nagroda może nie być przyznana, jeśli żaden z projektów nie będzie spełniał podanych wymagań).
6.    Oceny projektów dokona komisja złożona z wszystkich prowadzących zajęcia.
7.    Maksymalna ocena za zrealizowany projekt wynosi 15 punków. Punkty te dolicza się do liczby punktów potrzenych na zaliczenie ćwiczeń.



DOKUMENTACJA PROJEKTU


TEMATY PROJEKTOW

Projekt  Biblioteka algorytmów teorioliczbowych
Cel : Opracowanie zestawu narzędzi pozwalajacych na wykonywanie operacji arytmetycznych na dużych liczbach.
Zaimplementowanie systemu kryptograficznego RSA przy użyciu algorytmów z projektowanej biblioteki.

Projekt  Biblioteka algorytmów macierzowych
Cel:  Zbudowanie systemu algebraicznego, umożliwiajacego operacje na macierzach dowolnych typów.
Implementacja danego układu bramek logicznych wyrażonych w języku operacji na macierzach.

Projekt    Grafy
Cel : Operacje na grafach.
1.    Narzędzia do tworzenia i wizualizacji grafów  zorientowanych i niezorientowanych w sposób dynamiczny.
2.    Zapamiętywanie opisów grafów w pamięci wewnętrznej i na pliku. Rysowanie, wcześniej zapisanych grafów.
3.    Operacje na grafach: dołączanie nowych wierzchołków  i krawędzi, usuwanie  krawędzi i ew. wierzchołków.
4.    Algorytmy odwiedzania wierzchołków grafu.
5.    Problem kolorowania grafu (lub konstrukcja minimalnego drzewa rozpinającego grafu  lub inne algorytmy grafowe).

Literatura
 Cormen, Leisenrson, Rivest, Wprowadzenie do algorytmów,
 Aho A., Hopcroft J., Ullman J.,Projektowanie i analiza algorytmów komputerowych

Projekt   Logika
Cel : Pomoc dydaktyczna do nauki logiki.
1.    Wczytywanie  poprawnych formuł rachunku zdań i ich wizualizacja.
2.    Magazyn formuł: operacje dołączania i usuwania.
3.    Obliczanie wartości formuły dla rożnych wartościwań.
4.    Badanie tautologiczności, wykrywanie sprzeczności w zbiorze formuł.
5.    Testy i zabawy sprawdzające.
6.    Problem dowodzenia : wizualizacja dowodów apagogicznych i gentzenowskich.

Literatura
Tarski world
Rasiowa H., Wstęp do Matematyki Współczesnej,
Mostowski A., Logika Matematyczna



Literatura Pomocnicza

Aho A., Hopcroft J., Ullman J., Projektowanie i analiza algorytmów komputerowych, PWN
Alagic S., Arbib M., Projektowanie programów poprawnych i dobrze zbudowanych, WNT
Baase S., Computer Algorithms
Banachowski L., Kreczmar A., Elementy analizy algorytmów , WNT
Banachowski L., Kreczmar A., Rytter W., Analiza algorytmów i struktur danych, WNT
Banachowski L., Diks K.., Rytter W.,Algorytmy i struktury danych , WNT
Berge C., Graphes et Hypergraphes
Cormen T., Leiserson Ch., Rivest R., Wprowadzenie do algorytmów , WNT
Dijkstra E., Umiejętnosć programowania , WNT
Harel D., Algorytmika, WNT
Lipski W., Kombinatoryka dla programistów, WNT
Mirkowska G., Salwicki A., Logika dla Programistów, WNT
Sakarovitch, Optimisation Combinatoire
Sedgewick R., Algorithms
Wirth N., Algorytmy+Struktury Danych = Programy, WNT

SPIS TRESCI