Algorytmy i struktury danych: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rytter (dyskusja | edycje)
830 edycji
 
(Nie pokazano 45 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
<font size="6">Wstęp: poprawność i złożoność algorytmów</font>
== Forma zajęć ==
Wykład (30 godzin) + laboratorium (30 godzin)
== Opis ==
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.


== Sylabus ==
=== Autorzy ===
* Krzysztof Diks &mdash; Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Adam Malinowski &mdash; Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Wojciech Rytter &mdash; Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Tomasz Waleń &mdash; Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki


__TOC__
=== Wymagania wstępne ===
* Wstęp do programowania
* Metody programowania
* Matematyka dyskretna
* Logika i teoria mnogości


=== Zawartość ===
* Podstawowe zasady analizy algorytmów:
** poprawność
** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana)
**koszt zamortyzowany: metoda potencjału
* Podstawowe techniki i struktury:
**metoda ''dziel i zwyciężaj''
**metoda zachłanna
**pogramowanie dynamiczne
**transformacyjna konstrukcja algorytmu
**elementarne struktury danych: stosy, kolejki, listy
* Sortowanie:
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
** proste kolejki priorytetowe: kopce binarne
**HeapSort
** sortowanie pozycyjne
** złożoność problemu sortowania
* Selekcja:
** algorytm Hoare'a
** algorytm ''magicznych piątek''
* Wyszukiwanie i proste słowniki:
** wyszukiwanie liniowe i binarne
** prosty słownik: drzewa poszukiwań binarnych
** haszowanie
* Efektywne implementacje słownika:
** drzewa AVL
** drzewa typu ''splay''
** B-drzewa
*  Złożone struktury danych:
** wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego
** efektywne sumowanie zbiorów rozłącznych
* Algorytmy grafowe:
** DFS i jego zastosowania
** problemy ścieżkowe -- Algorytm Dijkstry
** minimalne drzewo rozpinające
* Wyszukiwanie wzorca w tekstach:
** prefikso-sufiksy
** algorytm Knutha-Morisa-Pratta
*Tekstowe struktury danych:
**tablice sufiksowe
**drzewa sufiksowe
* NP-zupełność:
** klasa NP
** problemy NP-trudne i NP-zupełne


Podstawowym elementem przy rozwiązywaniu zadanego problemu na komputerze jest dobór
=== Moduły===
algorytmu i struktury danych. Najważniejszymi aspektami algorytmu są jego "poprawność" i
złożoność.
Będziemy zasadniczo rozpatrywać tylko złożoność czasową i pamięciową.


W przypadku złożoności czasowej z reguły wyróżnimy pewną operację dominującą i czas będziemy
* [[Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu|Wstęp: poprawność i złożoność algorytmu]] ([[ASD Ćwiczenia 1|Ćwiczenia]])
traktować jako liczbę wykonanych operacji dominujących.
* [[Algorytmy i struktury danych/Wstęp: elementarne techniki algorytmiczne i struktury danych|Wstęp: elementarne techniki algorytmiczne i struktury danych]] ([[ASD Ćwiczenia 2|Ćwiczenia]])
W ten sposób nasza analiza będzie zależna jedynie od algorytmu a nie od implementacji i sprzętu. W
* [[Algorytmy i struktury danych/Sortowanie - BubbleSort, SelectionSort, InsertionSort| Sortowanie przez porównania: BubleSort, SelectionSort i InsertionSort]] ([[ASD Ćwiczenia 3|Ćwiczenia]])
przypadku sortowania przeważnie operacją dominującą jest porównanie dwóch elementów (mniejsze,  
* [[Algorytmy i struktury danych/Sortowanie: MergeSort, HeapSort i QuickSort| Sortowanie przez porównania: MergeSort, HeapSort i QuickSort ]] ([[ASD Ćwiczenia 4|Ćwiczenia]])
równe, mniejsze), a w przypadku przeglądania drzewa jedno przejście w drzewie między 
* [[Algorytmy i struktury danych/Sortowanie: dolna granica i sortowanie pozycyjne| Sortowanie: dolna granica, sortowanie pozycyjne]] ([[ASD Ćwiczenia 5|Ćwiczenia]])
wierzchołkami. W przypadku algorytmów tekstowych operacją dominującą jest porównanie dwóch
* [[Algorytmy_i_struktury_danych/Selekcja| Selekcja]] ([[ASD Ćwiczenia 6|Ćwiczenia]])
symboli. Z reguły będziemy przyjmować, że każda operacja arytmetyczna na małych liczbach daje się
* [[Algorytmy_i_struktury_danych/Wyszukiwanie| Wyszukiwanie]] ([[ASD Ćwiczenia 7|Ćwiczenia]])
zrobić w jednym kroku. Przez małe rozumiemy liczby mające <math>O(\log n)</math> bitów.  Z
* [[Algorytmy_i_struktury_danych/Słowniki| Słowniki]] ([[ASD Ćwiczenia 8|Ćwiczenia]])
reguły określamy pewien parametr <math>n</math>, będący rozmiarem problemu wejściowego i  
* [[Algorytmy_i_struktury_danych/Kolejki priorytetowe| Kolejki priorytetowe]] ([[ASD Ćwiczenia 9|Ćwiczenia]])
określamy złożoność jako funkcję <math>T(n)</math>, której argumentem jest rozmiar problemu.
* [[Algorytmy_i_struktury_danych/Find-Union| Find-Union]] ([[ASD Ćwiczenia 10|Ćwiczenia]])
* [[Algorytmy i struktury danych/Algorytmy grafowe - najlżejsze ścieżki| Algorytmy grafowe - najlżejsze ścieżki]] ([[ASD Ćwiczenia 11|Ćwiczenia]])
* [[Algorytmy i struktury danych/Przeszukiwanie grafów| Algorytmy grafowe - przeszukiwanie grafów]] ([[ASD Ćwiczenia 12|Ćwiczenia]])
* [[Algorytmy i struktury danych/Algorytmy tekstowe I| Algorytmy tekstowe I]] ([[ASD Ćwiczenia 13|Ćwiczenia]])
* [[Algorytmy_i_struktury_danych/Algorytmy_tekstowe_II| Algorytmy tekstowe II]] ([[ASD Ćwiczenia 14|Ćwiczenia]])
* [[Algorytmy i struktury danych/NP-zupełność| NP-zupełność]] ([[ASD Ćwiczenia 15|Ćwiczenia]])


