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ą [e-mail]

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())

{ 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()

{ 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;}

}

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²

O(n) - liniowa

O(n log n ) - liniowo-logarytmiczna , daje ponad dwukrotny wzrost czasu przy podwojeniu rozmiaru

O(n (log n )² ) - nieco szybszy wzrost niż liniowo-logarytmiczny

O( n² ) - kwadratowa , podwojenie rozmiaru - czterokrotny wzrost czasu

O(2ⁿ ) - wykładnicza , kwadratowy wzrost czasu przy podwojeniu n. (również n! zalicza się do tej klasy).

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₂ n.

Poniża tabelka pomoże zorientować się w wielkości tych liczb (uwaga : 1000 ≈ 2¹⁰ )

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();

}

Uwaga : tak naprawdę podstawowymi metodami są : insert, delete, get i size. Pozostałe ułatwiają po prostu korzystanie z list i można je zrealizować wykorzystując metody podstawowe.

Ponieważ część metod można zdefiniować niezależnie od konkretnej implementacji listy, wygodnie jest zdefiniować pomocniczą klasę AbstractList.

package lists;

import iterators.Iterator;

// zestaw metod ułatwiających implementację list

public abstract class AbstractList implements List

{

// wydruk wszystkich elementów listy

public String toString() {

StringBuffer buffer = new StringBuffer();

buffer.append('[');

if (!isEmpty()) {

Iterator i = iterator();

for (i.first(); !i.isDone(); i.next())

buffer.append(i.current()).append(", ");

buffer.setLength(buffer.length() - 2);

}

buffer.append(']');

return buffer.toString();

}

// ^ - bitowa różnica symetryczna

public int hashCode() {

int hashCode = 0;

Iterator i = iterator();

for (i.first(); !i.isDone(); i.next())

hashCode ^= i.current().hashCode();

return hashCode;

}

public boolean equals(Object object) {

return object instanceof List ? equals((List) object) : false;

}

public boolean equals(List other) {

if (other == null || size() != other.size())

return false;

else { Iterator i = iterator();

Iterator j = other.iterator();

for(i.first(),j.first();!i.isDone() && !j.isDone() &&

i.current().equals(j.current()); i.next(), j.next());

return i.isDone() && j.isDone();

}

}

}

Elementy list mogą być przechowywane w tablicy lub na liście wiązanej, można więc zaproponować dwie implementacje list.

• implementacja tablicowa

package lists;

import iterators.*;

public class ArrayList extends AbstractList

{ // domyślna wielkość początkowa tablicy

private static final int DEFAULT_INITIAL_CAPACITY = 16;

// bieżąca wielkość tablicy

private final int _initialCapacity;

private Object[] _array;

// długość listy

private int _size;

public ArrayList()

{ this(DEFAULT_INITIAL_CAPACITY); }

public ArrayList(int initialCapacity) {

_initialCapacity = initialCapacity;

clear(); // tworzy pustą tablicę o podanym rozmiarze

}

public ArrayList(Object[] array) {

_initialCapacity = array.length;

clear();

System.arraycopy(array, 0, _array, 0, array.length);

_size = array.length;

}

//jeśli trzeba powiększ tablicę; value nie może być null

public void insert(int index, Object value) throws IndexOutOfBoundsException {

if(index<0 || index>_size) throw new IndexOutOfBoundException();

ensureCapacity(_size + 1);

System.arraycopy(_array, index, _array, index + 1, _size - index);

_array[index] = value;

++_size;

}

public Object delete(int index) throws IndexOutOfBoundsException {

checkOutOfBounds(index);

Object value = _array[index];

int copyFrom = index + 1;

if (copyFrom < _size)

System.arraycopy(_array, copyFrom, _array, index, _size - copyFrom);

--_size;

return value;

}

public boolean delete(Object value) {

int index = indexOf(value);

if (index != -1)

delete(index);

return index != -1;

}

public void add(Object value) {

insert(size(), value);

}

public boolean contains(Object value) {

return indexOf(value) != -1;

}

public boolean isEmpty() {

return _size == 0;

}

public void clear() {

_array = new Object[_initialCapacity];

_size = 0;

}

public Object set(int index, Object value) throws IndexOutOfBoundsException {

checkOutOfBounds(index);

Object oldValue = _array[index];

_array[index] = value;

return oldValue;

}

public Object get(int index) throws IndexOutOfBoundsException {

checkOutOfBounds(index);

return _array[index];

}

public int indexOf(Object value) {

int i =0;

while(i < _size && value.equals(_array[i]))

++i;

return i<_size ? i : -1;

}

public Iterator iterator() {

return new ArrayIterator(_array, 0, _size);

}

public int size() {

return _size;

}

// wykorzystywana przy wstawianiu;

private void ensureCapacity(int capacity) {

if (_array.length < capacity) {

Object[] copy = new Object[capacity + capacity / 2];

System.arraycopy(_array, 0, copy, 0, _size);

_array = copy;

}

}

private void checkOutOfBounds(int index) throws IndexOutOfBoundsException {

if (index < 0 || index >= size())

throw new IndexOutOfBoundsException();

}

}

• implementacja wykorzystująca dwukierunkową listę wiązaną z wartownikiem

package lists;

import iterators.*;

// dwukierunkowa lista wiązana z wartownikiem wskazującym na początek i koniec listy

// element listy jest zdefiniowany jako wewnętrzna prywatna klasa

public class LinkedList extends AbstractList {

private final Element _headAndTail = new Element(null); // wartownik

private int _size; // dlugość listy

public LinkedList()

{ clear();}

public void insert(int index, Object value) throws IndexOutOfBoundsException {

if(index<0 || index>_size) throw new IndexOutOfBoundException();

Element element = new Element(value);

element.attachBefore(getElement(index));

++_size;

}

public Object delete(int index) throws IndexOutOfBoundsException {

checkOutOfBounds(index);

Element element = getElement(index);

element.detach();

--_size;

return element.getValue();

}

public boolean delete(Object value) {

Element e = _headAndTail.getNext();

while (e != _headAndTail && ! value.equals(e.getValue()))

e = e.getNext();

if (e != _headAndTail) {

e.detach(); --_size; return true;

}

else return false;

}

public void add(Object value)

{ insert(size(), value); }

public boolean contains(Object value)

{ return indexOf(value) != -1; }

public boolean isEmpty()

{ return _size == 0; }

public void clear() {

_headAndTail.setPrevious(_headAndTail);

_headAndTail.setNext(_headAndTail);

_size = 0;

}

public Object set(int index, Object value) throws IndexOutOfBoundsException {

checkOutOfBounds(index);

Element element = getElement(index);

Object oldValue = element.getValue();

element.setValue(value);

return oldValue;

}

public Object get(int index) throws IndexOutOfBoundsException {

checkOutOfBounds(index);

return getElement(index).getValue();

}

public Iterator iterator()

{ return new ValueIterator(); }

public int indexOf(Object value) {

int index = 0;

Element e = _headAndTail.getNext();

while( e != _headAndTail && ! value.equals(e.getValue()))

{ e = e.getNext(); ++index; }

return e!=_headAndTail ? index : -1;

}

public int size() {

return _size;

}

// wybór kierunku przeszukiwania przyspiesza działanie

// zapamiętanie ostatnio odczytywanego elementu i jego indeksu daje większe przyspieszenie

private Element getElement(int index)

{return index< _size/2 ? getElementForwards(index) : getElementBackwards(index); }

// dojście do podanej pozycji w przód

private Element getElementForwards(int index) {

Element element = _headAndTail.getNext();

for (int i = index; i > 0; --i)

element = element.getNext();

return element;

}

private Element getElementBackwards(int index) {

Element element = _headAndTail;

for (int i = _size - index; i > 0; --i)

element = element.getPrevious();

return element;

}

private void checkOutOfBounds(int index) throws IndexOutOfBoundsException {

if (index < 0 || index >= size())

throw new IndexOutOfBoundsException();

}

// pomocnicza klasa definiująca element listy

private static final class Element {

private Object _value;

private Element _previous;

private Element _next;

public Element(Object value)

{ setValue(value); }

public void setValue(Object value)

{ _value = value; }

public Object getValue()

{ return _value; }

public Element getPrevious()

{ return _previous;}

public void setPrevious(Element previous)

{ _previous = previous; }

public Element getNext()

{ return _next; }

public void setNext(Element next)

{ _next = next; }

// wstaw dany (this) element przed element next

public void attachBefore(Element next) {

Element previous = next.getPrevious();

setNext(next);

setPrevious(previous);

next.setPrevious(this);

previous.setNext(this);

}

public void detach() {

_previous.setNext(_next);

_next.setPrevious(_previous);

}

}

// iterator po wartościach elementów listy

// bardziej efektywny od zwykłej pętli po indeksach

private final class ValueIterator implements Iterator {

private Element _current = _headAndTail;

public void first()

{ _current = _headAndTail.getNext(); }

public void last()

{ _current = _headAndTail.getPrevious(); }

public boolean isDone()

{ return _current == _headAndTail; }

public void next()

{ _current = _current.getNext(); }

public void previous()

{ _current = _current.getPrevious(); }

public Object current() throws IndexOutOfBoundsException {

if (isDone())

throw new IndexOutOfBoundsException();

return _current.getValue();

}

}

}

Przykład wydruku elementów listy z wykorzystaniem jej iteratora (klasę Zawodnik zdefiniowano wcześniej :

package iteracje;

import iterators.*;

import lists.*;

import sorting.*;

public class Zawody

{ List lista = new ArrayList();

public Zawody(){ }

private class ZawodnikOK implements Predicate

{ public boolean accept(Object z)

{return ((Zawodnik)z).punkty >2;}

}

public void wydruki()

{ //wypełnienie elementów listy

Iterator it= lista.iterator();

it.first();

while(!it.isDone())

{ Zawodnik zaw=(Zawodnik)it.current();

System.out.println(zaw);

it.next();

}

System.out.println("Koniec");

}

Iterator fit= new FilterIterator(lista.iterator(),new ZawodnikOK());

fit.first();

while(!fit.isDone())

{ Zawodnik zaw=(Zawodnik)fit.current();

System.out.println(zaw);

fit.next();

}

System.out.println("Koniec");

}

}

Wybór implementacji zależy od tego jakie działania na liście wykonujemy najczęściej.

Zadania :

5. Można przyspieszyć implementację wiązaną listy przez zapamiętanie indeksu bieżącej pozycji. Zmodyfikuj odpowiednie metody.

6. Zaimplementuj listę, która do przechowywania wartości elementów wykorzystuje jednokierunkową listę wiązaną z wartownikiem . Porównaj prostotę i złożoność obliczeniową poszczególnych metod z wesją z wykładu.

7. Zaimplementuj listę, która do przechowywania wartości elementów wykorzystuje jednokierunkową listę wiązaną bez wartownika . Porównaj prostotę i złożoność obliczeniową poszczególnych metod z wesją z wykładu.

8. Dane są klasy Grupa ( lista Studentów), Student ( nazwisko i średnia ocen ). W klasie Grupa zdefiniuj metody :

• wybierzDobrych , wynikiem powinna być lista studentów mających średnią powyżej podanej wartości granicznej;

• usuńZłych , efektem powinno być usunięcie z listy studentów mających średnią poniżej podanej wartości granicznej;

• sredniaOcen, obliczającą średnia ocen wszystkich studentów

9. Jaka lista będzie najlepsza do wyznaczania LiczbySzczesliwej ( dla danych N i K ). Piraci ustawili N jeńców w koło i zaczynając od pierwszego liczyli do K, K-tego jeńca wrzucali do morza i odliczali dalej, zabawa trwała dotąd aż został tylko jeden jeniec - jego początkowa pozycja w kręgu jest właśnie szukaną LiczbaSzczesliwa dla danych N i K. Przyjąć najlepszy model i napisać odpowiednie metody. Uwaga: zadanie jest również znane pod nazwą problem Josephusa, okazuje się, że można zbudować odpowiedni wzór.

10. Rozbuduj interfejs list o operację złożenia list ( konkatenacji ). Operacja ta dołącza podaną ( parametr) listę na koniec danej ( this) listy . Czy można ją zrealizować jako uniwersalną ( niezależną od implementacji listy) , czy trzeba definiować oddzielnie dla list bazujących na tablicach i list wiązanych ?

Temat 4. Kolejki ich implementacja i przetwarzanie.

Kolejka - typ abstrakcyjny realizujący następujący interfejs :

package queues;

public interface Queue {

public void enqueue(Object value); //wstaw do kolejki

public Object dequeue() throws EmptyQueueException; //pobierz z kolejki

public void clear(); //usuń wszystkie elementy

public int size(); //długość kolejki

public boolean isEmpty(); // true jeśli kolejka jest pusta

}

Kolejki możemy dzielić na różne kategorie :

• nieograniczone

• ograniczone (dochodzi dodatkowa metoda sprawdzająca czy kolejka jest pełna)

Inny podział :

• zwykłe ( o kolejności pobierania z kolejki decyduje wyłacznie kolejność wstawiania)

stosuje się dwie strategie pobierania :

• FIFO (First In First Out) - typowa kolejka

• LIFO ( Last In First Out) - patrz niżej

• priorytetowe ( wcześniej są pobierane elementy o wyższym priorytecie ) - te będą omówione później.

Ze względu na złożoność operacji nie wykorzystuje się tablic do przechowywania elementów nieograniczonej kolejki zwykłej.

Implementacja bazująca na liście wiązanej może wyglądać np. tak :

package queues;

import lists.LinkedList;

import lists.List;

/**

* zwykła kolejka FIFO bazująca na liście wiązanej

*/

public class ListFifoQueue implements Queue {

private final List _list;

public ListFifoQueue() {

this(new LinkedList());

}

public ListFifoQueue(List list)

{ _list = list; }

public void enqueue(Object value)

{ _list.add(value); }

public Object dequeue() throws EmptyQueueException {

if (isEmpty()) {

throw new EmptyQueueException();

}

return _list.delete(0);

}

public void clear()

{ _list.clear(); }

public int size()

{ return _list.size(); }

public boolean isEmpty()

{ return _list.isEmpty(); }

public String toString()

{ return _list.toString();}

}

Zadania :

