Algorytmy i Złożoność

Egzamin:

I termin:

I4 - środa, 09.02.2011, 9:30

poprawka:

Wszyscy - 23.02.2011, 9:30

Plan godzinowy

Wykłady: 30

Ćwiczenia: 15

Laboratoria: 15

Plan pracy

1. Problem, algorytm, złożoność obliczeniowa, czasowa i pamięciowa, problem decyzyjny, problem optymalizacyjny;

2. Projektowanie efektywnych algorytmów;

3. Sortowanie;

4. Wyszukiwanie, selekcja;

5. Mnożenie macierzy i operacje pokrewne;

6. Algorytmy w grafach;

7. Arytmetyka na liczbach całkowitych;

8. Algorytmy dopasowania wzorców;

9. Hierarchia złożoności problemów;

10. Nierozstrzygalność;

Literatura

• Aho Hopcroft Ullman - "Projektowanie i analiza algorytmów", wyd. Helion, Gliwice 2003

• Balinska - "Projektowanie algorytmów i struktury danych", wyd. PP, Poznań 2003

• Banachowski diks rytter algorytmy I strukturyy danych, wnt, wawa 2006

• Bilski chmiel stoklosa zbior zaadan zze złozonosci obliczeniowej algorytmow, wyd pp, pzn 1992

• Knuth sztuka programowania, wnt, wawa, 2002

Strona internetowa

www.sk-kari.put.poznan.pl/stoklosa

WYKŁAD

1.1 Pojęcia

Informatyka

• nauka o przetwarzaniu, gromadzeniu i przesyłaniu informacji za pomocą środków technicznych (komputerów)

Dane

• dowolne wiadomości przetwarzane przez komputer, zapisane w pewnym alfabecie

Alfabet

• skończony zbiór znaków

Słowo

• skończony ciąg znaków w pewnym alfabecie

A* - Zbiór wszystkich słów w alfabecie A

A = {0, 1}

A* = {e¹, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}

Podzbiór L zbioru A

Język (formalny)

L c A*

(L zwiera się w A*); to miał być znaczek c z podkreśleniem (symbol inkluzji)

Słowo binarne (zero-jedynkowe)

• słowo określone za pomocą znaków z alfabetu binarnego

{0, 1} - zbiór wszystkich słów binarnych

Jeśli słowa binarne maja ustalona długość n to mówimy o słowie /znaku/ n-bitowym

Kod

1. reguła przekształcania zbioru znaków n inny zbiór znaków (funkcja matematyczna)

2. zbiór obrazów otrzymany za pomocą tego przekształcenia

1.2 Algorytm, problem

Algorytm

• procedura stosowana (sposób postępowania prowadzący) do rozwiązania problemu

Problem

• pytanie ogólne, na które należy udzielić odpowiedzi, zależne od ilości parametrów

Problem jest zadany, gdy przedstawimy:

1. ogólny opis jego parametrów,

2. zdanie stwierdzające, czym powinna charakteryzować się odpowiedź, czyli rozwiązanie

Przypadek szczególny problemu uzyskuje się wówczas, gdy ustali się wartości wszystkich parametrów problemu

Przykład: problem komiwojażera² (problem optymalizacyjny)

Opis

• W celu zebrania zamówień na towar komiwojażer musi odwiedzić r miast

Odległości między miastami są znane

Pytanie

• W jakiej kolejności powinien odwiedzać miasta, aby w każdym z nich być dokładnie jeden raz i wrócić do miasta, z którego rozpoczął podróż, przebywszy najmniejszą liczbę kilometrów?

Parametry problemu:

M = {m₁, m₂, ..., m_r} - skończony zbiór miast

D= {d₁₂, d₁₃, ..., d_1r, d₂₃, d₂₄, ..., d_2r, ..., d_(r-1)r} - zbiór liczb określających odległości między miastami, przy czym d_ij oznacza odległość pomiędzy m_i oraz m_j

Rozwiązanie problemu

• uporządkowana r-tka miast (m_f(1), m_f(2), ..., m_f(r)), taka, że suma odległości

$$\sum_{i = 1}^{r - 1}{d_{f\left( i \right)*\ f(i + 1)} + \ d_{f\left( r \right)*\ f(1)}}$$

jest najmniejsza, przy czym f jest funkcją porządkującą miasta

Przypadek szczególny:

M = {m₁, m₂, m₃, m₄},

D = {594, 303, 343, 389, 320, 303}

Rozwiązanie: (m₃, m₂, m₄, m₁),

Przebyta odległość: 1355 km

Przykład II: Problem Eulera (problem decyzyjny)

Pytanie

• Czy w grafie istnieje ścieżka przechodząca przez wszystkie krawędzie jeszcze jeden raz?

Przypadek szczególny

• zagadka mostów na Pregole

TU BYŁ OBRAZEK

Twierdzenie Eulera:

1. Przez wszystkie krawędzie grafu można przejść w sposób ciągły, przechodząc przy tym przez każdą krawędź dokładnie jeden raz <=> graf jest spójny i nie ma wierzchołków o nieparzystym stopniu, albo ma dokładnie dwa wierzchołki o stopniu nieparzystym

2. Przez wszystkie krawędzie można przejść w sposób ciągły wracając do wierzchołka wyjściowego, przechodząc przy tym przez każdą krawędź dokładnie jeden raz <=> graf jest spójny i nie ma wierzchołków o stopniu nieparzystym

Stopień wierzchołka

• Liczba krawędzi wierzchołka

Każdy problem optymalizacyjny można zredukować do problemu decyzyjnego

Problem decyzyjny

• pytanie ogólne, na które należy dać odpowiedź "tak" lub "nie"

π = (D_π, Y_π)

D_π - zbiór wszystkich przypadków

Y_π - zbiór przypadków, dla których odpowiedź brzmi "tak"

Algorytm

• skończony ciąg dobrze zdefiniowanych operacji, który:

1. przekształca wejściowy ciąg danych w ciąg wyjściowy,

2. zatrzymuje się w skończonym czasie

Wszystkie problemy można podzielić na dwie klasy:

1. Niealgorytmiczne (nierozstrzygalne) - takie, dla których rozwiązujący je algorytm nie istnieje (wymagany jest dowód); nie może być rozwiązany w skończonym czasie;

2. Algorytmiczne.

Problem niealgorytmiczny: problem stopu

• Czy istnieje program komputerowy³ orzekający, że każdy inny program zatrzyma się

Problem rozwiązywalny algorytmicznie (algorytmiczny)

• Problemy dla których można napisać program poprawny dla każdej danej wejściowej, pod warunkiem, że:

1. pozwolimy komputerowi pracować dostatecznie długo,

2. będzie wyposażony w tak dużo pamięci, jak potrzebuje.

Zakładamy, że z każdym problemem jest związane określone kodowanie:

kod: {I: I ∈D_π} →A*

Rozmiar wejścia (długość) przypadku I problemu π:

n = |kod(I)|

Dla przypadku komiwojażera:

A= {m, (, ), /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

kod(I) = m(1)/m(2)/m(3)/m(4)//594/303/343/389/320/303

n = |kod(I)| = 44

Inne rozmiary problemów:

• liczba wierzchołków grafu,

• liczba krawędzi grafu,

• stopień macierzy kwadratowej,

• itd.

1.3 Złożoność obliczeniowa algorytmów (problemów)

Podział:

1. problemy łatwe obliczeniowe,

2. problemy trudne obliczeniowo

Problem trudny obliczeniowo:

• Problem generowania wszystkich ciągów binarnych o długości n

1. n = 3

2. n = 128

dla n = 3

dec^4	bin^5
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

dla n = 128

Liczba wszystkich ciągów o długości 128:

2¹²⁸

Jeśli do wytworzenia jednego ciągu potrzeba 1 µs⁶, to wygenerowanie wszystkich ciągów:

2¹²⁸ * 10^-6s ≈ 1.078 * 10²⁵ lat

!! Wiek Ziemi: 3.6 * 10⁹ lat

Dla n = 128 zadanie jest trudne

<< TUTAJ BYŁO PEŁNO CYFEREK I NIE PRZEPISAŁEM

Problem łatwy: mnożenie liczb

np. 387x523=202401

Problem trudny: rozkład liczby złożonej

np. Liczba 155-cyfrowa (512-bitowa; maksymalnie może to być 768 bitów)

---

1. e - ciąg pusty↩

2. komiwojażer - przedstawiciel handlowy↩

3. program komputerowy jako algorytm↩

4. dec - dziesiętne↩

5. bin - binarne↩

6. 1 µs - mikrosekunda↩