Przeważnie rozważamy złożoność pesymistyczną - maksymalną złożoność dla danych tego samego
=== Literatura ===
rozmiaru <math>n</math>.
# ''Algorytmy i struktury danych'', L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
W praktyce ważniejszą może się okazać złożoność średnią, lub oczekiwaną, w tym przypadku
# ''Wprowadzenie do algorytmów'', Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
<math>T(n)</math> jest średnią (oczekiwaną) wartością złożoności dla wszystkich problemów
rozmiaru <math>n</math>. Tego typu złożoność zależy  istotnie od tego, jaka się pod tym kryje
przestrzeń probabilistyczna problemów wejsściowych. Z reguły zakładamy, że wszystkie problemy
wejściowe tego samego rozmiaru mogą się pojawić z tym samym prawdopodobieństwem. Jednakże
jest to często mało realistyczne założenie. Przestrzeń probabilistyczna danych wejściowych może być
bardzo skomplikowana, prowadzić to może do bardzo trudnych (i wykraczających poza ten kurs)
analiz.
 
Rozważmy następujący przykład. Przypuśćmy, że chcemy znaleźć pierwszą jedynkę w tablicy zerojedynkowej i nasz
algorytm przegląda tablicę od strony lewej sprawdzając kolejne elementy.
Niech operacją dominującą będzie sprawdzenie jednego elementu. Jeśli nie ma jedynki, to wykonamy
<math>n</math> sprawdzeń, jest to maksymalna liczba, zatem złożoność pesymistyczna wynosi
<math>T(n)=n</math>. Jeśli każdy ciąg binarny jest dany z tym samym prawdopodobieństwem to
łatwo policzyć, że złożoność średnia jest ograniczona przez stałą.
 
Do wyrażania złożoności stosujemy opis asymptotycznego wzrostu funkcji:
<math>f(n)\ =\ O(g(n))</math>  oznacza że <math>f(n) \le c\cdot g(n)</math> dla pewnej stałej
<math>n</math>.
Gdy <math>g(n)=n</math> to mówimy, że <math>f(n)</math> jest liniowa, oraz dla
<math>g(n)=n^2</math> mówimy, że złożoność <math>f(n)</math> jest
kwadratowa. Jeśli <math>g(n)</math> jest wielomianem to wtedy mówimy o złożoności
wielomianowej.
 
 
Będziemy używać dodatkowych notacji:
 
<math>f(n)=\Theta(g(n)),\ f(n)=\Omega(n)</math>.
Były one wprowadzone na wykładach z matematyki dyskretnej.
 
 
Dla przypomnienia:
 
 
<math>f(n)=\Theta(g(n)) \Leftrightarrow f(n)=O(g(n)) </math> & <math>  g(n)=O(f(n))\,</math>
<br>
 
<math>f(n)=\Omega(g(n)) \,</math>, gdy  dla nieskończenie wielu <math>n</math> i pewnej stałej
<math>c>0</math> zachodzi  <math>f(n) \ge c\cdot g(n)</math>
 