11. Przedstaw bezpośrednia realizację ( bez wykorzystania klasy List ) zwykłej kolejki nieograniczonej. Do przechowywania elementów wykorzystaj jednokierunkową listę wiązaną z wartownikiem.

12. Ograniczoną kolejkę zwykłą bazującą na tablicy można efektywnie ( czyli unikając kopiowania dużych porcji danych) zaimplementować w sposób bezpośredni ( bez wykorzystania klasy List) . Zdefiniuj odpowiednią klasę np. ArrayFifoQueue.Złożoność wszystkich operacji powinna być stała - O(1).

Temat 5. Stosy ich implementacja i przetwarzanie.

Stos jest typem abstrakcyjnym realizującym następujący intefejs :

package stacks;

import queues.Queue;

public interface Stack extends Queue {

public void push(Object value); // odłóż na stos

public Object pop() throws EmptyStackException; //pobierz ze stosu

public Object peek() throws EmptyStackException; //odczytaj ( nieniszcząco ) ze stosu

public void clear(); //czyść stos

public int size(); // wysokość stosu

public boolean isEmpty(); //true jeśli stos jest pusty

}

Stos może być traktowany jako zwykła kolejka ze strategią obsługi LIFO. Podobnie jak kolejki możemy podzielić stosy na nieograniczone i ograniczone.

Przykładowa implementacja stosu z wykorzystaniem listy wiązanej i wskazaniem, że stos jest rodzajem kolejki.

package stacks;

import lists.LinkedList;

import lists.List;

import queues.EmptyQueueException;

public class ListStack implements Stack {

private final List _list = new LinkedList();

public void push(Object value)

{ _list.add(value);}

public Object pop() throws EmptyStackException {

if (isEmpty()) {

throw new EmptyStackException();

}

return _list.delete(_list.size() - 1);

}

public Object peek() throws EmptyStackException {

Object result = pop();

push(result);

return result;

}

public void enqueue(Object value)

{ push(value); }

public Object dequeue() throws EmptyQueueException {

try {

return pop();

} catch (EmptyStackException e) {

throw new EmptyQueueException();

}

}

public void clear()

{ _list.clear(); }

public int size()

{ return _list.size(); }

public boolean isEmpty()

{ return _list.isEmpty(); }

}

Ponieważ stos ( szczególnie ograniczony ) może mieć efektywną implementację tablicową, może być celowe zastąpieniem bezpośredniego tworzenia listy odpowiednim konstruktorem, co pozwoli użytkownikowi wybierać rodzaj stosu.

Jako przykład wykorzystania kolejki i stosu podaję kalkulator obliczający wartość wyrażenia zapisanego w notacji ONP ( odwrotna notacja polska, notacja postfiksowa). Wyrażenie jest podane jako kolejka wartości i operatorów.

package calculate;

import java.io.*;

import lists.*;

import queues.*;

import stacks.*;

public class calculate

{ Analyzer analyzer= new Analyzer();

void evaluate() throws IOException

{ //przekształcenie napisu zawierającego postać nawiasową na kolejkę reprezentującą ONP

Queue onp=analyzer.analyze();

//kontrolny wydruk ONP

System.out.println(onp.toString());

Stack st=new ListStack();

Object el;

while(!onp.isEmpty())

{ el=onp.dequeue();

if(el instanceof Double)

st.push(el);

else { double right=(Double)st.pop(),left=(Double)st.pop();

switch((Character)el)

{ case '+' : st.push(left+right); break;

case '-' : st.push(left-right); break;

case '*' : st.push(left*right); break;

case '/' : st.push(left/right); break;

}

}

}

System.out.println((Double)st.pop());

}

}

Do otrzymania zapisu w ONP można wykorzystać nieco zmodyfikowany kalkulator z poprzedniego semestru.

package calculate;

import java.io.*;

import queues.*;

public class Analyzer

{StreamTokenizer wej= new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

Queue onp = new ListFifoQueue();

Queue analyze() throws IOException

{ // ustawiamy analizator tak aby nowa linia (EOL) '/' i '-' były traktowane jako samodzielne tokeny

// pod pojęciem liczby rozumiemy liczbę bez znaku

wej.eolIsSignificant(true);

wej.ordinaryChar('/');

wej.ordinaryChar('-');

System.out.println(" Wprowadz wyrażenie ");

wej.nextToken();

// każda metoda startuje z wczytanym piewrszym tokenem

expression();

return onp;

}

void expression()throws IOException

{ int oper=wej.ttype;

if(oper!='+' && oper!='-') // liczba lub wyrazenie w () - czyli skladnik

{term(); oper=wej.ttype;}

else onp.enqueue(new Double(0.0));

while(oper=='+' || oper=='-')

{ wej.nextToken();

term();

onp.enqueue(new Character((char)oper));

oper=wej.ttype;

}

}

void term() throws IOException

{factor();

int oper=wej.ttype;

while(oper=='*' ||oper=='/')

{ wej.nextToken();

factor();

onp.enqueue(new Character((char)oper));

oper=wej.ttype;

}

}

void factor()throws IOException

{ if(wej.ttype==wej.TT_NUMBER) onp.enqueue(new Double(wej.nval));

// jeśli nie liczba to musi być wyrażenie w nawiasach

else {wej.nextToken(); expression();}

wej.nextToken();

}

}

Zadania :

13. Przedstaw bezpośrednia realizację ( bez wykorzystania klasy List ) stosu nieograniczonego. Do przechowywania elementów wykorzystaj jednokierunkową listę wiązaną bez wartownika.

14. Przedstaw bezpośrednia realizację ( bez wykorzystania klasy List ) stosu ograniczonego. Do przechowywania elementów wykorzystaj tablicę.

15. Innym rodzajem stosu ograniczonego jest stos tonący. Jeśli na stosie jest już MAKS elementów, to dołożenie następnego powoduje utratę elementu leżącego na samym dnie stosu. Jaką inną nazwę ma taka struktura ? Gdzie jest wykorzystywana ? Zaimplementuj stos tonący. Jaką strukturę danych wykorzystasz do przechowywania elementów.

16. Veloso's Traversable Stack jest to stos, który poza zwykłymi operacjami ma możliwość nieniszczącego odczytu z pozycji wskazywanej przez kursor (peek). Kursor można ustawić na wierzchołek stosu (top) i przesuwać o jedną pozycję w dół stosu (down - potrzebna jest sygnalizacja osiągnięcia dna stosu ). Normalne operacje (push i pop ) automatycznie ustawiają kursor na wierzchołek. Zaimplementuj VTS jako rozszerzenie zwykłego stosu.

Temat 6. Algorytmy sortowania.

Porządkowanie : algorytmy , złożoność algorytmów ( czasowa i pamięciowa), poprawność realizacji algorytmu ( niezmienniki i zbieżniki ).

Istnieje wiele różnych algorytmów sortowania. Aby móc je porównywać należy ustalić własności (kryteria ) według których będziemy to robić. Najważniejsze z nich to:

- stopień skomplikowania algorytmu

- szybkość działania (złożoność obliczeniowa - optymistyczna, średnia i pesymistyczna )

- zapotrzebowanie na dodatkową pamięć (złożoność pamięciowa)

- stabilność algorytmu ( czy elementy o jednakowych kluczach zachowają pierwotną kolejność )

- przydatność do sortowania różnych struktur danych (tablice, listy, pliki).

Oczywiście każdy z algorytmów może mieć wiele różnych realizacji. Raczej nie można powiedzieć, że istnieje jeden najlepszy algorytm ( czy też jego realizacja), tak więc dobierając algorytm sortowania do konkretnego przypadku należy uwzględnić takie czynniki jak:

- rodzaj i wielkość porządkowanej struktury (tablica, lista, plik)

- złożoność porównania kluczy

- złożoność przepisywania elementów (wielkość elementu) - w javie ma to znaczenie tylko wtedy gdy tworzymy kopie elementów

- początkowe uporządkowanie danych ( dane uporządkowane, losowe, prawie uporządkowane, odwrotnie uporządkowane, o tej samej wartości )

- wielkość dostępnej pamięci operacyjnej

- wymagania dotyczące stabilności itp.

Najpełniejszy przegląd zagadnień związanych z sortowaniem można znaleźć w :

Knuth D. E. The art of computer programming. Vol 3. Sorting and Searching.

Warto również zajrzeć do :

1.Wirth N. Algorytmy + struktury danych = programy.

2.Reingold E. M., Nievergelt J., Deo N. Algorytmy kombinatoryczne.

3.Aho A. V., Hopcroft J. E., Ullman J. D. Projektowanie i analiza algorytmów komputerowych.

4.Banachowski L., Kreczmar A. Elementy analizy algorytmów.

5.Banachowski L, Diks K, Rytter W Algorytmy i struktury danych.

6. Cormen T H, Leiserson Ch E, Rivest R L : Wprowadzenie do algorytmów.

7. Sedgewick R. : „Algorytmy w C++”

8. Bentley J. : „Perełki oprogramowania”

Większość (ale nie wszystkie ) algorytmów ustala kolejność elementów na podstawie porównań wartości elementów. Możemy wykorzystać porządek naturalny ( wyznaczony przez metodę compareTo ) lub użyć odpowiednich komparatorów. Drugie rozwiązanie jest bardziej uniwersalne i je będziemy wykorzystywać.

Aby sortować w porządku naturalnym elementy sorowane muszą implementować interface Comparable :

public interface Comparable

{ public int compareTo(Object other); }

czyli mieć zdefiniowaną metodę compareTo ( wynik <0 oznacza this<other; = 0 this = other i >0 this > other).

W drugim przypadku musimy zaimplementować interface Comparator :

public interface Comparator

{ public int compare(Object left, Object right) throws ClassCastException; }

Metoda compare ma wyniki takie jak compareTo.

Można zdefiniować komparator wyznaczający porządek naturalny :

package sorting;

public final class NaturalComparator implements Comparator {

// wykorzystuje wzorzec singleton

public static final NaturalComparator INSTANCE = new NaturalComparator();

private NaturalComparator() { }

public int compare(Object left, Object right) throws ClassCastException

{ return ((Comparable) left).compareTo(right); }

}

Równie łatwo można utworzyć komparator odwrotny :

package sorting;

public class ReverseComparator implements Comparator {

// podstawowy komparator

private final Comparator _comparator;

public ReverseComparator(Comparator comparator)

{ _comparator = comparator; }

public int compare(Object left, Object right) throws ClassCastException

{ return _comparator.compare(right, left); }

}

W przypadkach bardziej złożonych można komplikować metodę compare lub zbudować komparator złożony wykorzystujący istniejące, proste komparatory. Pozwala to czasami uzyskać stabilne sortowanie nawet dla algorytmów niestabilnych.

package sorting;

import iterators.Iterator;

import lists.ArrayList;

import lists.List;

public class CompoundComparator implements Comparator {

//tablica komparatorów ; od najważniejszego

private final List _comparators = new ArrayList();

public void addComparator(Comparator comparator)

{ _comparators.add(comparator); }

public int compare(Object left, Object right) throws ClassCastException {

int result = 0;

Iterator i = _comparators.iterator();

for (i.first(); !i.isDone()&&

(result = ((Comparator) i.current()).compare(left, right))==0; i.next());

return result;

}

}

Algorytmy sortowania.

Rozpoczynamy od algorytmów klasycznych ( o kwdratowej złożoności średniej).

- Na początek najprostszy, ale najgorszy algorytm sortowania przez zamianę (BubbleSort)

Idea algorytmu : 1. powtarzaj aż do całkowitego uporządkowania ciągu

porównuj parę elementów i jeśli ich kolejność jest nieprawidłowa to je zamień

Jego podstawowa realizacja wygląda tak:

Najpierw definicja interfejsu ułatwiającego wykorzystanie algorytmów sortowania :

package sorting;

import lists.List;

public interface ListSorter

// wynikiem jest nowa lista lub stara posortowana

{ public List sort(List list); }

Teraz sortowanie bąbelkowe:

package sorting;

import lists.List;

public class BubbleSort implements ListSorter {

private final Comparator _comparator;

public BubbleSort(Comparator comparator)

{ _comparator = comparator; }

// wynikiem jest posortowana lista pierwotna

// najbardziej prymitywna wersja

public List sort(List list) {

int size = list.size();

for (int pass = 1; pass < size; ++pass) {

for (int left = 0; left < (size - pass); ++left) {

int right = left + 1;

if (_comparator.compare(list.get(left), list.get(right)) > 0)

swap(list, left, right);

}

}

return list;

}

private void swap(List list, int left, int right) {

Object temp = list.get(left);

list.set(left, list.get(right));

list.set(right, temp);

}

}

Jest to algorytm prosty ale wolny . Można go przyspieszyć na kilka sposobów:

• ograniczyć pętlę zewnętrzną przez wykrywanie czy ciąg nie został uporządkowany wcześniej

• ograniczyć pętlę wewnętrzną przez zapamiętanie pozycji ostatniej zamiany w poprzednim przebiegu

• zastąpić ciąg zamian elementów ciągiem przepisań

• przechodząc ciąg na przemian w obu kierunkach ( ShakerSort).

Wprowadzając pierwsze trzy usprawnienia otrzymujemy :

package sorting;

import lists.List;

public class BubbleSort1 implements ListSorter {

private final Comparator _comparator;

public BubbleSort1(Comparator comparator)

{ _comparator = comparator; }

// wynikiem jest posortowana lista pierwotna

//wersja ulepszona wykorywająca wcześniejsze uporządkowanie

public List sort(List list) {

int lastSwap = list.size()-1; //pozycja ostatniej zamiany

while(lastSwap>0){

int end=lastSwap;

lastSwap=0;

for (int left = 0; left < end; ++left) {

if (_comparator.compare(list.get(left), list.get(left+1)) > 0)

{ //ciąg zamian jest zastąpiony ciągiem przepisań

Object temp=list.get(left);

while(left<end && _comparator.compare(temp, list.get(left+1)) > 0)

{ list.set(left, list.get(left+1)); left++; }

lastSwap=left;

list.set(left,temp);

}

}

}

return list;

}

}

Przykład sortowania listy zawodników według nazwisk i punktów:

//klasa zawodnik uzupełniona o metody porównujące

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;}

public int porNazw(Zawodnik z) { return nazw.compareTo(z.nazw);}

