Algorytmy i Złożoność, Algorytmy i złożoności, Algorytmy i złożoności

Algorytmy i Złożoność

Strona startowa

[ Pobierz całość w formacie PDF ]

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 pracylProblem, algorytm, złożoność obliczeniowa, czasowa i pamięciowa, problem decyzyjny, problem optymalizacyjny;llProjektowanie efektywnych algorytmów;llSortowanie;llWyszukiwanie, selekcja;llMnożenie macierzy i operacje pokrewne;llAlgorytmy w grafach;llArytmetyka na liczbach całkowitych;llAlgorytmy dopasowania wzorców;llHierarchia złożoności problemów;llNierozstrzygalność;lLiteratura

· 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

WYKŁAD1.1 PojęciaInformatyka

· 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 lreguła przekształcania zbioru znaków n inny zbiór znaków (funkcja matematyczna)llzbiór obrazów otrzymany za pomocą tego przekształcenial

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:

logólny opis jego parametrów,llzdanie stwierdzające, czym powinna charakteryzować się odpowiedź, czyli rozwiązaniel

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 = {m1, m2, ..., mr} - skończony zbiór miast

D= {d12, d13, ..., d1r, d23, d24, ..., d2r, ..., d(r-1)r} - zbiór liczb określających odległości między miastami, przy czym dij oznacza odległość pomiędzy mi oraz mj

Rozwiązanie problemu

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

i=1r-1dfi* f(i+1)+ dfr* f(1)

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

Przypadek szczególny:

M = {m1, m2, m3, m4},

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

Rozwiązanie: (m3, m2, m4, m1),

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:lPrzez 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 nieparzystymllPrzez 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 nieparzystyml

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:

lprzekształca wejściowy ciąg danych w ciąg wyjściowy,llzatrzymuje się w skończonym czasielWszystkie problemy można podzielić na dwie klasy:lNiealgorytmiczne (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;llAlgorytmiczne.l

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:

lpozwolimy komputerowi pracować dostatecznie długo,llbędzie wyposażony w tak dużo pamięci, jak potrzebuje.l

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ł:lproblemy łatwe obliczeniowe,llproblemy trudne obliczeniowolProblem trudny obliczeniowo:

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

a) n = 3

b) n = 128

dla n = 3

dec

bin

000

001

... [ Pobierz całość w formacie PDF ]

Linki


Copyright � 2006 Sitename.com. Designed by Web Page Templates

Darmowy hosting zapewnia PRV.PL