{{przyklad|||
<math>\frac{1}{100}\cdot n^2- 2n = \Theta(n^2 )\cdot n^5+2^n = \Theta(2^n),
n!=\Omega(10^n)</math>,<br>
Jeśli <math>f(n)=(1+(-1)^n)\cdot n</math>, to <math>f(n)=\Omega(n),\ f(n)=O(n)</math> ale nie
zachodzi <math>f(n)=\Theta(n)\,</math>.}}
 
 
 
 
'''Konwencje językowe.''' Jaki jest najlepszy język do opisu algorytmu ? Jest to przykład problemu
nierozstrzygalnego. Niewątpliwie język ojczysty jest najlepszym
językiem potocznym , a ulubiony język programowania jest  najlepszym językiem do implementacji
algorytmu. Język, którym będziemy opisywać algorytmy jest gdzieś pomiędzy tymi językami, język
potoczny nie wystarcza a konkretny język programowania może spowodować to, że "prosty" algorytm
się zrobi nieczytelny.  Będziemy używać, o ile się da, nieformalnych konstrukcji programistycznych, a
w przypadku bardzo prostych algorytm będziemy się starali pisać algorytm w języku C-podobnym.
 
== Poprawność algorytmu: niezmienniki, własność stopu ==
Przez poprawność algorytmu rozumiemy to, że daje on takie odpowiedzi jakich oczekujemy.
Oczywiście algorytm musi być poprawny aby miało sens rozpatrywanie jego złożoność.
 
=== Pojęcie niezmiennika ===
Poprawność algorytmu sprowadza się do spełniania określonych niezmienników na różnych etapach
tego algorytmu.
Rozważmy kilka przykładów pozwalających zrozumieć znaczenie niezmiennika.
 
Załóżmy, że mamy zbiór <math>S</math> składający się z <math>n</math> przedmiotów, niektóre z
przedmiotów są czarne a niektóre białe. Zakładamy, że liczba czarnych przedmiotów jest nieparzysta.
 
 
{{algorytm|||
1 '''while'''  <math>|S|> 1</math>
2    pobierz dwa przedmioty z S;
3    '''if''' przedmioty są różnego koloru to wstaw z powrotem czarny
4 '''return''' kolor ostatniego przedmiotu w S;
}}
 
Załóżmy, że mamy 10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni
przedmiot ? Rozpatrzmy niezmiennik: parzystość liczby czarnych przedmiotów.
 
Ponieważ na początku mamy nieparzystą liczbę czarnych przedmiotów, zatem na wyjściu mamy kolor
czarny.
 
 
Rozpatrzmy modyfikację tego algorytmu, zakładamy że n jest niezerowe.
 
{{algorytm|||
1 '''while'''  <math>|S|> 1</math>
2    pobierz dwa przedmioty z S;
3    '''if''' co najmniej jeden jest biały to wstaw z powrotem jeden biały;
4 '''return''' kolor ostatniego przedmiotu w S.
}}
 
Załóżmy, że mamy  10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni
przedmiot? Tym razem rozważmy niezmiennik: znak liczby białych przedmiotów.
(Znak liczby jest równy 0 jeśli jest ona równa zeru, 1 jeśli jest większa od zera.) Zatem ostatnim
przedmiotem jest przedmiot biały.
 
=== Własność stopu===
Podstawowym elementem poprawności algorytmu jest to, że ma on własność stopu: dla poprawnych
danych wejściowych da odpowiedź po skończonym czasie. Na przykładzie dwóch prostych
algorytmów pokażemy,
że sprawdzanie własności stopu może nie być czynnością trywialną.
 
{{algorytm|Suma-Kwadratów-Cyfr|suma_kwadratow_cyfr|suma_kwadratow_cyfr
  1  '''while'''  ((n <>4)  and  (n<> 1))
  2  <math> n := </math> suma kwadratów cyfr liczby <math> n </math>;
}}
 
 
{{algorytm|6174|algorytm_6174|
wejściem jest czterocyfrowa liczba naturalna niepodzielna przez 1111
pierwszymi cyframi mogą być zera
'''while''' (n<>6174)
    <math>n1 :=</math>  największa liczba czterocyfrowa której cyfry są permutacją cyfr liczby n;
    <math>n2 :=</math> najmniejsza liczba czterocyfrowa której  cyfry są permutacją cyfr liczby n;
    <math>n := </math>n1 - n2;
}}
{{algorytm|X|algorytm_X|
'''while''' (n<>1)
    '''if''' n parzyste <math>n :=</math> n div 2; '''else''' <math>n := </math>3*n+1;
   
}}
Pierwsze dwa algorytmy mają własność stopu, w pierwszym łatwo to sprawdzić gdyż dla
<math>n>100</math> następna wartość jest istotnie mniejsza.  
 