public int porPunkty(Zawodnik z) { return punkty-z.punkty;}

}

//klasy komparatorów

package iteracje;

import sorting.*;

public final class NameComparator implements Comparator {

// wykorzystuje wzorzec singleton

public static final NameComparator INSTANCE = new NameComparator();

private NameComparator() { }

public int compare(Object left, Object right) throws ClassCastException

{ return ((Zawodnik)left).porNazw((Zawodnik)right); }

}

package iteracje;

import sorting.*;

public final class PointsComparator implements Comparator {

// wykorzystuje wzorzec singleton

public static final PointsComparator INSTANCE = new PointsComparator();

private PointsComparator() { }

public int compare(Object left, Object right) throws ClassCastException

{ return ((Zawodnik)left).porPunkty((Zawodnik)right); }

}

//sortowanie listy zawodników; najpierw wg nazwisk a potem wg punktów

package iteracje;

import iterators.*;

import lists.*;

import sorting.*;

public class Zawody

{ List lista = new ArrayList();

public Zawody() { }

public void testBubbleSort()

{ // wypełnienie listy

//sortowanie wg nazwisk

ListSorter ls=new BubbleSort(NameComparator.INSTANCE);

lista=ls.sort(lista);

System.out.println(lista);

System.out.println();

// wg punktów

ls=new BubbleSort(PointsComparator.INSTANCE);

lista=ls.sort(lista);

System.out.println(lista);

System.out.println();

//wg punktów i nazwisk (przy równych punktach decyduje nazwisko)

Comparator cc=new CompoundComparator();

cc.add(NameComparator.INSTANCE);

cc.add(PointComparator.INSTANCE);

ls=new BubbleSort(cc);

lista=ls.sort(lista);

System.out.println(lista);

System.out.println();

}

Wolne działanie tego algorytmu wynika z faktu że pojedyncza zamiana sąsiednich elementów zmienia stopień nieuporządkowania ciągu (liczony jako liczba inwersji - ile razy wartość większa występuje przed mniejszą) tylko o 1. Zamiana elementów odległych o h mogłaby zmniejszyć liczbę inwersji nawet o h.

Wykorzystał to w 1959 roku Shell do opracowania sortowania z malejącymi przyrostami (ShellSort)

Idea : Wybieramy ciąg malejących przyrostów h₁,...,h_t spełniający warunek: h_t=1 oraz h_i < h_j dla i >j;

Dla i od 1 do t wykonaj

Przyjmij przyrost h_i

Przez proste wstawianie (lub zamianę) uporządkuj wszystkie podciągi elementów odległych od siebie o h_i

Niestety nie wiadomo jak dobrać dla konkretnego przypadku najlepszy ciąg przyrostów . Ponieważ skomplikowanie tego algorytmu nie jest duże, a złożoność obliczeniowa nie jest najgorsza więc chętnie jest stosowany praktycznie.

Przykładowa realizacja z ciągiem przyrostów: 1,4,13,40,121,364,1093,3280,9841 .......( h_j+1 =3* h_j +1 ), liczbę przyrostów wyznacza się tak aby sortowane podciągi zawierały conajmniej 3 elementy.

package sorting;

import lists.List;

public class ShellSort implements ListSorter {

private final Comparator _comparator;

// przyrost

private int _h = 1;

public ShellSort(Comparator comparator)

{ _comparator = comparator; }

// ciąg przyrostów : h[0]=1; h[i]=3*h[i-1]+1

// minimalna długość podciągu : 3

// sortowanie podciągów : InsertSort

public List sort(List list) {

int size=list.size();

hMaxSet(size); //znajdź największy przyrost

do { //dla malejących kolejno przyrostów

for(int i=_h;i<size;i++) //wstawiaj kolejne elementy na podlistach

insert(list,i);

}while ((_h/=3) >0);

return list;

}

private void hMaxSet(int size){

while( _h < size/9)

_h=3*_h+1;

}

private void insert( List list, int poz) {

Object temp,value=list.get(poz);

while( poz>=_h && _comparator.compare(value,temp=list.get(poz-_h)) < 0)

{list.set(poz,temp); poz-=_h; }

list.set(poz,value);

}

}

Dla tego ciągu liczba porównań wynosi O(n^3/2). Inne stosowane ciągi można znaleźć w książce Sedgewicka.

Dwa inne elementarne (klasyczne) algorytmy : sortowanie przez wstawianie (InsertSort) oraz sortowanie przez wybór (SelectSort).

1. Sortowanie przez wstawianie - sposób preferowany przez karciarzy

idea: 1. powtarzaj n - razy

weź kolejny element z ciągu nieuporządkowanego

wstaw go na właściwe miejsce w ciągu uporządkowanym

2. Sortowanie przez wybór

idea: 1. powtarzaj n - razy

zabierz najmniejszy element z ciągu nieuporządkowanego

wpisz go na koniec ciągu już uporządkowanego

Są to dwa bardzo proste, ale wolne (złożoność kwadratowa) algorytmy - stosowane często do niewielkich ciągów. Mimo podobnej budowy mają bardzo różne własności (jakie ? patrz literatura lub słuchaj wykładu).

Przykładowe realizacje:

package sorting;

import lists.List;

public class InsertSort implements ListSorter {

private final Comparator _comparator;

public InsertSort(Comparator comparator) { _comparator = comparator; }

public List sort(List list) {

for (int i = 1; i < list.size(); ++i) {

Object value = list.get(i),temp;

int j;

for (j = i; j > 0&& _comparator.compare(value, temp=list.get(j - 1))< 0; --j)

list.set(j,temp);

list.set(j, value);

}

return list;

}

}

Jak widać algorytm jest bardzo prosty, nie potrzebuje dodatkowej pamięci. Jest jednak wolny ( dużo porównań i tyle samo przepisań ). Silnie zależy od natury porządkowanego ciągu (lubi uporządkowane ciągi ), zachowuje przy tym naturalną kolejność elementów równych. Można poprawić jego efektywność przez zmniejszenie liczby porównań (wyszukiwanie binarne).

package sorting;

import lists.List;

public class SelectSort implements ListSorter {

private final Comparator _comparator;

public SelectSort(Comparator comparator) { _comparator = comparator; }

public List sort(List list) {

int size = list.size();

for (int slot = 0; slot < size - 1; ++slot) {

int smallest = slot;

for (int check = slot + 1; check < size; ++check)

if (_comparator.compare(list.get(check), list.get(smallest)) < 0)

smallest = check;

swap(list, smallest, slot);

}

return list;

}

private void swap(List list, int left, int right) {

if (left != right) { // podejście optymisty

Object temp = list.get(left);

list.set(left, list.get(right));

list.set(right, temp);

}

}

}

Prosty, wolny (ale ma najmniejszą możliwą liczbę przepisań) ,nie zależy od uporządkowania danych, nie jest stabilny - czyli nie zachowuje kolejności elementów równych. Można go przyspieszyć znajdując jednocześnie elementy maks i min (szybciej można znaleźć maks i min jednocześnie niż szukając ich po kolei) wystarczy 1.5n porównań zamiast 2n.

Złożone algorytmy sortowania (liniowo-logarytmiczne) : sortowanie szybkie (QuickSort) sortowanie przez scalanie (MergeSort) oraz sortowanie stogowe (HeapSort).

Sortowanie szybkie

Opracowany w 1962 roku przez Hoare'a, jest jednym z najlepiej poznanych (matematycznie) algorytmów. Oparty jest na zasadzie "divide et impera". Jej sens jest następujący: Aby rozwiązać problem wielkości N, rozwiąż rekurencyjnie dwa podproblemy wielkości N/2 i połącz ich wyniki by otrzymać rozwiązanie całego problemu.

Idea algorytmu jest następująca :

1. wybierz dowolny element z porządkowanego ciągu - X

2. podziel ciąg na podciąg zawierający elementy mniejsze od X i drugi zawierający pozostałe

3. tak samo posortuj pierwszy podciąg

4. posortuj drugi podciąg tą samą metodą

5.połącz rozwiązania

Sortowanie przez scalanie

idea : 1. podziel ciąg na dwa podciągi

2. uporządkuj pierwszy podciąg tą samą metodą

3. uporządkuj drugi podciąg tą samą metodą

4. połącz podciągi zachowując uporządkowanie

Przykładowe realizacje algorytmu szybkiego sortowania ( różnią się sposobem podziału na podciągi):

• podział jednostronny zaproponowany przez Lomuto ( najprostszy)

package sorting;

import lists.List;

public class QuickSort implements ListSorter {

private final Comparator _comparator;

public QuickSort(Comparator comparator) { _comparator = comparator; }

// wynikiem jest posortowana oryginalna lista

public List sort(List list) {

quicksort(list, 0, list.size() - 1);

return list;

}

private void quicksort(List list, int startIndex, int endIndex) {

if (endIndex > startIndex) {

int partition = partition(list, startIndex, endIndex);

quicksort(list, startIndex, partition );

quicksort(list, partition + 1, endIndex);

}

}

// podział według Lomuto

private int partition(List list, int left, int right) {

//jako element dzielący bierzemy ostatni

Object value=list.get(right);

int i=left-1;

while (left <= right){

if( _comparator.compare(list.get(left), value) <= 0)

swap(list, ++i,left);

++left;

}

return i<right ? i :i-1;

}

private void swap(List list, int left, int right) {

if (left != right) {

Object temp = list.get(left);

list.set(left, list.get(right));

list.set(right, temp);

}

}

}

• podział dwustronny ( szybszy ale bardziej skomplikowany) - lekko zmodyfikowana wersja Harrisa i Rossa ( styl !!)

// tylko metody które uległy zmianie

private void quicksort(List list, int startIndex, int endIndex) {

if (endIndex > startIndex) {

//jako element dzielący bierzemy ostatni

Object value=list.get(endIndex);

int partition = partition(list, value, startIndex, endIndex - 1);

if (_comparator.compare(list.get(partition), value) < 0)

++partition;

swap(list, partition, endIndex);

quicksort(list, startIndex, partition - 1);

quicksort(list, partition + 1, endIndex);

}

}

//styl!!

private int partition(List list, Object value, int left, int right) {

while (left < right) {

if( _comparator.compare(list.get(left), value) < 0)

{++left; continue;}

if(_comparator.compare(list.get(right), value) >= 0)

{--right; continue;}

swap(list, left, right); ++left;

}

return left;

}

• poprawiona wersja ( w porządnym strukturalnym stylu)

private void quicksort(List list, int startIndex, int endIndex) {

if (endIndex > startIndex) {

//jako element dzielący bierzemy ostatni

int partition = partition(list, startIndex, endIndex);

quicksort(list, startIndex, partition - 1);

quicksort(list, partition + 1, endIndex);

}

}

private int partition(List list, int left, int right) {

Object value=list.get(right);

int i=left-1,j=right;

while (i < j) {

while( _comparator.compare(list.get(++i), value) < 0);

while( (j>left) &&_comparator.compare(list.get(--j), value) > 0);

if( i < j)

swap(list, i, j);

}

swap(list,i,right);

return i;

}

Program jest prosty, bardzo szybki, potrzebuje niestety pamięci dla wywołań rekurencyjnych ( można zmniejszyć głębokość rekurencji przez odpowiednie modyfikacje, albo zrealizować wersję iteracyjną ), Jest jednak silnie zależny od początkowego uporządkowania ciągu (paradoksalnie, najgorszym przypadkiem jest ciąg już uporządkowany; również gdy wartości wielu elementów się powtarzają działa wolno).

Możliwości usprawnień:

1. efektywność tego algorytmu jest uzależniona od równomierności i szybkości podziału na podciągi - przegląd różnych metod podziału można znaleźć w {Bentley J. - „Perełki oprogramowania”]

2. QuickSort jest wyraźnie lepszy od innych przy długich ciągach, stąd pomysł aby przerywać rekurencję przy ciągach krótszych od M, a następnie wykorzystać prosty algorytm do ostatecznego posortowania (ciąg jest już prawie uporządkowany, więc dobry będzie InsertSort)

3. Można pozbyć się rekurencji używając własnego stosu do zapamiętania ciągów do posortowania, jeśli zastosujemy zasadę „odkładaj na stos dłuższy z podciągów, a krótszy obsłuż od razu” to zapewnimy sobie co najwyżej logarytmiczna wysokość stosu (normalnie może być liniowa - w najgorszym przypadku)

Prosta rekurencyjna realizacja algorytmu sortowania przez scalanie ( wersja zstępująca - podział ciągu na coraz mniejsze podciągi , a następnie ich stopniowe scalanie) :

package sorting;

import iterators.Iterator;

import lists.ArrayList;

import lists.List;

public class MergeSort implements ListSorter {

private final Comparator _comparator;

public MergeSort(Comparator comparator) { _comparator = comparator; }

// wynikiem jest nowa lista

public List sort(List list)

{ return mergesort(list, 0, list.size() - 1); }

private List mergesort(List list, int startIndex, int endIndex) {

if (startIndex == endIndex) {

List result = new ArrayList();

result.add(list.get(startIndex));

return result;

}

int splitIndex = startIndex + (endIndex - startIndex) / 2;

return merge(mergesort(list, startIndex, splitIndex),

mergesort(list, splitIndex + 1, endIndex));

}

private List merge(List left, List right) {

List result = new ArrayList();

Iterator l = left.iterator(); Iterator r = right.iterator();

l.first(); r.first();

while (!l.isDone() && !r.isDone()) {

if (_comparator.compare(l.current(), r.current()) <= 0)

{ result.add(l.current()); l.next(); }

else { result.add(r.current()); r.next(); }

}

while(!l.isDone())

{ result.add(l.current()); l.next(); }

while(!r.isDone())

{ result.add(r.current()); r.next(); }

return result;

}

}

Można zastosować iteracyjny algorytm wstępujący (podstawowy jest zstępujący) : podziel listę na listy jednoelementowe i umieść je w kolejce, następnie do uzyskania jednej listy wykonuj DoKolejki(Merge(Zkolejki,Zkolejki)) - w bardziej rozbudowanej wersji możemy w kolejce umieszczać nie pojedyncze elementy a serie (już uporządkowane podciągi kolejnych elementów) - wymaga to tylko przebudowy metody createQueue.

package sorting;

import iterators.Iterator;

import queues.*;

import lists.List;

public class IterativeMergeSort implements ListSorter {

private final Comparator _comparator;

public IterativeMergeSort(Comparator comparator) { _comparator = comparator; }

public List sort(List list)

{ return mergeSublists(createQueue(list)); }

private List mergeSublists(Queue q)

while (q.size() > 1)

q.enqueue(mergePair((List)q.dequeue(),(List)q.dequeue());

return (List)q.dequeue();

}

private Queue createQueue(List list) {

Queue result = new ListFifiQueue();

Iterator i = list.iterator();

i.first();

while (!i.isDone()) {

List singletonList = new ArrayList(1);

singletonList.add(i.current());

result.enqueue(singletonList);

i.next();

}

return result;

}

private List mergePair(List left, List right) {

List result = new ArrayList(left.size()+right.size());

Iterator l = left.iterator(); Iterator r = right.iterator();

l.first(); r.first();

while (!l.isDone() && !r.isDone()) {

if (_comparator.compare(l.current(), r.current()) <= 0)

{ result.add(l.current()); l.next(); }

else { result.add(r.current()); r.next(); }

}

while(!l.isDone())

{ result.add(l.current()); l.next(); }

while(!r.isDone())

{ result.add(r.current()); r.next(); }

return result;

}

}

Sortowanie stogowe

Opis stogu i definicje metod realizujących działania na stogowej kolejce priorytetowej - (będzie) można znaleźć w wykładzie o kolejkach priorytetowych.

package sorting;

import iteration.Iterator;

import lists.ArrayList;

import lists.List;

import queues.HeapPriorityQueue;

import queues.Queue;

public class HeapSort implements ListSorter {

private final Comparator _comparator;

public HeapSort(Comparator comparator) {_comparator = comparator;}

public List sort(List list) {

Queue queue = createPriorityQueue(list);

List result = new ArrayList(list.size());

while (!queue.isEmpty()) {

result.add(queue.dequeue());

}

return result;

}

private Queue createPriorityQueue(List list) {

Comparator comparator = new ReverseComparator(_comparator);

Queue queue = new HeapPriorityQueue(comparator);

Iterator i = list.iterator();

i.first();

while (!i.isDone()) {

queue.enqueue(i.current());

i.next();

}

return queue;

}

}

Jeden z szybszych (ale wolniejszy od sortowania szybkiego) algorytmów (złożoność O(N*log N)),w porównaniu do najbardziej znanego sortowania szybkiego nie jest rekurencyjny (łatwiej go analizować), nie potrzebuje dodatkowej pamięci (rekurencja zawsze jej zużywa sporo) i nie jest wrażliwy na uporządkowanie danych wejściowych. Można go usprawnić optymalizując metody obsługi stogu, ale pogarsza się w ten sposób jego czytelność. Czy to się opłaca zależy od stopnia przyspieszenia i potrzeb.

1. można przyspieszyć fazę budowy stogu ( do O(n)) - przez opuszczanie kolejnych elementów od (n div 2) do 0 na dół

2. można zmniejszyć liczbę porównań w fazie rozbierania stogu wykorzystując spostrzeżenie Floyda, że ostatni element wstawiany w miejsce korzenia prawie zawsze opada na dno stogu, będzie więc szybciej jeżeli będziemy schodzić od wierzchołka do dna przesuwając w górę większego z synów ( na każdym poziomie), na wolne miejsce wstawiamy ostatni element stogu i przesuwamy go WGórę (rzadko zachodzi taka potrzeba)

Zadania :

17. Przeanalizuj zachowanie poszczególnych algorytmów sortowania przy porządkowaniu ciągu liter SORTOWANIE JEST PROSTE , zwróć uwagę na liczbę porównań i przepisań oraz stabilność.

18. Na wykładzie przedstawiono uniwersalne algorytmy (umożliwiające sortowanie list bez względu na ich implementację). Zaproponuj bezpośrednie ( definiując odpowiednie struktury danych i potrzebne metody w jednej klasie ) implementacje algorytmów. Który sposób daje prostszy kod ? Co z efektywnością ?

19. Jeśli znamy kryterium początkowego sortowania można łatwo ( przez wykorzystanie odpowiedniego komparatora złożonego) doprowadzić do stabilności każdego z algorytmów sortowania. Czy można zaproponować uniwersalne rozwiązanie zapewniające zachowanie stabilności ?

Algorytmy sortowania specyficznych typów danych - bez porównywania elementów.

Sortowanie przez rozdział

Stosowany wtedy gdy porządkowane elementy (ich klucze) pochodzą z niezbyt dużego zbioru z wyznaczonym porządkiem liniowym . Załóżmy że klucze mają wartości liczbowe od 1 do M. Elementów do uporządkowania jest N. Zazwyczaj N >> M. Utwórzmy strukturę M kolejek.

idea: 1. powtarzaj n - razy

weź kolejny element i umieść go w kolejce wyznaczonej przez wartość klucza

(jeśli klucz ma wartość i to w i-tej kolejce)

2. wyprowadź (połącz) wszystkie kolejki

1 - kubełkowe (BucketSort) [Aho,Banachowski]

Stosowane gdy wartości porządkowanych elementów pochodzą ze skończonego zbioru wartości np 1 .. M. Wykorzystując kolejkę priorytetową z ograniczonym zbiorem wartości priorytetów (patrz wykład o kolejkach) możemy zapisać następujący algorytm (zakładamy, że najmniejsza wartość elementu daje najwyższy priorytet):

1. for (i =0; i<n; i++) DoKolejki(el[i]);

2. for (i=0; i<n; i++) ZKolejki(element)

Drukuj(element)

Gdy stosujemy ten algorytm do porządkowania tablicy zużywamy dużo dodatkowej pamięci (tyle ile zajmuje tablica + struktura kolejki), z tego względu algorytm nadaje się bardziej do sortowania list.

2 - wielolistowe (uogólnienie kubełkowego) [Banachowski]

W poprzednim przypadku mieliśmy do czynienia ze skończonym zbiorem wartości elementu. Rozważmy ciąg w którym elementy mają ograniczone wartości np. 0<=el < X, ale są liczbami rzeczywistymi (zbiór możliwych wartości jest nieskończony). Możemy wówczas wykorzystać tablicę M kolejek priorytetowych (o nieskończonym zbiorze wartości priorytetów (p.wykł. 3).

1. for (i=0; i<n; i++)

pr=floor (el[i]/X*M)

DoKolejki(pr,el[i])

2. for (pr=0; pr <M;pr++)

while (! PustaKolejka(pr))

ZKolejki(pr,elem)

Drukuj(elem)

Oba algorytmy są bardzo szybkie. Ciekawe, że w alg .1 nie wykonuje się żadnych porównań (a w 2 stosunkowo niewiele - przy wstawianiu do kolejki)

3 - pozycyjne (RadixSort) [Aho]

Sytuacja jest bardziej skomplikowana gdy klucz elementu jest określony przez ciąg P wartości z zakresu 0 : M-1.

Możemy wykorzystać tablicę M zwykłych (FIFO) kolejek. Zakładając że mamy procedurę PolaczKolejki, która tworzy listę dołączając na jej koniec kolejne kolejki od 1 do P otrzymujemy następujący algorytm :

1. for( nrpoz=P; nrpoz >=0; nrpoz--)

for( i= 0; i<N ;i++)

DoKolejki(el[i].klucz[nrpoz],el[i])

PolaczKolejki

UWAGA: oczywiście klucze (w alg. 1 i 3) nie muszą być liczbami całkowitymi (przyjęto tak dla uproszczenia), co więcej zakresy wartości dla poszczególnych pozycji klucza (alg. 3) mogą być różne.

Sortowanie przez zliczanie

idea: dla każdego elementu ciągu

oblicz ile jest elementów od niego mniejszych ,

umieść element na wyznaczonej w ten sposób pozycji ciągu wynikowego.

Uwaga: naiwna realizacja tego algorytmu daje złożoność O(n²)

Realizacja algorytmu sortowania przez zliczanie (CountingSort) [Cormen]

Zakładamy, że każdy z n sortowanych elementów jest liczbą całkowitą z przedziału od 0 do K-1. Dane są umieszczone w tablicy A, wynik zapisujemy w tablicy C, używamy również pomocniczej tablicy liczników B.

void CountingSort(Tablica a, Tablica c, int n)

{ int b[K],i;

for(i=0;i<K;i++) b[i]=0;

for(i=0; i<n;i++) b[a[i]]++;

for( i=1;i<n;i++) b[i]+=b[i-1];

for (i=n-1;i>=0;i--) c[(b[a[i]]--]=a[i];

}

Jest to stabilny algorytm o złożoności O(n+k).

Sortowanie zewnętrzne - przeprowadzane bezpośrednio na danych umieszczonych w plikach.

Algorytmy tej klasy (wymienione poniżej) nie będą omawiane na wykładzie (ich szczegółowy opis można znaleźć w [Wirth "Algorytmy + Struktury Danych = Programy]). Dlaczego ? Algorytmy te (co prawda efektywne ale dość skomplikowane) powstały przy założeniu, że sortowany ciąg znajduje się w pliku o dostępie sekwencyjnym (jego elementy można odczytywać tylko kolejno ) i jest na tyle duży, że nie mieści się w całości w pamięci operacyjnej programu. Od czasu ich powstania sytuacja się nieco zmieniła :

1. znacznie zwiększyła się pamięć operacyjna dostępna dla programu,

2. używane pliki pozwalają na dostęp bezpośredni (w dowolnej kolejności - Seek) do ich elementów.

Czynnik drugi pozwala efektywnie wykorzystywać pliki indeksowe (specjalne pliki pokazujące uporządkowanie elementów pliku głównego). Przykład wykorzystania pliku indeksowego zostanie omówiony później.

Z kolei zwiększenie pamięci powoduje, że większość wykorzystywanych przez nas plików mieści się w pamięci, jeśli nie to jest duże prawdopodobieństwo, że zmieści się struktura zawierająca tylko klucz (zazwyczaj stanowi on niewielką część elementu pliku ) i położenie elementu w pliku (numer rekordu ) - wówczas wystarczy posortować taką strukturę i zgodnie z uporządkowaniem przepisać plik.

1 Sortowanie przez łączenie proste

2 Sortowanie przez łączenie naturalne

3 Sortowanie przez wielokierunkowe łączenie wyważone

4 Sortowanie polifazowe

Temat 7. Kolejki priorytetowe.

Jest to najbardziej ogólny rodzaj kolejek. Spośród elementów stojących w kolejce pobierany jest element o najwyższym priorytecie, a przy równych priorytetach ten element który wcześniej stanął w kolejce. Zwykła kolejka może być traktowana jako kolejka priorytetowa, w której priorytet jest określony przez czas wejścia do kolejki. Implementacja kolejki zależy od charakteru zbioru priorytetów.

a)- z nieograniczonym zbiorem wartości priorytetów

• nieuporządkowane

wstawianie na koniec kolejki (złożoność O(1))

usuwanie elementu o najwyższym priorytecie (pierwszego z równych) (złożoność O(N))

• uporządkowane, wykorzystujące :

-- uporządkowaną listę lub tablicę

usuwanie z początku kolejki (złożoność O(1))

wstawianie na właściwe miejsce (za ostatni o takim samym priorytecie) ( złożoność O(N))

• stóg ( złożoność wstawiania i pobierania O(log N))

b)- z priorytetami o wartościach wybranych z niewielkiego zbioru.

W tym wypadku wykorzystujemy tablicę zwykłych kolejek (dla każdego priorytetu osobna).

Implementacja kolejki bazującej na liście nieuporządkowanej :

package queues;

import lists.LinkedList;

import lists.List;

import sorting.Comparator;

public class UnsortedPriorityQueue implements Queue {

private final List _list;

private final Comparator _comparator; //do ustalenia priorytetu

public UnsortedPriorityQueue(Comparator comparator) {

_comparator = comparator;

_list = new LinkedList();

}

public void enqueue(Object value)

{ _list.add(value); }

public Object dequeue() throws EmptyQueueException {

if (isEmpty()) throw new EmptyQueueException();

return _list.delete(getIndexOfLargestElement());

}

private int getIndexOfLargestElement() {

int result = 0;

for (int i = 1; i < _list.size(); ++i)

if (_comparator.compare(_list.get(i), _list.get(result)) > 0)

result = i;

return result;

}

public void clear()

{ _list.clear(); }

public int size()

{ return _list.size(); }

public boolean isEmpty()

{ return _list.isEmpty();}

}

Implementacja wykorzystująca listę uporządkowaną :

package queues;

import lists.LinkedList;

import lists.List;

import sorting.Comparator;

public class SortedPriorityQueue implements Queue {

private final List _list;

private final Comparator _comparator;

public SortedPriorityQueue(Comparator comparator) {

_comparator = comparator;

_list = new LinkedList();

}

public void enqueue(Object value) {

int pos = _list.size();

while (pos > 0 && _comparator.compare(_list.get(pos - 1), value) > 0)

--pos;

_list.insert(pos, value);

}

public Object dequeue() throws EmptyQueueException {

if (isEmpty()) throw new EmptyQueueException();

return _list.delete(_list.size() - 1);

}

public void clear()

{ _list.clear(); }

public int size()

{ return _list.size();}

public boolean isEmpty()

{ return _list.isEmpty();}

}

Pojęcie stogu (Heap):

Stogiem zupełnym (stertą ) nazywamy takie drzewo binarne, które ma dwie własności:

• kształtu : jest pełnym drzewem, przy czym ostatni poziom jest zapełniany od lewej strony

• uporządkowania : węzeł jest zawsze większy od swoich potomków.

Najprościej jest realizować stóg w tablicy. Wówczas synami węzła i są węzły 2*i+1 oraz 2*(i+1), a ojcem węzła i jest węzeł (i-1)/ 2 .

Implementacja kolejki wykorzystującej stóg :

package queues;

import lists.ArrayList;

import lists.List;

import sorting.Comparator;

public class HeapPriorityQueue implements Queue {

private final List _list;

private final Comparator _comparator;

public HeapPriorityQueue(Comparator comparator) {

_comparator = comparator;

_list = new ArrayList();

}

public void enqueue(Object value) {

_list.add(value);

swim(_list.size() - 1);

}

//wynoszenie elementu w górę

private void swim(int index) {

int parent;

while(index != 0 &&

_comparator.compare(_list.get(index), _list.get(parent= (index - 1) / 2)) > 0)

{ swap(index, parent);

index=parent;

}

}

private void swap(int index1, int index2) {

Object temp = _list.get(index1);

_list.set(index1, _list.get(index2));

_list.set(index2, temp);

}

public Object dequeue() throws EmptyQueueException {

if (isEmpty()) throw new EmptyQueueException();

Object result = _list.get(0);

if (_list.size() > 1) {

_list.set(0, _list.get(_list.size() - 1));

sink(0);

}

_list.delete(_list.size() - 1);

return result;

}

// opuszczanie elementu w dół stogu

private void sink(int index) {

boolean isDone=false;

int child;

while(!isDone && (child=2*index+ 1 ) < _list.size()) {

if (child < _list.size()- 1 &&

_comparator.compare(_list.get(child), _list.get(child+1)) < 0)

++child;

if (_comparator.compare(_list.get(index), _list.get(child)) < 0)

swap(index, child);

else isDone=true;

}

}

public void clear()

{ _list.clear(); }

public int size()

{ return _list.size(); }

public boolean isEmpty()

{ return _list.isEmpty();}

}

Zadania :

20. Stóg wykorzystywany do sortowania stogowego można zbudować bez wykorzystania metody swim ( przesuwanie w górę). Jest to znacznie szybszy proces.Zaimplementuj odpowiednią metodę.

21. Flloyd zauważył, że można przyspieszyć usuwanie elementu kolejki stogowej przez modyfikację metody sink. Zaproponował żeby opuszczać element na sam dół stogu, a następnie jeśli trzeba to go podnieść na odpowiednią pozycję. Kiedy to podejście przynosi korzyść.

Temat 8. Tablice symboli (słowniki).

Słownik (inne nazwy to : tablica skojarzeniowa, tablica asocjacyjna, tablica indeksowana wartością klucza, odwzorowanie, mapa - bezmyślne przetłumaczenie angielskiego terminu map czyli odwzorowanie) - typ abstrakcyjny z określonymi operacjami :

JestElementem - czy dany element występuje w słowniku albo wyszukaj element o danym kluczu

Dodaj - dopisz element do słownika

Usun - usuń element ze słownika

Wybierz - k-ty co do wielkości element

Sortuj - wypisz wszystkie elementy w sposób uporządkowany

Połącz - połącz dwa słowniki w jeden

Należy pamiętać że podstawową operacją na typowym słowniku jest wyszukiwanie elementu; dodawanie i usuwanie albo nie występują, albo są wykonywane bardzo rzadko. Więc efektywność wyszukiwania decyduje o przydatności danej realizacji. Metody wyszukiwania elementu zależą od sposobu organizacji słownika. Klucze obiektów ( elementów ) występujących w słowniku nie mogą się powtarzać. Elementy występujące w słowniku mogą się składać albo z samego klucza (np. słownik słów kluczowych kompilatora, słownik do sprawdzania pisowni ) lub z klucza i danych (np. słownik polsko-angielski, encyklopedia, książka telefoniczna). Od typu elementu zależy sposób działania operacji JestElementem:

- tylko sprawdzenie gdy element ma tylko klucz

- zwrócenie wartości pola dane dla elementów zbudowanych z klucza i danych.

Operacja dodawania elementu do słownika jest wykonywana znacznie rzadziej. Tylko w specyficznych sytuacjach w czasie normalnej pracy (on-line) i wówczas jej efektywność jest istotna , zazwyczaj jednak jest wykonywana w trybie off-line i szybkość nie ma praktycznego znaczenia. Usuwanie elementu prawie zawsze jest wykonywane w trybie off-line.

Można wyróżnić trzy podstawowe klasy struktur służących do przechowywania elementów słownika :

1. ciąg nieuporządkowany ( tablica, plik lub lista)

2. tablica haszowana

3. ciąg uporządkowany (tablica, plik, lista, struktury drzewiaste).

Na początek zajmiemy się wyszukiwaniem na listach nieuporządkowanych i uporządkowanych.

Interfejs wyszukiwania :

package searching;

import lists.List;

public interface ListSearcher {

//zwraca pozycję obiektu na liście - jeśli jest

//jeśli nie to - (pozycja_wstawienia + 1)

// plus1 umożliwia wskazanie, że element powinien się znajdować na początku listy

public int search(List list, Object value);

}

Dla list nieuporządkowanych stosujemy wyłącznie proste przeszukiwanie liniowe ( złożonośc O(N)) .

Dla list uporządkowanych możemy zastosować :

- wyszukiwanie liniowe ( O(N)) , szybsze wykrywanie braku elementu w porównaniu do list nieuporządkowanych :

package searching;

import lists.List;

import sorting.Comparator;

public class LinearListSearcher implements ListSearcher {

private final Comparator _comparator;

public LinearListSearcher(Comparator comparator)

{ _comparator = comparator; }

public int search(List list, Object value) {

int cmp=0,i;

for (i=0; i<list.size() && (cmp = _comparator.compare(value, list.get(i)))>0; i++);

return i<list.size() && cmp ==0 ? i : -(i+1); //lista może być pusta

}

}

- wyszukiwanie binarne (złożoność O(log N)) :

idea :

Oznaczenia : k- klucz szukanego elementu

poc - pozycja lewego końca przeszukiwanego obszaru k(poc) klucz tej pozycji

kon - pozycja prawego końca k(kon) jej klucz

b - wyznaczony w danym kroku punkt podziału k(b) klucz

do b= (poc+kon) div 2

if ( k >k(b)) b+1 staje się lewym końcem nowego przedziału

else b staje się prawym końcem nowego przedziału

while ( poc >=kon)

sprawdź element na pozycji poc

implementacja iteracyjna (nieco inna wersja - dla optymistów )

package searching;

import lists.List;

import sorting.Comparator;

public class IterativeBinaryListSearcher implements ListSearcher {

private final Comparator _comparator;

public IterativeBinaryListSearcher(Comparator comparator)

{ _comparator = comparator; }

public int search(List list, Object value) {

int lower = 0;

int upper = list.size() - 1;

int index=0,cmp=0;

while (lower <= upper &&

(cmp = _comparator.compare(value, list.get(index=(lower + upper)/2)))!=0)

if (cmp < 0) upper = index - 1;

else lower = index + 1;

return lower<=upper && cmp==0 ? index : -(lower+1);

}

}

implementacja rekurencyjna

package searching;

import lists.List;

import sorting.Comparator;

public class RecursiveBinaryListSearcher implements ListSearcher {

private final Comparator _comparator;

public RecursiveBinaryListSearcher(Comparator comparator)

{ _comparator = comparator; }

public int search(List list, Object value)

{ return search(list, value, 0, list.size() - 1); }

// wersja dla miłośników instrukcji return ( moim zdaniem nienajlepsza )

private int search(List list, Object value, int lower, int upper) {

if (lower > upper) return -(lower + 1);

int index = (lower + upper) / 2;

int cmp = _comparator.compare(value, list.get(index));

if (cmp < 0) return search(list, value, lower, index - 1);

if (cmp > 0) return search(list, value, index + 1, upper);

return index;

}

}

Jeszcze szybsze jest wyszukiwanie interpolacyjne (stosowane gdy klucze mają rozkład równomierny)

do b= poc+(k-k(poc))/(k(kon)-k(poc))*(kon-poc)

if (k >k(b)) b+1 staje się lewym końcem nowego przedziału

else b staje się prawym końcem nowego przedziału

while (poc >=kon)

sprawdź element na pozycji poc

Złożoność log log(N) - czyli praktycznie stała.

Zadania :

22. Zaimplementuj wyszukiwanie binarne dokładnie według przedstawionej powyżej idei. Sprawdź swój algorytm dla wszystkich granicznych przypadków.

23. Zaimplementuj rekurencyjną wersję wyszukiwania liniowego. Chodzi wyłącznie o gimnastykę umysłu - staramy się unikać rekurencji o głębokości liniowej.

Drzewa : budowa i przetwarzanie.

Drzewo ukorzenione jest to graf skierowany, nie zawierający cykli i spełniający następujące warunki:

1.Istnieje dokładnie jeden wierzchołek (węzeł) do którego nie dochodzi żadna krawędź - korzeń drzewa

2.Dla każdego wierzchołka grafu istnieje droga ( jedyna) od korzenia do tego wierzchołka

3.Każdy wierzchołek nie będący korzeniem ma jedyną krawędź dochodzącą do niego.

Jeśli w grafie istnieje krawędź (gałąź) od węzła w do węzła v, to w nazywamy poprzednikiem ( przodkiem, ojcem ) v , a v nazywamy następnikiem (potomkiem, synem) w. Wierzchołek bez potomków nazywamy liściem. Wierzchołek mający co najmniej jednego potomka nazywamy węzłem wewnętrznym. Wierzchołek reprezentujący elementy nie występujące w drzewie (oznaczony przez NULL ) nazywamy węzłem zewnętrznym (w niektórych książkach te węzły są nazywane liśćmi) . Wierzchołek v razem z jego potomkami nazywamy poddrzewem o korzeniu v. Głębokość ( poziom ) wierzchołka v jest to długość drogi (liczba krawędzi) od korzenia do v (korzeń ma głębokość 0 ). Wysokość drzewa jest to maksymalna długość drogi od korzenia do liści (czyli największa z głębokości liści , wysokość drzewa pustego wynosi -1, a drzewa jednowęzłowego 0).

Drzewo uporządkowane - drzewo w którym następniki każdego wierzchołka są uporządkowane ( na rysunku - od lewej do prawej ).

W programowaniu najważniejsze znaczenie mają uporządkowane drzewa binarne. Binarne drzewo poszukiwań (Binary Search Tree) - drzewo uporządkowane spełniające warunki :

1. wśród następników każdego wierzchołka wyróżniamy lewy i prawy następnik

2. każdy wierzchołek ma co najwyżej jeden prawy i jeden lewy następnik

3. w lewym poddrzewie znajdują się wartości mniejsze od korzenia, a w prawym większe.

4. klucze się nie powtarzają.

Podstawowe działania na uporządkowanych drzewach binarnych (patrz BST.java).

Najprostsza postać węzła drzewa ( można ją wzbogacić o dodatkowe informacje) :

class Node{

Object value;

Node left;

Node right;

Node(Object x)

{ value=x; left = right = null; }

}

Do podstawowych działań na drzewach możemy zaliczyć :

1. Przechodzenie przez wszystkie wierzchołki drzewa (w określonej kolejności) - przetwarzanie całego drzewa

2. Wyszukiwanie - sprawdzanie czy w drzewie występuje węzeł o zadanym kluczu

3. Wstawianie - dołączanie nowego węzła do drzewa

4. Usuwanie węzła z drzewa.

1. Przechodzenie przez wszystkie wierzchołki drzewa (o korzeniu t ) :

Przejdź(Wsk t)

Przejdź(t->lewe);

przetwórz(t); // wykorzystaj węzeł t

Przejdź(t->prawe);

Ponieważ trzy czynności - przejdź lewe, przetwórz korzeń i przejdź prawe możemy ustawić na 6 różnych sposobów tyle też jest sposobów przechodzenia drzewa. Dla BST jest najważniejszy sposób pokazany wyżej ponieważ daje wierzchołki od najmniejszego do największego.

Przykład przechodzenia in-order (PLW) w celu pokazania struktury drzewa jest w BST.java ( metoda toString ).

2. Wyszukiwanie węzła (o zadanej wartości ) w drzewie . Jeśli węzła nie ma zwraca NULL.

public Object find(Object x)

{Node t = search(x);

return t !=null ? t.value : null;

}

private Node search(Object value) {

Node node = _root;

int cmp=0;

while (node != null &&(cmp = _comparator.compare(value, node.value))!=0)

node = cmp < 0 ? node.left : node.right;

return node;

}

Jest to przykład jednej z nielicznych iteracyjnych metod dla drzew.

3. Wstaw węzeł do drzewa .

Należy przeszukać drzewo, i jeśli dodawanego węzła w nim nie ma - dołączyć go (zawsze jako liść). Jeśli jest to zgłaszany jest wyjątek.

public void insert(Object x)

{ _root= insert(x,_root); }

protected Node insert(Object x, Node t) {

if(t== null) t=new Node(x);

else { int cmp=_comparator.compare(x,t.value);

if(cmp<0) t.left=insert(x,t.left);

else if(cmp>0) t.right=insert(x,t.right);

else throw new DuplicateItemException(x.toString());

}

return t;

}

4. Usuń węzeł (o podanej wartości ) z drzewa .

Znajdź węzeł w drzewie - możliwe są dwa przypadki

- węzła nie ma (błąd) - zgłaszany jest wyjątek

- węzeł jest - i tu rozróżniamy 3 przypadki:

- a) węzeł jest liściem - zwyczajnie go usuwamy

- b) ma tylko jednego syna - zastępujemy go lewym lub prawym poddrzewem

- c) ma dwóch synów (najgorszy przypadek )

