wyklad AiSD, Informatyka PWr, Algorytmy i Struktury Danych, Algorytmy i Struktury Danych
[ Pobierz całość w formacie PDF ]
1
UWAGI WSTĘPNE :
Zawarty w tym zbiorze program wykładu, ma na celu wyłącznie ułatwienie przygotowania się do zajęć oraz śledzenie
toku wykładu - nie może być traktowany jako pełna wersja wykładu, której znajomość wystarczy do zaliczenia. Również
wykład nie jest kompletnym przedstawieniem omawianych zagadnień, lecz jedynie wprowadzeniem do nich. Reszta jest
w literaturze - na szczęście dość obfitej. Przykładowe pozycje podaję poniżej.
Literatura:
1.
Harris S., Ross J., Od podstaw Algorytmy.
2.
Wirth N., Algorytmy + struktury danych = programy.
3.
Reingold E. M., Nievergelt J., Deo N. Algorytmy kombinatoryczne.
4.
Aho A. V., Hopcroft J. E., Ullman J. D. Projektowanie i analiza algorytmów komputerowych.
5.
Knuth D., Sztuka programowania, sortowanie i wyszukiwanie.
6.
Banachowski L, Diks K, Rytter W Algorytmy i struktury danych.
7.
Cormen T H, Leiserson Ch E, Rivest R L Wprowadzenie do algorytmów
8.
Sedgewick Robert Algorytmy w Javie
Literatura uzupełniająca:
1.
Harel D Rzecz o istocie informatyki - Algorytmika
2.
Bentley J Perełki oprogramowania
3.
Sysło M M Algorytmy
Uwagi: Pozycja 1 jest najbardziej zgodna z tokiem wykładu - można ją uznać za podstawową. Pozycje 2...4 są nieco
wiekowe co może utrudniać czytanie, jednak zawierają wiele wartościowych informacji. 7 jest chyba najlepszą książką
poświęconą algorytmom w języku polskim (jej wadą jest cena i dla niektórych to ,że zawiera tylko opisy algorytmów -
bez programów). 6 jest najbardziej dostępna jednak jej skrótowość powoduje, że więcej jest myślenia niż czytania. 8 -
bardzo dobra i dostosowana do Javy.
Z uzupełniających chciałbym szczególnie polecić 1 - czyta się prawie jak kryminał.
Wszystkie problemy i wątpliwości można wyjaśnić :
- osobiście pok. 4.12 B-4 ( terminy konsultacji podaję osobno)
- telefonicznie 320-42-19
- przez pocztÄ™ elektronicznÄ… janusz.ratajczak@pwr.wroc.pl
Temat 1. Budowa i wykorzystanie iteratorów.
Dostępne w Javie pętle, nie są w pełni elastyczne. Nie dają również możliwości ukrycia szczegółów związanych ze
sposobem przechodzenia przez kolejne elementy przetwarzanego zbioru. Elastyczniejsze są iteratory. W swojej książce o
wzorcach projektowych, Gamma i inni zaproponowali koncepcję iteratora, który jest bardziej uniwersalny od
standardowego , wbudowanego w JavÄ™.
Interfejs iteratora :
package iterators;
public interface Iterator
{ public void previous();
public void next();
public void first();
public void last();
public boolean isDone();
public Object current();
}
Uwaga : nie zawsze warto budować iterator jako klasę generyczną ( parametryzowaną ), wytarczy tylko pamiętać o
rzutowaniu obiektu zwracanego przez metodÄ™ current().
Przykłady wykorzystania iteratora :
- pętla while
Iterator it = ....;
it.first(); //lub it.last()
While(!it.isDone())
{ Object object = it.current();
....
it.next(); //lub it.previous()
}
- pętla for
Iterator it = ....;
for(it.first(); !it.isDone();it.next())
2
{ Object object = it.current();
....
}
- przetwarzanie w odwrotnej kolejności
Iterator it = ....;
for(it.last(); !it.isDone();it.previous())
{ Object object = it.current();
....
}
Przykład implementacji iteratora tablicowego :
package iterators;
public class ArrayIterator implements Iterator
{ final Object[] _array;
final int _first;
final int _last;
int _current=-1;
public ArrayIterator(Object[] array, int start, int length)
{_array=array;
_first=start;
_last=start+length-1;
}
public ArrayIterator(Object[] array)
{_array=array;
_first=0;
_last=array.length-1;
}
public void first()
{ _current=_first; }
public void last()
{ _current=_last; }
public void next()
{++_current;}
public void previous()
{--_current; }
public boolean isDone()
{return _current <_first || _current> _last; }
public Object current()
{ return _array[_current];}
}
Do przetwarzania w odwrotnej kolejności ( zamiast używać previous zamiast next ) możemy zbudować iterator odwrotny
package iterators;
public class ReverseIterator implements Iterator
{ private final Iterator _it;
public ReverseIterator(Iterator it)
{ _it=it; }
public void first()
{ _it.last(); }
public void last()
{ _it.first(); }
public void next()
{_it.previous();}
public void previous()
{_it.next(); }
public boolean isDone()
{return _it.isDone(); }
public Object current()
3
{ return _it.current();}
}
Dzięki wykorzystaniu iteratora odwrotnego nie trzeba zmieniać klasy która go wykorzystuje - wystarczy przekazać jej
albo iterator bazowy albo odwrotny.
Do przetwarzania tylko wybranych ( wg. jakiegoś kryterium ) elementów wygodnie jest użyć iteratora filtrującego :
package iterators;
public class FilterIterator implements Iterator
{ private final Iterator _it;
private final Predicate _pred;
public FilterIterator(Iterator it, Predicate pred)
{ _it=it; _pred=pred; }
public void filterForwards()
{ while( !_it.isDone() && !_pred.accept(_it.current()))
_it.next();
}
public void filterBackwards()
{ while( !_it.isDone() && !_pred.accept(_it.current()))
_it.previous();
}
public void first()
{ _it.first();
filterForwards();}
public void last()
{ _it.last();
filterBackwards();}
public void next()
{_it.next();
filterForwards();}
public void previous()
{_it.previous();
filterBackwards();}
public boolean isDone()
{return _it.isDone(); }
public Object current()
{ return _it.current();}
}
Użyliśmy tutaj klasy Predicate zawierającej jedyną metodę accept() - badającą czy dany element spełnia nasze kryteria -
oczywiście trzeba ją zaimplementować w klasie definiującej elementy które przetwarzamy.
package iterators;
public interface Predicate
{ public boolean accept(Object ob); }
Przykład tworzenia i wykorzystania iteratora tablicowego - do wydruku wszystkich i wybranych elementów tablicy.
package iteracje;
import iterators.*;
public class Zawodnik
{ String nazw;
int punkty;
public Zawodnik(String n, int p)
{nazw=n; punkty=p;}
public String toString()
{ return nazw+" "+punkty;}
}
4
package iteracje;
import iterators.*;
import lists.*;
public class Zawody
{ Zawodnik[] tab=new Zawodnik[5];
public Zawody()
{ }
//do wydruku zawodników którzy mają więcej niż dwa punkty
private class ZawodnikOK implements Predicate
{ public boolean accept(Object z)
{return ((Zawodnik)z).punkty >2;}
}
public void wydruki()
{ // wypełnienie tablicy
//wydruk całej tablicy; można podać indeksy : początku i końca fragmentu tablicy
Iterator it= new ArrayIterator(tab);
it.first();
while(!it.isDone())
{Zawodnik zaw=(Zawodnik)it.current();
System.out.println(zaw);
it.next();
}
//wykorzystano wcześniej utworzony iterator tablicowy
Iterator fit= new FilterIterator(it,new ZawodnikOK());
fit.first();
while(!fit.isDone())
{Zawodnik zaw=(Zawodnik)fit.current();
System.out.println(zaw);
fit.next();
}
}
Zadania :
1) Zdefiniuj iterator tablicowy udostępniający co k-ty element tablicy, rozpoczynając od elementu o indeksie poc.
2) Dane są klasy Grupa ( tablica Studentów), Student ( nazwisko i średnia ocen ). Zdefiniuj iterator filtrujący
udostępniający tych studentów którzy mają średnią powyżej podanej wartości granicznej.
3) Zdefiniuj iterator udostępniający kolejne liczby Fibbonacciego mniejsze od podanego N. Uwaga : liczby należy
generować na bieżąco, nie należy używać tablicy do ich przechowywania.
4) Zdefiniuj iterator udostępniający kolejne liczby pierwsze mniejsze od podanego N. Uwaga : liczby należy
generować na bieżąco, nie należy używać tablicy do ich przechowywania.
Temat 2. Złożoność algorytmów.
- złożoność pamięciowa
- złożoność obliczeniowa:
- średnia
- optymistyczna
- pesymistyczna
Typowe złożoności spotykane w algorytmach :
O(1) - stały czas działania
O(log n) – logarytmiczna , czas bardzo wolno rośnie, przy podwojeniu rozmiaru zadania czas rośnie o stałą, czas
wzrośnie dwukrotnie gdy rozmiar wzrośnie do n
2
O(n) - liniowa
O(n log n ) – liniowo-logarytmiczna , daje ponad dwukrotny wzrost czasu przy podwojeniu rozmiaru
O(n (log n )
2
) - nieco szybszy wzrost niż liniowo-logarytmiczny
O( n
2
) - kwadratowa , podwojenie rozmiaru – czterokrotny wzrost czasu
O(2
n
) - wykładnicza , kwadratowy wzrost czasu przy podwojeniu n. (również n! zalicza się do tej klasy).
5
Przykładowe wartości tych funkcji :
lg n
n
n lg n
n (lg n )
2
n
2
2
n
3
10
33
110
100
1024
7
100
664
4414
10000
1 i 30 zer
10
1000
9966
99317
1000000
1 i 300 zer
13
10000
132877
1765633
100000000
1 i 3000 zer
17
100000
1660964
27588016
10000000000
1 i 30000 zer
20
1000000
19931569
397267426
1000000000000
1 i 300000 zer
Uwaga : lg n oznacza log
2
n.
Poniża tabelka pomoże zorientować się w wielkości tych liczb (uwaga : 1000 ≈ 2
10
)
sekundy
100
10000
100000
1000000
10000000
100000000
1000000000
10000000000
ile to jest
2 min
3 godz.
1.1 dnia
1.5 tyg.
4 mies.
3 lata
30 lat
3 wieki
Temat 3. Listy ich implementacja i przetwarzanie.
Lista:
elementarna struktura danych, w której elementy są ustawione w określonej kolejności ( co nie znaczy, że są
uporządkowane ). Lista może być traktowana jako uogólnienie tablicy.
Rodzaje list :
- proste i cykliczne
- jednokierunkowe , dwukierunkowe i wielokierunkowe
- uporzÄ…dkowane i nieuporzÄ…dkowane
W celu uproszczenia działań można wykorzystać elementy organizacyjne : głowę (head) i ogon (tail) - wartownik .
Definicja prostego interfejsu listowego :
package lists;
import iterators.Iterable;
public interface List extends Iterable
{
// dodaj na wskazanÄ… pozycjÄ™
public void insert(int index, Object value) throws IndexOutOfBoundsException;
// dodaj na koniec
public void add(Object value);
//usuń element ze wskazanej pozycji
public Object delete(int index) throws IndexOutOfBoundsException;
// usuń pierwsze wystąpienie wskazanej wartości
public boolean delete(Object value);
// usuń wszystkie elementy
public void clear();
// zmień element na wskazanej pozycji
public Object set(int index, Object value) throws IndexOutOfBoundsException;
// daj wartość wskazanego elementu
public Object get(int index) throws IndexOutOfBoundsException;
// znajdź pozycję podanej wartości; -1 gdy nie ma
public int indexOf(Object value);
// czy dana wartość występuje na liście
public boolean contains(Object value);
// liczba elementów na liście
public int size();
// czy pusta lista
public boolean isEmpty();
[ Pobierz całość w formacie PDF ]