Pozostawiamy jako ćwiczenie  jak najkrótszy koncepcyjnie dowód  własności stopu obu algorytmów
(nie chodzi nam tu o brutalny dowód polegający na sprawdzeniu wszystkich  przypadków przez
komputer).
 
Algorytm X jest dosyć zagadkowy, nie wiadomo, czy dla dowolnego naturalnego dodatniego
<math>n</math> ma on własność stopu.
 
== Złożoność algorytmów: analiza siedmiu prostych algorytmów ==
 
Na przykładzie siedmiu prostych algorytmów pokażemy, jak się analizuje i osiąga złożoność liniową.
Po dokładniejsze uzasadnienia i analizy odsyłamy do ćwiczeń.  Naiwne wersje tych algorytmów
działają w czasie kwadratowym (Wybraliśmy ''"siedem"'' losowo, na przykład jest ''siedem'' dni w
tygodniu ,był taki film ''Siedmiu wspaniałych'' itp.)
 
==== Przywódca ciągu ====
Przywódcą ciągu jest element, który występuje w ciągu więcej razy niż połowa długości tego ciągu.
Naszym problemem jest policzenie przywódcy ciągu danego tablicą <math>A[1..n]</math>. Dla
uproszczenia przyjmijmy, że w tym ciągu jest przywódca. Łatwo można modyfikować algorytm by
sprawdzał istnienie przywódcy.
 
{{algorytm|Liczenie-Przywódcy|algorytm_liczenie_przywodcy|
  <math> ile :=  0 </math>;
    '''for''' i <math>:=</math> 1 to n do
      '''if''' <math>(ile = 0)  \{ile := ile+1; j := i\}</math>;
      '''else if''' <math>( A[i]=A[j]) </math>  <math> ile:=ile+1; </math> '''else'''
        <math> ile :=ile-1</math>;<br>
    '''return''' <math>A[j]</math>;
}}
Przyspieszenie wynika z następującej własności problemu: jeśli mamy dwa różne elementy w tablicy
to możemy je usunąć i przywódca pozostanie taki sam.
 
Algorytm można zmodyfikować tak aby w czasie liniowym liczył on słabego przywódcę: element,
który występuje w tablicy więcej niż n/5 razy.
W tym przypadku potrzebne są cztery liczniki  odpowiadające czterem kandydatom na słabego
przywódcę.  
Algorytm liczy  element który jest kandydatem na słabego przywódcę (jeśli istnieje taki przywódca to
na pewno jest nim wyliczony element). Jeśli istnieje słaby przywódca i mamy pięć różnych elementów to można je usunąć bez zmiany
wyniku. Pozostawiamy napisanie odpowiedniego algorytmu jako ćwiczenie.
 
Problem można rozwiązać inaczej sortując tablicę, wtedy mamy złożoność O(n log n). Podamy potem
również rozwiązanie metodą "dziel i zwyciężaj".
 
 
<center>
<flash>file=przywodca_slaby.swf|width=520|height=270</flash></center>
 
W animacji kolorem żółtym na końcu zaznacza się licznik słabego przywódcy, jego nazwa jest w
niebieskim kwadraciku.
 
====Szukanie sumy==== Mamy dane dwie posortowane rosnąco tablice <math>A,B</math> i liczbę
x,pytamy  czy są  <math>a \in A,\ b \in B</math> takie, że <math>x=a+b</math>.
 
{{algorytm|Szukanie Sumy|algorytm_szukanie_sumy|
  Szukanie Sumy
    <math>i := 1; j := n;</math>
    '''while''' <math>(i <= n</math>  and <math> j > 0)</math>
      '''if''' <math>(A[i]+B[j]=x) </math>'''return''' true; else
      '''if''' <math>(A[i]+B[j]<x) i:=i+1; </math>'''else''' <math>j:=j-1</math>;
    '''return''' false;
}}
Przyspieszenie jest możliwe dzięki odpowiedniej kolejności sprawdzania <math>i,j</math> i
pominięciu zbędnych sprawdzeń.
 
==== Maksymalny segment ====  Dla tablicy <math>A[1..n] \,</math> liczymy maksymalną
wartość z zera i
ze wszystkich liczb <math>\sum_{k=i}^j\ A[k]</math>, gdzie <math>1\le i\le j\le n</math>.
 
'''Algorytm''' Maksymalny-Segment;<br>
    wynik := 0; sufiks := 0;
    '''for''' i := 1 to n do
      sufiks := max(A[i]+sufiks,0);
      wynik := max(wynik,  sufiks);
 