• znajdujemy skrajnie lewy węzeł w prawym poddrzewie (bezpośredni następnik - może mięć co najwyżej jednego syna więc jest łatwy do usunięcia; można wybierać największy w lewym poddrzewie) ,zastępujemy nim usuwany węzeł i usuwamy go.

public void delete(Object x)

{_root=delete(x,_root); }

protected Node delete(Object x, Node t) {

if(t==null) throw new ItemNotFoundException(x.toString());

else { int cmp=_comparator.compare(x,t.value);

if(cmp<0) t.left=delete(x,t.left);

else if(cmp>0) t.right=delete(x,t.right);

else if(t.left!=null &&t.right!=null)

t.right=detachMin(t.right,t);

else t = (t.left != null) ? t.left : t.right;

}

return t;

}

//zastąp usuwany element jego następnikiem i usuń następnik

protected Node detachMin(Node t, Node del) {

if(t.left!=null) t.left=detachMin(t.left,del);

else {del.value=t.value; t=t.right;}

return t;

}

Drzewa BST wyradzają się przy nielosowej kolejności wstawiania elementów (np. uporządkowane).

Zbudowanie optymalnego (gwarantującego minimalną liczbę porównań) jest bardzo trudne - patrz Aho,Hopcroft,Ullman - "Projektowanie i analiza algorytmów komputerowych . Dlatego zazwyczaj zadowalamy się prawie optymalnymi drzewami gwarantującymi logarytmiczną wysokość (złożoność wyszukiwania).