Przyspieszenie w stosunku do algorytmu kwadratowego następuje dzięki wprowadzeniu dodatkowej
zmiennej sufiks.
Po każdym zakończeniu  pętli "for" zachodzi: wynik jest maksymalną sumą przedziału zawierającego
się w <math>[1..i]</math>
oraz sufiks jest maksymalną sumą segmentu który jest sufiksem przedziału <math>[1..i]</math>.
 
 
==== Najbliższy mniejszy sąsiad z lewej strony ====
Dla każdego <math>i > 1</math> zdefiniujmy najbliższego mniejszego sąsiada <math>i</math> jako: 
<math>Lewy[i] =max \{j<i : A[j]<A[i] \}</math>
Dla uproszczenia zakładamy, że  <math>A[i]> 0</math> dla <math>i>0</math> oraz
<math>A[0]=0</math>.
 
{{algorytm|Najbliższy-Mniejszy-Sąsiad|algorytm_najblizszy_mniejszy_sasiad|
Najbliższy Mniejszy Sąsiad
'''for''' <math>i := 1</math> to n do
  <math>  j := i-1;</math>
    '''while''' <math>( A[j] >= A[i]) j := Lewy[j];</math>
      <math>Lewy[i] := j;</math>
}}
 
Przyspieszenie następuje dzięki temu, że nie ma potrzeby sprawdzania tablicy dla indeksów istotnie
wewnątrz przedziału  <math>[[Lewy[i-1]...(i-1)]</math> .  Niech <math>k_i</math> będzie liczbą
tych <math>j</math> dla których <math>A[j]>=A[i]</math>. Wystarczy
pokazać, że suma wszystkich <math>k_i</math> jest liniowa. Może się zdarzyć, że niektóre
<math>k_i</math> mają wartość
liniową. Zauważmy jednak, że dany indeks <math>j</math> pojawia się co najwyżej raz w sytuacji
gdy <math>A[j] >= A[i]</math>,
potem będzie "przeskoczony".
 
==== Najdłuższy malejący podciąg ====
Niech <math>A[1], A[2],\ldots A[n]</math> będzie ciągiem dodatnich liczb. Następujący algorytm
oblicza długość najdłuższgo  malejącego podciągu. 
{{algorytm|Najdłuższy-Malejący|algorytm_najdluzszy_malejacy|
Najdłuższy-Malejący
<math>wynik := 1;</math>
'''for''' <math>i := 1</math> to n do
    <math>x := A[i]; A[i]:=0;</math>
    <math>k := min \{ j : x  > A[j]\};</math>
    <math>A[k] := x ;</math>
    <math>wynik := max(k, wynik);</math>
}}
 
 
Algorytm może, po niewielkim dodatkowym  wysiłku fizycznym procesora, podać najdłuższy maljący
podciąg, albo też rozkład na minimalną liczbę podciągów niemalejących.
Nie jest jasne jak policzyć leksykograficznie minimalny i leksykograficznie maksymalny podciąg
malejący o długości k, gdzie
k jest wynikiem powyższego algorytmu. Jak również możemy się zastanowić nad efektywnym
algorytmem znajdowania liczby wszystkich takich ciągów długości k.
 
==== Proste Pakowanie====
Załóżmy, że mamy n pudełek, każde o rozmiarze R, oraz n przedmiotów o rozmiarach <math>R \ge 
r[1]\ge r[2]\ldots \ge r[n]</math>. Mamy włożyć przedmioty do pudełek, co najwyżej dwa do jednego
pudełka.  Pozostawiamy jako ćwiczenie analizę następującego algorytmu, który oblicza minimalną
liczbę pudełek.
{{algorytm|Proste-Pakowanie|algorytm_proste_pakowanie|
<math>wynik := n;</math>
'''for''' <math>i := 1</math> to n do
    '''if''' <math>(i < wynik</math>  and <math> r[i]+r[wynik] <= R)</math>
      <math>wynik := wynik-1;</math>
}}
 
<center><flash>file=Klocki.swf|width=450|height=250</flash></center>
 
Naiwne wersje powyższych sześciu algorytmów  działają w czasie kwadratowym. W każdym z tych
algorytmów bardzo proste spostrzeżenia prowadzą do algorytmów liniowych.
Podamy jeszcze jeden bardzo krótki ciekawy algorytm (chociaż bez żadnego widocznego
zastosowania praktycznego).
 
==== Permutacje wagowe====
Przypuśćmy, że mamy wagę
szalkową, początkowo obie szalki sa puste, oraz mamy odważniki o numerach  1,2,..n. Waga i-tego
odważnika wynosi <math> a_i</math>.
Dla danej permutacji <math>\Pi</math> numerów odważników będziemy je wkładać na wagę
zgodnie z permutacją. Kładziemy kolejno odważniki
w kolejności <math> \Pi </math> na lewą lub prawa szalkę, raz położony odważnik nie zmieia już
nigdy swego położenia na szalce (wybór szalki jest dosyć
niedeterministyczny). Otrzymujemy ciąg wyników ważenia: +1 gdy lewa szalka  przeważa, wpp. -1.
Ciąg ten oznaczamy przez Input.
Mówimy że  permutacja <math> \Pi </math> jest zgodna z ciągiem wyników ważeń danych tablicą
Input. Zajmiemy się problemem: dany
jest na wejściu ciąg Input wyników ważeń i mamy znalezć
jakąkolwiek permutację <math> \Pi </math> zgodną z ciągiem Input. Takich permutacji może być
wiele. Zauważmy, że
liczba permutacji wynosi n!, a liczba ciągów wyników ważeń wynosi <math> 2^n</math>, co jest
liczbą znacznie mniejszą. <br>
Następujący algorytm znajduje pewną permutację zgodną.
Zakładamy że
 
<center> <math> a_1<a_2<a_3<\ldots a_n</math></center>
 
{{algorytm|Permutacja-Wagowa|algorytm_permutacja_wagowa|
    <math> p:=1; q:=n;</math>
    '''for'''  <math>i:=n  </math> '''downto''' <math>1</math> '''do'''
      '''if''' <math>(i>1)\ \textrm{and}\  (Input[i-1] \ne Input[i])</math>)
        <math> Wynik[i]:= q; q:=q-1; </math>
      '''else '''
          <math> Wynik[i] := p; p:=p+1</math>;
}}
 
Jeśli Input = [+1,+1,+1,-1,-1,-1,+1,+1,-1], to Wynik = [6 5 4 7 3 2 8 1 9].
 
 
 
Ciąg wejściowy jest zrealizowany przez następujący ciąg wyborów wkładania kolejnego odważnika
na wagę:
 
    L  P  L  P  P  L  L  P  P
 
gdzie L oznacza połóż na lewą szalkę, P na prawą.
Korzystając (tylko częściowo) z dialeku C++ można zapisać algorytm krócej
 
 
{{algorytm|Permutacja-Wagowa1|algorytm_permutacja_wagowa|
    <math> p:=1; q:=n;</math>
    '''for'''  <math>i:=n  </math> '''downto''' <math>1</math> '''do'''
      '''if''' <math>(i>1)\ \textrm{and}\  (Input[i-1] \ne Input[i])</math>)
        <math> Wynik[i]:= q-- </math>; '''else ''' <math> Wynik[i] := p++ </math>;
}}
 
Wynik algorytmu pozostawia pewien ''niedosyt'', generujemy dobry wynik ale
w pewnym sensie jakikolwiek dobry. Nie jest jasne, jak policzyć efektywnie liczbę wszystkich
permutacji zgodnych z danym ciągiem wyników, albo
znależć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią.
Co będzie jeśli tablica Input zawiera również zera (wagi szalek są równe). Wtedy nie każdy ciąg Input
jest realizowalny.  Jak to można efektywnie sprawdzać?
 
== Koszt zamortyzowany ==
Jeśli mamy ciąg operacji <math>op_1,op_2,\ldots, op_n</math> to koszt zamortyzowany jednej z
nich jest sumarycznym kosztem
wykonania wszystkich operacji podzielonym przez liczbę operacji, inaczej mówiąc jest to, dla danego
ciągu operacji, średni koszt jednej z nich. Zauważmy,
że nie mówmy tu nic o prawdopodobieństwie, model jest deterministyczny. Na przykład w algorytmie
Najbliższy-Mniejszy-Sąsiad rozważmy ciąg operacji
 
<math>op_i</math>: while <math>( A[j] >= A[i])\ j = Lewy[j]</math>
 
Koszt pojedyńczej operacji może być liniowy, również sumaryczny koszt ciągu tych operacji
<math>op_1,op_2,\ldots, op_n</math> jest liniowy. Zatem
pesymistyczny koszt jednej operacji jest tutaj liniowy, natomiast zamortyzowany koszt jednej operacji
jest  ograniczony przez stałą. W tym przypadku
wiemy, że każde sprawdzenie <math>A[j]>=A[i])</math> z wynikiem negatywnym
odbywa się tylko raz dla danej wartości <math>j</math>. Możemy powiedzieć, że księgujemy koszt
operacji elementom <math>j</math>
 
o tej własności. Nieformalna metoda księgowania kosztów polega na rozdzielaniu (księgowaniu)
kosztu, a
następnie szacowaniu sumarycznej złożoności poprzez sumowanie wszystkich zaksięgowanych
kosztów. Operacje
pożyczają, w pewnym sensie, fundusze na pokrycie kosztów z różnych źródeł. Metoda ta będzie
wykorzystana
do analizy algorytmu dla interesującego problemu Find-Union.
 