1. drzewa wyważone AVL (Adelson-Velski, Landis) - dla każdego węzła wysokości poddrzew różnią się co najwyżej o 1. Stosunkowo proste działania (wystarczy dodać wskaźnik wyważenia). Gwarantowana wysokość 1.45log n.

2. inne : BB-drzewa (2-3 drzewa) , drzewa czerwono-czarne ( SBB drzewa, 2-3-4 drzewa) - obecnie najczęściej stosowane, opracowane przez Bayera.

Drzewa wyważone AVL (patrz AVL.java).

// nie będą omawiane na wykładzie ( lekko się zestarzały od 1962 roku

// zamiast nich będzie omówiona implementacja 2-3-4 drzew w postaci drzew czerwono-czarnych.

//aby ułatwić porównanie pozostawiam AVL w treści wykładu

Wyszukiwanie odbywa się jak w zwykłym drzewie BST. Wstawianie i usuwanie węzłów komplikują się, ponieważ trzeba kontrolować wyważenie i czasami przebudowywać drzewo. Wskaźnik wyważenia dla każdego z węzłów może przyjmować jedną z trzech wartości

L- lewe poddrzewo jest wyższe od prawego

R- oba drzewa mają tę samą wysokość

P- prawe poddrzewo jest wyższe

Przebudowa drzewa jest realizowana za pomocą rotacji - tym razem również podwójnych:

//Prosta zamiana węzła z jego lewym potomkiem

Node RotRight(Node t)

{ Node t1=t.left;t.left = t1.right; t1.right=t; return t1;}

// Prosta zamiana węzła z jego prawym potomkiem

Node RotLeft(Node t)

{ Node t1=t.right; t.right =t1.left; t1.left = t; return t1;}

//Podwójna rotacja LewaPrawa:

// 1. lewy potomek węzła ze swoim prawym potomkiem

// 2. węzeł z lewym potomkiem(po zamianie 1.)

Node RotLeftRight(Node t)

{ t.left = RotLeft(t.left); return RotRight(t);}

// rotacja PrawaLewa - Symetryczna do rotacji LewaPrawa

Node RotRightLeft(Node t)

{ t.right=RotRight(t.right); return RotLeft(t); }

Wstawianie elementu x do drzewa o korzeniu t , h - wskaźnik czy drzewo zmieniło wysokość , jeśli już był zgłaszany jest wyjątek.

Należy rozpatrzyć następujące przypadki w zależności od wskaźnika ojca wstawianego węzła przed wstawieniem ( zakładamy że nowy węzeł jest dołączany jako lewy syn - przy wstawianiu do prawego poddrzewa sytuacja jest w pełni symetryczna)

- P - oba poddrzewa wyrównują się, nowy wskaźnik ojca jest R

- R - urosło lewe poddrzewo ale warunek wyważenia jest zachowany nowy współczynnik ojca jest L

- L - najgorszy przypadek - urosło wyższe drzewo, należy przywrócić wyważenie, postępowanie zależy od

wyważenia lewego poddrzewa wyważanego węzła :

- L - prosta zamiana węzła z jego lewym potomkiem

- P lub R - podwójna zamiana (LewoPrawo)

1. lewy potomek z prawym potomkiem lewego potomka węzła

2. węzeł z lewym potomkiem (po zamianie 1.) }

W przypadkach R i L należy skontrolować wyważenie przodka wstawianego węzła.

Usuwanie węzła (parametry jak wyżej) odbywa się jak w BST plus wyważanie drzewa.

Tym razem poddrzewo mogło ulec skróceniu - łato zauważyć podobieństwo sytuacji : urosło lewe poddrzewo i prawe poddrzewo uległo skróceniu.

Podobnie jak przy wstawianiu sytuacja zależy od wyważenia ojca usuwanego węzła (do opisu przyjmijmy że usuwany węzeł był w lewym poddrzewie, jeśli usunęliśmy z prawego poddrzewa sytuacja jest symetryczna).

- L - wyższe drzewo uległo skróceniu, nowy wskaźnik - R

- R - skróciło się lewe poddrzewo ale warunek wyważenia jest zachowany nowy wskaźnik - P

- P - obcięte zostało niższe drzewo, trzeba przywrócić wyważenie, sprawdzamy wskaźnik wyważenia prawego

poddrzewa wyważanego węzła

- P lub R - prosta zamiana węzła z jego prawym potomkiem

- L - podwójna zamiana (PrawoLewo)

1. prawy potomek z lewym potomkiem prawego potomka

2. węzeł z prawym potomkiem

2-3-4 drzewa i ich implementacja w postaci drzew czerwono-czarnych przechylonych w lewo (LLRBTree Sedgevick 2007) (patrz LLRB.java).

Koncepcję 2-3-4 drzew opracował w 1972 roku Bayer. Są to prawie optymalne drzewa poszukiwań - gwarantują logarytmiczną złożoność wyszukiwania. W węźle może być zapisane do 3 elementów. Wszystkie liście są na tym samym poziomie.

• wyszukiwanie odbywa się podobnie jak w BST

• wstawianie zawsze do liścia; gdy liść jest 4-węzłem następuje jego podział i przeniesienie elementu dzielącego do ojca . Jest to bardzo kłopotliwe, więc częściej stosuje się eliminację 4-węzłów przy schodzeniu do liścia. Ciekawostka : drzewo rośnie w stronę korzenia.

• usuwanie jest bardziej złożone , należy rozróżnić dwie sytuacje :

• usuwanie z liścia ; czasem połączone z pożyczką elementu od sąsiedniego węzła lub połączeniem węzłów

• usuwanie z węzła wewnętrznego - zastępujemy usuwany element jego bezpośrednim następnikiem lub poprzednikiem (znajduje się on w liściu więc jest łatwy do usunięcia)

Bezpośrednia realizacja węzłów w postaci tablicy elementów byłaby bardzo nieefektywna, dlatego 2-3-4 drzewa implementuje się jako drzewa czerwono-czarne ( Guibas i Sedgewick 1978).

Jest prosty sposób przedstawienia 2-,3- i 4-węzłów za pomocą węzłów binarnych z dodanym polem koloru.

Własności drzew czerwono czarnych :

• każdy węzeł jest albo czerwony albo czarny

• korzeń i wszystkie węzły zewnętrzne są czarne

• jeśli węzeł jest czerwony to jego synowie są czarni ( nie ma dwóch czerwonych wezłów pod rząd)

• każda ścieżka od ustalonego węzła do liścia ma tyle samo czarnych węzłów.

Drzewa czerwono-czarne mimo dużej złożoności metod realizujących poszczególne działania (co jest spowodowane dużą liczbą różnych sytuacji) są powszechnie stosowane - ze względu na gwarantowaną logarytmiczną złożoność i szybkość działania. Dopiero Sedgewick w 2007 zaproponował ograniczenie sposobów przedstawienia węzłów co doprowadziło do znaczącego uproszczenia kodu - bez pogorszenia szybkości wyszukiwania. Opracowane przez niego LLRBTree (Left Lean Red Black Tree - drzewa czerwono-czarne przechylone w lewo ) dopuszczają występowanie 4-węzłów tylko chwilowo ( w czasie wykonywania operacji) i pozwalają na jedną reprezentację 3- węzłów. Przykładowa implementacja :

package rbtree;

public class LLRBTree<Elem extends Comparable<Elem>> {

static final boolean RED=true;

static final boolean BLACK =false;

private Node _root;

public LLRBTree()

{ _root=null;}

private boolean isRed( Node x)

{return x!= null && x.color==RED;}

public Elem find(Elem x)

{Node t = search(x);

return t !=null ? t.value : null;

}

private Node search(Elem value) {

Node node = _root;

int cmp=0;

while (node != null &&(cmp = value.compareTo(node.value))!=0)

node = cmp < 0 ? node.left : node.right;

return node;

}

private Node rotateL(Node t)

{ Node x=t.right;

t.right=x.left;

x.left=t;

x.color=t.color;

t.color=RED;

return x; }

private Node rotateR(Node t)

{ Node x=t.left;

t.left=x.right;

x.right=t;

x.color=t.color;

t.color=RED;

return x; }

private void colorFlip(Node t)

{t.color=!t.color; t.left.color=!t.left.color; t.right.color=!t.right.color; }

public void insert(Elem x)

{ _root= insert(x,_root); _root.color=BLACK;}

protected Node insert(Elem x, Node t) {

if(t== null) t=new Node(x);

else { int cmp=x.compareTo(t.value);

if(isRed(t.left) && isRed(t.right))

colorFlip(t);

if(cmp<0) t.left=insert(x,t.left);

else if(cmp>0) t.right=insert(x,t.right);

else throw new RuntimeException("Duplicate "+x.toString());

t=fixUp(t);

}

return t;

}

private Node fixUp(Node t)

{ if(isRed(t.right))

t=rotateL(t);

if(isRed(t.left) && isRed(t.left.left))

t=rotateR(t);

if(isRed(t.left) && isRed(t.right))

colorFlip(t);

return t; }

private Node moveRedR( Node t)

{ colorFlip(t);

if(isRed(t.left.left))

{ t=rotateR(t); colorFlip(t); }

return t; }

private Node moveRedL( Node t)

{ colorFlip(t);

if(isRed(t.right.left))

{ t.right=rotateR(t.right); t=rotateL(t); colorFlip(t);}

return t;}

public void delete(Elem x)

{_root=delete(x,_root);

if(_root!=null) _root.color=BLACK;}

protected Node delete(Elem x, Node t) {

if(t==null) throw new RuntimeException("Not found "+x.toString());

else { int cmp=x.compareTo(t.value);

if(cmp<0)

{ if(!isRed(t.left) && !isRed(t.left.left))

t=moveRedL(t);

t.left=delete(x,t.left);

}

else{if( isRed(t.left)) t=rotateR(t);

if(x.compareTo(t.value)==0&&t.right == null) return null;

else { if(!isRed(t.right) && !isRed(t.right.left))

t=moveRedR(t);

if(x.compareTo(t.value)>0)

t.right=delete(x,t.right);

else t.right=detachMin(t.right, t);

}

}

}

return fixUp(t);

}

protected Node detachMin(Node t, Node del) {

if(t.left==null) {del.value=t.value; t=null;}

else { if(!isRed(t.left) && !isRed(t.left.left))

t=moveRedL(t);

t.left=detachMin(t.left,del);

t=fixUp(t); }

return t;

}

public String toString()

{return toString(_root,0);}

private String toString(Node t,int pos) {

String result="";

String spaces=" ";

if(t!=null) result=result+toString(t.right,pos+4)+spaces.substring(0,pos)

+String.format("%s%s",t.value,(t.color ? "/R" :"/B"))+toString(t.left,pos+4);

else result=result+String.format("%n");

return result;

}

class Node{

Elem value;

Node left;

Node right;

boolean color;

Node(Elem x)

{ value=x; left = right = null; color = RED;}

}

}

B-drzewa.

Są to zrównoważone drzewa wielokierunkowe - naturalne uogólnienie 2-3-4 drzew.

Stosowane są w przypadku dużych słowników - nie mieszczących się w pamięci operacyjnej. Węzły tych drzew zawierają więcej niż jeden obiekt (element słownika ) co zmniejsza liczbę odczytów z dysku, przez zmniejszenie

głębokości drzewa, a przez to przyspiesza działanie ( odczyt z dysku odbywa się zazwyczaj większymi porcjami więc odczytanie 1 bajta i odczytanie kilkuset bajtów zabiera praktycznie tyle samo czasu).

Ponieważ różni autorzy przedstawiają nieco różne warianty tych drzew, wybrałem rozwiązania przedstawione przez Cormena ("Wprowadzenie do algorytmów").

Węzeł (strona) B-drzewa rzędu M zawiera od M-1 do 2M-1 kluczy (czyli ma od M do 2M potomków, lub jest liściem ). Wyjątkiem jest korzeń (może mieć mniej kluczy). Wszystkie liście drzewa leżą na tym samym poziomie.

Węzeł B-drzewa rzędu M ma następującą strukturę :

class Node

{ static int Size=... // 2* (rząd drzewa)-1

int numItems; // liczba kluczy na stronie

Object [ ]itemArray =new Object[size]; // tablica kluczy (mogą być kompletne obiekty)

Node[ ] childArray =new Node[size+1] // tablica potomków i-ty element to strona

} // zawierająca klucze mniejsze itemArray[i]

Klasa BTree ma tylko pole root - korzeń drzewa.

Wygodnie jest przyjąć, że puste drzewo to drzewo złożone z pustej (n==0) strony korzenia.

Przechodzenie przez drzewo w kolejności rosnących kluczy ( np. w celu wydrukowania wartości) :

void printBTree ( Node t)

{ for (int i=0; i< t.numItems;i++)

{ if ( t.childArray[i]!=null ) printBTree ( t.childArray[i]);

print( t.itemArray[i]);

}

}

Szukanie obiektu o kluczu k w B-drzewie o korzeniu t (sprawdzanie czy jest) :

boolean ( Node t , Object item)

{ int i=0;

int cmp=0;

while ( i<t.numItems && ((cmp=comparator.compare(item,t.itemArray[i])) >0))

i++; // szukaj klucza >=item

if( i<t.numItems && cmp= =0) return true; // znaleziono

if (t.childArray[i]==null) return false; // doszliśmy do liścia, item nie ma

return find(t.childArray[i],item); // szukaj na stronie potomnej

}

Wstawianie nowego obiektu na stronę C. Możliwe są dwa przypadki:

1. Na stronie jest mniej niż 2M-1 kluczy - wstawiamy nowy klucz na odpowiednie miejsce tablicy kl;

2. Strona jest pełna (zawiera 2M-1 kluczy)

- przydzielamy pamięć na nową stronę D

- rozdzielamy 2M kluczy równo (prawie) na strony C i D, klucz środkowy wstawiamy do strony będącej teraz ojcem stron C i D (powtarzamy krok 2 aż do usunięcia przepełnienia stron).