Typowym przykładem liczenia kosztu w sposób zamortyzowany jest analiza generacji kolejnych
reprezentacji binarnych kolejnych liczb naturalnych od 0 do <math>2^n-1</math>,
dodając jedynkę. W jednym kroku zastępujemy najdłuższy ciąg jedynek od końca zerami, następnie
wstawiamy
jedną jedynkę. Ponieważ w sumie wstawiliśmy <math>2^n-1</math> jedynek w ciągu <math>2^n-
1</math> operacji, to zamortyzowana
liczba operacji zamiany zera na jedynkę wynosi 1.
 
''Zasada magazynu.''
W ostatnim  przykładzie możemy powiedzieć, że analizowaliśmy
koszt tzw. ''metodą magazynu''. W każdej operacji koszt jest proporcjonalny do liczby przedmiotów
włożonych
do magazynu lub do liczby przedmiotów wyjętych z magazynu. Magazyn początkowo jest pusty.
Wtedy całkowity
koszt jest proporcjonalny do liczby przedmiotów włożonych. W przypadku generowania liczb
binarnych do magazynu
wkładamy nowe jedynki, a wyjmujemy te jedynki, które zamieniamy na zera.
 
=== Potencjał - Fundusz Ubezpieczeń Kosztów Algorytmicznych===
 
Metodę magazynu można uogólnić na tzw. metodę potencjału. Niech <math>\Phi_i</math> będzie
pewną liczbą naturalną (włączając zero) odpowiadającą potencjałowi
po wykonaniu <math>i</math> operacji. Zakładamy, że potencjał jest początkowo zero, nigdy nie jest
ujemny, a każda operacja <math>op_i</math> ma
koszt proporcjonalny do <math>|\Phi_i-\Phi_{i-1}|</math>. Wtedy całkowity koszt jest tego samego
rzędu co <math> \sum c_i</math>.
W naszych poprzednich przykładach rozmiar magazynu jest w tym sensie potencjałem.
 
Można powiedzieć obrazowo że potencjał jest kapitałem Funduszu Ubezpieczeń Kosztów
Algorytmicznych. Koszt zamortyzowany jednej operacji jest składką,
którą ta operacja wpłaca do funduszu.
 
Operacja najpierw wpłaca swoją składkę a następnie pobiera z funduszu tyle, żeby proporcjonalnie
(być może z dokładnością do stałego współczynnika) zaplacić za swój koszt wykonania.
 
Dzięki temu, że wiele operacji pobiera z funduszu znacznie mniej niż wpłaca niektóre operacje mogą
jednorazowo pobrać dużą kwotę, którą płacą za koszt wykonania. Operacje <math>op_i</math>
ubezpieczają się od kosztów ich
wykonani. Poszczególne operacje płacą drobne składki <math>c_i</math>, a swój koszt za każdym
razem opłacają biorąc pieniądze z Funduszu.
Czasami koszt operacji jest duży ale do tego czasu wpłacono tyle drobnych składek,że możemy ten
koszt pokryć. Istotne jest jedynie
żeby Fundusz nie zbankrutował i kapitał nie zszedł poniżej zera. Możliwa jest również sytuacja gdy
Fundusz startuje
z kapitałem początkowym. Wtedy kapitał ten wlicza
się do całkowitego kosztu algorytmu, który się dodajemy do sumy składek.
 
Rozważmy  przykłady ilustrujące wykorzystanie potencjału. Najistotniejsze jest określenie składek
 
==== Tablica dynamiczna====
Przypuśćmy, że mamy dynamiczną tablicę. W każdym momencie wiemy ile elementów w tablicy jest
aktywnych, elementy nieaktywne zaznaczamy. W
każdej operacji, jeśli liczba elementów nieaktywnych jest mniejsza od <math>\frac{1}{4}</math>
wielkości tablicy to tworzymy tablicę
dwa razy mniejszą i tam przepisujemy elementy aktywne, starą tablicę zwalniamy. W przeciwnym
wypadku jeśli chcemy dodać element,
który spowoduje przepełnienie tablicy to całą tablicę kopiujemy do tablicy dwa razy większej.
Początkowo tablica ma rozmiar 1.
Zakładamy, że operacją dominującą jest kopiowanie aktywnego elementu do nowej tablicy. Jeśli
mamy <math>n</math> operacji to
całkowity koszt kopiowania jest liniowy. Wystarczy w każdej operacji dać składkę 4 jednostek do
Funduszu (potencjału). 
Wtedy koszt jednej dużej operacji przepisywania  zamortyzuje się zmianą potencjału.
 
 
==== Zastąpienie kolejki dwoma stosami====
Jedną kolejkę Q można zastąpić dwoma stosami <math>S1,\ S2</math>. Jeśli pierwszy element stosu
lub kolejki w
reprezentacji poziomej jest w ciągu na pierwszej pozycji (tzn. pobieramy <math>e_1</math>,
stawimay za <math>e_n</math>),
oraz <math> Q = (e_1,e_2,..,e_k)</math> to dla pewnego <math>j </math> mamy:
 
<math>S1 = (e_n,e_{n-1},...,e_j),\ S2 = (e_{1},e_{2}, ...,e_{j-1})</math>.
 
Inaczej mówiąc pierwszy element kolejki jest na wierzchołku drugiego stosu, a
ostatni lement kolejki jest wierzchołku pierwszego stosu.
 
Operacja wstawiania do A odpowiada wstawieniu elementu do <math>S1</math>, operacja pobrania
z Q odpowiada pobraniu elementu z S2
z tym, że jeśli <math>S2</math> jest pusty to przepisujemy najpierw wszystkie elementy z S1 do S2.
Niech operacją dominującą
będzie jedna operacja stosowa (wstawienie lub pobranie pojedynczego elementu ze stosu). Wtedy ciąg
<math>n</math> operacji
kolejkowych, startujących od pustej kolejki, ma koszt liniowy w tej implementacji. Wystarczy, że
każda operacja wkłada do Funduszu
składkę 3 jednostek. Dowód tego pozostawiamy jako ćwiczenie.
 
==== Zastąpienie kolejki dwustronnej  trzema stosami====
Roważmy podobny problem, z tym że nasza kolejka jest dwustronna, możemy wkładać i pobierać
element z każdego z dwóch końców kolejki.
Wtedy możemy taką kolejkę zastąpić trzema stosami tak, że teraz również każda operacja kolejkowa
będzie mieć zamortyzowany koszt stały.
Elementy kolejki trzymamy w dwóch stosach S1, S2 tak jak poprzednio. Niezmiennikiem jest to, że
oba stosy są niepuste lub mają w sumie co
najwyżej jeden element. Zapewniamy zachodzenie niezmiennika wykorzystując trzeci stos. W
momencie gdy jeden ze stosów ma więcej niż jeden element a
drugi jest pusty, korzystając z trzeciego stosu, doprowadzamy do reprezentacji aktualnej kolejki przez
stosy S1, S2, tak aby miały one tę samą
liczbę elementów (z dokładnością do 1). Pozostawiamy jako ćwiczenie dowód (metodą potencjału)
tego, że zamortyzowany koszt jest stały.
[[Grafika:Example.jpg]]

Aktualna wersja na dzień 09:29, 2 sty 2007

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

Opis

Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.

Sylabus

Autorzy

  • Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Adam Malinowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Tomasz Waleń — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

Wymagania wstępne

  • Wstęp do programowania
  • Metody programowania
  • Matematyka dyskretna
  • Logika i teoria mnogości

Zawartość

  • Podstawowe zasady analizy algorytmów:
    • poprawność
    • złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana)
    • koszt zamortyzowany: metoda potencjału
  • Podstawowe techniki i struktury:
    • metoda dziel i zwyciężaj
    • metoda zachłanna
    • pogramowanie dynamiczne
    • transformacyjna konstrukcja algorytmu
    • elementarne struktury danych: stosy, kolejki, listy
  • Sortowanie:
    • sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
    • proste kolejki priorytetowe: kopce binarne
    • HeapSort
    • sortowanie pozycyjne
    • złożoność problemu sortowania
  • Selekcja:
    • algorytm Hoare'a
    • algorytm magicznych piątek
  • Wyszukiwanie i proste słowniki:
    • wyszukiwanie liniowe i binarne
    • prosty słownik: drzewa poszukiwań binarnych
    • haszowanie
  • Efektywne implementacje słownika:
    • drzewa AVL
    • drzewa typu splay
    • B-drzewa
  • Złożone struktury danych:
    • wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego
    • efektywne sumowanie zbiorów rozłącznych
  • Algorytmy grafowe:
    • DFS i jego zastosowania
    • problemy ścieżkowe -- Algorytm Dijkstry
    • minimalne drzewo rozpinające
  • Wyszukiwanie wzorca w tekstach:
    • prefikso-sufiksy
    • algorytm Knutha-Morisa-Pratta
  • Tekstowe struktury danych:
    • tablice sufiksowe
    • drzewa sufiksowe
  • NP-zupełność:
    • klasa NP
    • problemy NP-trudne i NP-zupełne

Moduły

Literatura

  1. Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
  2. Wprowadzenie do algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych&oldid=68278”