Ponieważ przenoszenie klucza w górę jest dość kłopotliwe, zastosujemy inne rozwiązanie. Ilekroć przy wyszukiwaniu miejsca wstawienia mamy wejść na pełną stronę od razu ją dzielimy. Fizyczne wstawianie odbywa się wtedy na niepełną stronę.

Usuwanie elementu nie jest proste ze względu na możliwość powstania niedomiaru (strony mającej mniej niż M-1 kluczy) , mamy trzy główne przypadki :

1. Usuwamy klucz k ze strony t będącej liściem (jest to zwykłe usunięcie elementu z tablicy)

2. Usuwamy klucz k ze strony t nie będącej liściem.

1. Niech y będzie synem t poprzedzającym k. Jeśli y ma co najmniej M kluczy, to w poddrzewie o korzeniu y wyznacz poprzednik k' klucza k. Rekurencyjnie usuń k" i w węźle t zastąp k przez k'.

2. Symetrycznie, jeśli syn z występujący po k w węźle t, ma co najmniej M kluczy, to wyznacz następnik k' dla k w poddrzewie o korzeniu z . Rekurencyjnie usuń k' i zastąp w x k przez k'.

3. Jeśli obaj synowie y i z mają tylko po M-1 kluczy, to przenieś k i wszystko z węzła z do y. Zwolnij pamięć przydzieloną z i usuń rekurencyjnie k z y.

3. Jeśli klucz k nie występuje w wewnętrznym węźle t, to wyznacz korzeń ws[i] poddrzewa w którym musi znajdować sie k. Jeśli ws[i] ma tylko M-1 węzłów to wykonaj podkrok 3a lub 3b aby zapewnić, że zejdziemy rekurencyjnie do węzła z co najmniej M kluczami. Usuń rekurencyjnie k z właściwego poddrzewa.

1. jeśli w węźle ws[i] jest tylko M-1 kluczy, ale jeden z jego sąsiednich braci ma >=M kluczy, to umieść w ws[i] dodatkowy klucz, przesuwając odpowiedni klucz z t, a w jego miejsce przenosząc klucz z lewego lub prawego brata - tego który ma >=M kluczy (trzeba również przenieść odpowiadający mu wskaźnik na syna)

2. jeśli ws[i] i sąsiedni bracia mają po M-1 kluczy to połącz ws[i] z jednym z sąsiednich braci, przesuwając odpowiedni klucz z x do nowo powstałego węzła (zwolnij pamięć opróżnionej strony).

Tu są (a może będą) realizacje odpowiednich funkcji.

Przedstawione wcześniej 2-3-4 drzewa są odpowiednikami BDrzewa rzędu 2.

Drzewa pozycyjne.

Na koniec przedstawiam przykład pozycyjnego (cyfrowego) drzewa poszukiwań - w literaturze można znaleźć inne drzewa pozycyjne : TRIE, PATRICIA, TST itd.

Mogą one być stosowane gdy klucz jest ciągiem symboli z niewielkiego alfabetu. Np. ciąg liter, ciąg cyfr, ciąg niewielkich liczb, czy też kreska-kropka (jak w alfabecie Morse'a). Zakładamy, że łatwo możemy przetworzyć każdy symbol na wartość liczbową .

Korzeń pustego drzewa stanowi węzeł bez wartości (dane = wartość pusta) który wszystkie adresy ma ustawione na NULL.

Jak wyglądają poszczególne działania na takim drzewie ?

1. Szukanie węzła o danym kluczu (kl) w drzewie o korzeniu t:

Schodzimy po gałęziach drzewa wyznaczonych przez kolejne pozycje klucza - możliwe są trzy zakończenia :

1. doszliśmy do końca drzewa, a nie wykorzystaliśmy wszystkich pozycji klucza

- węzła o takim kluczu nie ma w drzewie

2. Wyczerpaliśmy klucz (sprawdzamy pole dane w osiągniętym węźle)

a. ma wartość - jest to szukany węzeł

b. ma wartość nieokreśloną (0) nasz klucz jest przedrostkiem klucza istniejącego w drzewie węzła ale

sam nie ma wartości

2. Wstawianie węzła o kluczu kl do drzewa o korzeniu t.

Najpierw schodzimy po drzewie ( tak jak przy szukaniu ):

1.Skończyl się klucz na węźle w

a. w ma ustawioną wartość - węzeł już jest w drzewie (błąd ?)

b. węzeł nie ma wartości - wpisujemy do węzła wskaźnik wartości

2.Skończyło się drzewo - musimy wytworzyć ciąg węzłów odpowiadający niewykorzystanym pozycjom klucza (wszystkie oprócz ostatniego maja wartość pusta, ostatni ma wartość )

3. Usuwanie z drzewa o korzeniu t węzła o kluczu kl. (zakładamy że węzeł jest w drzewie)

Najpierw schodzimy do usuwanego węzła (rekurencyjnie) i ustawiamy mu wartość pusta. Wracając sprawdzamy czy dany węzeł jest liściem z pustą wartością : jeśli tak to go usuwamy (nie wolno usunąć korzenia ).

Charakterystyczną cechą drzew cyfrowych jest to że czas znalezienia węzła nie zależy od liczby wierzchołków a jedynie od długości klucza (zazwyczaj jest mniejszy niż w drzewach binarnych). Każdy zbiór kluczy ma jedyną reprezentację - nie ma drzew gorszych i lepszych. Niestety wymagają one sporo pamięci - możliwe są różne rozwiązania kombinowane redukujące tę wadę.

Jako ciekawostkę można dodać, że tak naprawdę to drzewo pozycyjne nie jest drzewem ale lasem ( a jeśli wszystkie klucze mają jednakową długość to nawet żywopłotem ).

Zadania :

24. Jaką kolejność przechodzenia drzewa wykorzystasz do zapisania elementów drzewa w pliku. Po odczytaniu z pliku i wykonaniu ciągu wstawień powinna zostać odtworzona struktura drzewa.Nie wykorzystuj możliwości serializacji.

25. Wytwarzany w przykładzie (BST.java) wydruk wymaga przechylania głowy przy czytaniu. Opracuj metodę drukującą drzewo wierszami. Podpowiedź : rozważ przydatność wykorzystania kolejki.

26. Jak wygląda drzewo binarne reprezentujące wyrażenie. Jaką kolejność przechodzenia zastosujesz do obliczania wartości tego wyrażenia.

27. Zaimplementuj inne metody przetwarzające drzewo, których wynikiem będzie :

• liczba węzłów drzewa

• liczba węzłów wewnętrznych

• liczba węzłów z jednym ( dwoma) potomkiem

• liczba liści

• liczba węzłów zewnętrznych

• liczbę węzłów mniejszych od korzenia

• głębokość węzła

• wysokość poddrzewa którego korzeniem jest dany węzeł itp.

28. Zaimplementuj metody wpisującemu każdemu węzłowi drzewa ( w dodatkowym polu) wartości z poprzedniego zadania.

29. Znajdź w drzewie największy z węzłów nie większych ( mniejszych ) od danego.

30. Utwórz BDrzewo ( rzędu 2) wstawiając do niego kolejne wartości od 1 do 13. Zwróć uwagę na sytuacje wymagające przebudowy drzewa. Z tak zbudowanego drzewa usuwaj kolejno elementy : 8, 9, 1, 2, 3 itd.

Tablice haszowane.

Gdyby wszystkie klucze były różne i miały wartości z niewielkiego zakresu 0..M-1, można by było zastosować prostą tablicę indeksowaną kluczem elementów.

Najczęściej jednak możliwych wartości klucza jest zbyt wiele, wówczas stosujemy haszowanie ( mieszanie).

Stosujemy je jeśli potrafimy zbudować funkcję przyporządkowującą każdemu kluczowi wartość z przedziału 0..M-1. Zazwyczaj zbiór możliwych wartości kluczy jest bardzo duży, o wiele większy od liczby pamiętanych elementów. Np. zbiór słów o długości mniejszej od 15 liter (polskiego alfabetu ) ma liczność około 2E24, podczas gdy duże słowniki zawierają około 100000 haseł, duże zbiory indeksowane nazwiskiem mogą mieć np. 10000000 elementów. Idea polega na tym by element el zapisać w tablicy na pozycji h(el). Oczywiście h nie jest funkcją różnowartościową, więc pojawiają się kolizje (dwa lub więcej kluczy daje tę samą wartość h(el)) sposób ich rozwiązywania zależy od realizacji tablicy haszowanej.

a) tablica statyczna

Zapis elementu do tablicy :

IF (pozycja h(el) jest wolna ) zapisz element

ELSE znajdź pierwszą wolną pozycję (od h(el) cyklicznie)

zapisz element na wolnej pozycji

Wyszukanie (dla uproszczenia - zawsze istnieje jedna wolna pozycja) :

IF (na pozycji h(el) jest właściwy element) znalazłeś

ELSE szukaj cyklicznie do znalezienia lub trafienia na wolną

IF (koniec na wolnej pozycji ) nie ma

ELSE znalazłeś

Wyszukiwanie może być (w najgorszym przypadku) czasochłonne, ale jest proste, trochę gorzej jest z usuwaniem elementu .

Przedstawiony powyżej algorytm rozstrzygania konfliktów nazywa się adresowaniem ( sondowaniem) liniowym. Jeśli oznaczymy przez k klucz szukanego elementu ,H funkcję mieszającą, N- liczbę elementów (rozmiar) tablicy oraz h_i pozycję sprawdzana w i-tym kroku, to ciąg h_i wygląda następująco :

h₀=H(k)

h_i=(h₀+i) mod N

Ta metoda nie zabezpiecza jednak przed grupowaniem się elementów. Lepsze efekty daje mieszanie podwójne (H' oznacza drugą funkcję haszującą):

h₀=H(k)

h_i=(h₀+i*H'(k)) mod N

W tym przypadku krok H' i rozmiar tablicy N powinny być względnie proste. Niestety nie ma prostego sposobu usuwania elementów. W razie konieczności usuwania można zastosować znacznik dla elementów usuniętych. Taki element jest traktowany jako wolny przy wstawianiu, a jako zajęty ale o wartości pustej przy wyszukiwaniu. Niestety może to prowadzić do szybszego zapełniania tablicy.

Inną możliwością, jest stworzenie (wspólnego dla wszystkich pozycji tablicy) obszaru przeniesień, przeszukiwanego liniowo w przypadku wystąpienia kolizji. Jest to rozwiązanie nieco lepsze (dające prostsze algorytmy) lecz wymagające większej pamięci.

Istnieje jeszcze trzecie rozwiązanie - można przyspieszyć wyszukiwanie łącząc pozycje zawierające elementy o tej samej wartości w listę.

Naturalnym rozszerzeniem ostatniego podejścia jest :

b. tablica list

Takie rozwiązanie zdecydowanie upraszcza algorytmy (szczególnie usuwanie elementu) dając o wiele lepsze wykorzystanie pamięci.

Haszowanie jest skuteczną metodą reprezentacji słownika jeśli potrafimy dobrze dobrać funkcję haszującą (tak aby dawała równomierny rozrzut elementów w tablicy - niestety nie jest to proste). Można to zrobić eksperymentalnie dla słownika stałego ( bez Wstaw i Usun). Przy zmiennym słowniku sytuacja jest gorsza (najgorsza gdy wszystkie elementy mają taką samą wartość h(el)). Dodatkowo na efektywność tej metody wpływa stopień zapełnienia tablicy (czym mniej wolnych miejsc tym gorzej).

Oznaczając przez α stopień zapełnienia tablicy (liczba zapisanych elementów / rozmiar) otrzymujemy następujące wyniki:

algorytm liczba prób dla el ∈ słownika liczba prób dla el ∉ słownika

tablica list 1+α/2 1+α

adresowanie liniowe 0.5+ 1/(2*(1-α)) 0.5+1/(2*(1-α )²)

mieszanie podwójne -ln(1-α)/α 1/(1-α)

Przykładowe wartości liczby sondowań w zależności od

wypełnienia tablicy - α 1/2 2/3 3/4 9/10

tablica list - trafione 1,25 1,33 1,38 1,45

tablica list - chybione 1,5 1,67 1,75 1,9

adresowanie liniowe - trafione 1,5 2,0 3,0 5,5

adresowanie liniowe - chybione 2,5 5,0 8,5 55,5

podwójne mieszanie - trafione 1,4 1,6 1,8 2,6

podwójne mieszanie - chybione 2.0 3,0 4,0 9,0

Widać, że liczba prób nie zależy od wielkości tablicy lecz tylko od stopnia jej zapełnienia.

Porównanie złożoności poszukiwania dla różnych sposobów implementacji słownika :

pesymistyczny średni

wstawianie wyszukiwanie wstawianie wyszukiwanie

trafione chybione

tablica indeksowana kluczem 1 1 1 1 1

tablica (lista) uporządkowana n n n/2 n/2 n/2

tablica (lista) nieuporządkowana 1 n 1 n/2 n

wyszukiwanie binarne n lg n n/2 lg n lg n

BST n n lg n lg n lg n

AVL lub czarno-czerwone lg n lg n lg n lg n lg n

BST randomizowane n* n* lg n lg n lg n

mieszanie 1 n* 1 1 1

* - oznacza sytuację możliwą ale bardzo mało prawdopodobną

Zadania :

31. Dla wybranego przez siebie ciągu elementów, wielkości tablicy i funkcji haszujących zbadaj różnice w liczbie konfliktów przy sondowaniu liniowym i podwójnym haszowaniu.

Temat 9. Algorytmy grafowe.

Zbiory rozłączne

Dane jest n elementów pogrupowanych w pewną liczbę zbiorów rozłącznych. Każdy zbiór jest identyfikowany przez swojego reprezentanta. Wykonujemy na nich tylko dwie operacje : znajdowanie zbioru do którego należy dany element oraz łączenie dwóch zbiorów.

MAKE_SET(x) - tworzy zbiór, którego jedyny element jest wskazany przez x.

UNION(x,y) - łączy dwa zbiory zawierające odpowiednio x i y, w jeden.

FIND(x) - zwraca wskaźnik do reprezentanta zbioru zawierającego x.

A. Prosta realizacja lasu zbiorów rozłącznych.

Struktura elementu : class Elem { Object val; Elem parent; ...};

void MAKE_SET( Elem x)

{x.parent = x; }

void UNION ( Elem x , Elem y)

{ LINK(FIND(x),FIND(y)); }

void LINK ( Elem x, Elem y)

{ y.parent = x; }

Elem FIND( Elem x )

{ return x = = x.parent ? x : FIND(x.parent) ;}

B. Realizacja lasu z równoważeniem wysokości drzew.

Struktura elementu : class Elem {Object val; Elem parent; int height;};

void MAKE_SET( Elem x)

{x.parent = x; x.height=0; }

void UNION ( Elem x , Elem y)

{ LINK(FIND(x),FIND(y)); }

void LINK ( Elem x, Elem y)

{ if (x.height > y.height) y.parent=x;

else {x.parent=y;

if (x.height == y.height)

y.height++;

}

Elem FIND( Elem x )

{ return x == x.parent ? x : FIND(x.parent) ;}

C. Realizacja lasu z kompresją ścieżki.

Struktura elementu : class Elem {Object val ; Elem parent; };

void MAKE_SET( Elem x)

{x.parent = x; }

void UNION ( Elem x , Elem y)

{ LINK(FIND(x),FIND(y)); }

void LINK ( Elem x, Elem y)

{ y.parent = x; }

Elem FIND( Elem x )

{ if (x != x.parent) x.parent = FIND(x.parent);

return x.parent ;}

Można połączyć rozwiązania B i C.

Grafy - reprezentacje grafów, podstawowe algorytmy grafowe

Reprezentacje grafów :

1. Lista sąsiedztwa (LS)

2. Macierz sąsiedztwa (MS)

3. Lista krawędzi (LK)

1. Przeszukiwanie (przechodzenie) grafu.

Przyjmujemy, że graf jest reprezentowany przez listę sąsiedztwa (LS) oraz każdy wierzchołek ma pole "odwiedzony".

1. Przeszukiwanie grafu wszerz (algorytm BFS - Breadth First Search)

Pomocniczo wykorzystujemy procedury obsługi kolejki:

CLEAR - utwórz pustą kolejkę

IS_EMPTY - czy kolejka jest pusta ?

ENQUEUE - wstaw do kolejki

DEQUEUE - pobierz z kolejki (funkcja)

Przechodzenie rozpoczynamy od wierzchołka s. Zakładamy, że graf jest spójny. Jeśli nie należy dodać zewnętrzną pętlę.

BFS(s)

for each u∈ V- {s}

u.odwiedzony = false

s.odwiedzony = true

CLEAR

ENQUEUE(s)

while not IS_EMPTY

u = DEQUEUE

//wykorzystaj u

for each v∈LS[u]

if not v.odwiedzony then v.odwiedzony = true

ENQUEUE(v)

2. Przeszukiwanie grafu wzdłuż (algorytm DFS - Deep First Search)

DFS(s) { Przechodzenie rozpoczynamy od wierzchołka s.}

for each u∈ V-{s}

u.odwiedzony = FALSE

s.odwiedzony = TRUE

DFS_V(s)

DFS_V(u);

//wykorzystaj u

u.odwiedzony = true

for each v∈LS[u]

if not v.odwiedzony then DSF_V(v)

2. Minimalne drzewo rozpinające.

Algorytm Kruskala.

Danymi dla tego algorytmu są: zbiór wierzchołków grafu (V) i lista jego krawędzi (LK) uporządkowana rosnąco ze względu na wagi. Wynikiem jest zbiór MST (Minimal Spanning Tree) zawierający krawędzie tworzące drzewo rozpinające o minimalnej sumie wag krawędzi.

Pomocniczo wykorzystamy procedury obsługi zbiorów rozłącznych MAKE_SET,FIND i UNION.

Przedstawiony algorytm należy do klasy algorytmów zachłannych.

MST_KRUSKAL

MST = {} {zbiór pusty}

for each v∈V

MAKE_SET(v)

for each <u,v> ∈ LK

if FIND(u) <> FIND(v) then

MST = MST ∪ {<u,v>}

UNION(u,v)

Złożoność O( |E| log|E| ).

Inny algorytm został zaproponowany przez Prima.

Dane to: zbiór wierzchołków grafu (V), każdy wierzchołek v jest wzbogacony o dwa pola : prev - wskazuje wierzchołek drzewa z którym łączy się v, pr - priorytet, czyli odległość wierzchołka od już zbudowanej części drzewa. Algorytm wykorzystuje kolejkę priorytetową wierzchołków uporządkowaną według rosnącego pola pr i listę sąsiedztwa (LS).

Dodatkowe operacje kolejki :

IN_QUEUE (v) - czy element v jest w kolejce

MOD_PRIORITY(v, prior) - ustaw nowy priorytet elementu v i przebuduj kolejkę.

Budowę drzewa rozpoczyna się od wskazanego wierzchołka startowego s .

Pomocnicza operacja to :

INIT (s)

for each v∈V-{s}

v.pr =

ENQUEUE(v)

s.pr = 0 s.prev = null ENQUEUE(s)

MST_PRIM( s )

INIT(s)

while not IS_EMPTY

u=DEQUEUE

for each v∈ LS(u)

if IN_QUEUE(v) and (w<u,v> < v.pr )

v.prev = u

MOD_PRIORITY( v, w<u,v> )

Złożoność obliczeniowa : O( |E| log |V| ).

Tym razem MST jest zapisane w sposób niejawny - poprzez pola prev.

3. Najkrótsza ścieżka między dwoma wierzchołkami.

Algorytm Dijkstry.

Zakładamy, że mamy ważony graf skierowany o nieujemnych wagach krawędzi. Należy znaleźć najkrótszą drogę od źródła s do ujścia w. Danymi do tego algorytmu jest lista sąsiedztwa grafu(LS- z zapisanymi wagami krawędzi ). Dodatkowymi danymi związanymi z każdym węzłem (należącym do zbioru V) są : pr - priorytet wierzchołka czyli odległość od źródła, oraz prev - węzeł poprzedzający na najkrótszej ścieżce. Wykorzystujemy zbiór S - węzłów już wykorzystanych oraz kolejkę priorytetową (uporządkowaną według niemalejącej odległości od źródła) .

Pomocnicze operacje :

INIT(s) // patrz wyżej

RELAX(u,v)

if v.pr > u.pr + w<u,v>

then MOD_PRIORITY(v, u.pr + w<u,v>)

v.prev=u

DIJKSTRA(s ,w)

INIT(s)

while not IS_EMPTY

u=DEQUEUE

for each v∈LS[u]

RELAX(u,v)

PRINT(s,w)

PRINT ( s, v)

if v = s then write s

else PRINT (s, v.prev)

write v

Jeśli wykorzystamy kolejkę priorytetową wykorzystując kopiec, to złożoność wynosi O(|E|log|V|). Algorytm ten jest bardzo podobny do algorytmów BSF i MST_PRIM.

Algorytm Bellmana-Forda.

Tym razem wagi krawędzi mogą być ujemne, ale nie mogą istnieć cykle o ujemnej wadze ( algorytm sam wyjrywa czy są takie). Znajdujemy najkrótszą drogę od źródła s do ujścia w. Danymi do tego algorytmu jest lista krawędzi (LK- z zapisanymi wagami krawędzi ). Dodatkowymi danymi związanymi z każdym węzłem (należącym do zbioru V) są : pr - priorytet wierzchołka czyli odległość od źródła, oraz prev - węzeł poprzedzający na najkrótszej ścieżce. Tym razem nie wykorzystujemy kolejki więc upraszcza się metoda MOD_PRIORITY ( modyfikuje tylko pole pr ).

BELLMAN_FORD (s ,w)

INIT(s)

for i =1 to |V|-1

for each <u,v>∈LK

RELAX(u,v)

for each <u,v>∈LK

if v.pr > u.pr +w<u,v>

return false

PRINT(s,w)

return true

Złożoność tego algorytmu to O(|V|*|E|).

Uwaga : w obu algorytmach można zrezygnować z pola prev - ścieżkę zawsze można odtworzyć korzystając z wyznaczonych wartości pola pr i wag krawędzi.

Temat 10. Algorytmy geometryczne.

Pojęcia podstawowe : punkt, odcinek, wektor, prosta.

Problemy :

• po której stronie wektora p->q leży punkt r

• czy punkty x i y leżą po tej samej stronie prostej p-q

• czy punkt r należy do odcinka p-q

• czy podcinki p-q i r-s przecinają się

• czy punkt p leży wewnątrz wielokąta W

1. W jest wielokątem wypukłym

2. W jest dowolnym wielokątem

• Znajdowanie otoczki wypukłej zbioru punktów

1. algorytm Grahama

2. algorytm Jarvisa

3. algorytm przyrostowy

Temat 11. Przetwarzanie tekstów .

• wyszukiwanie wystąpień wzorca w tekście

Prosty interfejs do wyszukiwania wzorca w tekście począwszy od wskazanej pozycji :

package ssearching;

public interface StringSearcher { public int search(CharSequence text, int from); }

1. algorytm naiwny (siłowy - brute force)

package ssearching;

public class BruteForceSearcher implements StringSearcher {

private final CharSequence _pattern;

public BruteForceSearcher(CharSequence pattern)

{ _pattern = pattern; }

public int search(CharSequence text, int from) {

int s = from;

while (s <= text.length() - _pattern.length()) {

int i = 0;

while (i < _pattern.length() && _pattern.charAt(i) == text.charAt(s + i))

++i;

if (i == _pattern.length()) return s;

++s;

}

return -1;

}

}

2. algorytm Knutha-Morrisa-Pratta

package ssearching;

public class KnuthMorrisPrattSearcher implements StringSearcher

{ private final CharSequence _pattern;

private final int[] _shuffle;

public KnuthMorrisPrattSearcher(CharSequence pattern)

{ _pattern = pattern;

_shuffle = computeShuffle(pattern);

}

public int search(CharSequence text, int from) {

int s = from;

int i = 0;

while (s <= text.length() - _pattern.length()) {

i=_shuffle[i];

while (i <_pattern.length() && _pattern.charAt(i) == text.charAt(s + i))

++i;

if (i >=_pattern.length())

return s;

s += Math.max(1,i-_shuffle[i]);

}

return -1;

}

private static int[] computeShuffle(CharSequence pattern) {

int[] shuffle = new int[pattern.length()];

shuffle[0]=0;

int tmp=0;

for (int i = 1; i < pattern.length(); ++i){

while (tmp>0 && pattern.charAt(tmp) != pattern.charAt(i))

tmp=shuffle[tmp];

if(pattern.charAt(tmp)==pattern.charAt(i))

tmp++;

shuffle[i]=tmp;

}

return shuffle;

}

}

3. algorytm Boyera-Moore'a

package ssearching;

public class BoyerMooreSearcher implements StringSearcher {

/** The supported character set size (ASCII). */

private static final int CHARSET_SIZE = 256;

private final CharSequence _pattern;

/** The position (0, 1, 2...) of the last occurrence of each character within the pattern. */

private final int[] _lastOccurrence;

public BoyerMooreSearcher(CharSequence pattern) {

_pattern = pattern;

_lastOccurrence = computeLastOccurrence(pattern);

}

public int search(CharSequence text, int from) {

int s = from;

while (s <= text.length() - _pattern.length()) {

int i = _pattern.length() - 1;

char c = 0;

while (i >= 0 && _pattern.charAt(i) == (c = text.charAt(s + i)))

--i;

if (i < 0)

return s;

s += Math.max(i - _lastOccurrence[c], 1);

}

return -1;

}

private static int[] computeLastOccurrence(CharSequence pattern) {

int[] lastOccurrence = new int[CHARSET_SIZE];

for (int i = 0; i < lastOccurrence.length; ++i)

lastOccurrence[i] = -1;

for (int i = 0; i < pattern.length(); ++i)

lastOccurrence[pattern.charAt(i)] = i;

return lastOccurrence;

}

}

4. algortym Karpa-Rabina

package ssearching;

public class KarpRabinSearcher implements StringSearcher {

private final CharSequence _pattern;

private static int chars=256; //liczność alfabetu

private static int q=8388607; //liczba pierwsza taka że q*chars < MAX_INT

private int cm; //chars do potęgi pattern.length()-1 modulo q

private int hp; //funkcja haszująca wzorca

public KarpRabinSearcher(CharSequence pattern)

{_pattern = pattern;

hp=h(pattern);

cm=computeCM(pattern.length());}

public int search(CharSequence text, int from) {

int s = from;

int ht=h(text.subSequence(s,s+_pattern.length()));

while (s <= text.length() - _pattern.length()) {

if(hp==ht) return s;

if(s < text.length() - _pattern.length())

ht=((ht-text.charAt(s)*cm)*chars+text.charAt(s+_pattern.length()))%q;

s++;

}

return -1;

}

private int computeCM(int m)

{ int res=1;

for(int i=1;i<m;i++)

res=(res*chars)%q;

return res;

}

private int h(CharSequence s)

{ int res=s.charAt(0);

for(int i=1;i<s.length();i++)

res=(res*chars+s.charAt(i))%q;

return res;

}

}

Prosta klasa do testowania wyszukiwarek :

package ssearching;

import java.io.*;

public class TestStringSearcher

{ void test(){

CharSequence text= "aaaaaaaaaaaaaababababacaaaaaa";

CharSequence pattern = "ababababac";

StringSearcher ss1 = new BruteForceSearcher(pattern),

ss2 = new BoyerMooreSearcher(pattern),

ss3 = new KnuthMorrisPrattSearcher(pattern),

ss4 = new KarpRabinSearcher(pattern);

System.out.println(" ss1 = " + ss1.search(text,0));

System.out.println(" ss2 = " + ss2.search(text,0));

System.out.println(" ss3 = " + ss3.search(text,0));

System.out.println(" ss4 = " + ss4.search(text,0));

}

}

• kompresja tekstu ( kodowanie )

1. algorytm Huffmana

I to by było na tyle - na razie, bo parę rzeczy wymaga uzupełnienia.

jr

Będę wdzięczny za wszelkie ( poza wytykaniem literówek ) uwagi dotyczące przedstawionego materiału.

48

---