Niero

Niero

z

z

strzygalnoś

strzygalnoś

ć

ć

i złożoność

i złożoność

algorytmiczna

algorytmiczna

Algorytm

Komputery przetwarzają przekazywane im informacje
z wykorzystaniem pewnych algorytmów. Program jest

algorytmem zapisanym w języku zrozumiałym dla maszyny

Jeżeli dany algorytm da się wykonać na maszynie o

dostępnej mocy obliczeniowej i pamięci oraz

akceptowalnym czasie,
to mówi się że jest

obliczalny

obliczalny

Poprawne działanie większości algorytmów

implementowanych w komputerach opiera się na kolejnej

realizacji pewnego zestawu warunków. Jeżeli, któryś z nich

nie zostanie spełniony, to program kończy się

komunikatem

błędu

błędu

Struktura danych

(ang. data structure) - sposób uporządkowania informacji

w komputerze. Na strukturach danych operują algorytmy
Przykładowe struktury danych to:

* tablica

* lista

* stos

* kolejka

* graf
* drzewo i jego liczne odmiany (np. drzewo binarne)
* rekord, zwany w niektórych językach po prostu

strukturą (ang. struct, record), logiczny odpowiednik

to krotk

Rozmiar zadania

Rozmiar zadania (problemu) to rozmiar tych
danych wejsciowych, których
ilość wpływa na czas wykonania algorytmu,
tzn. im większa jest ilość tych
danych tym dłużej realizuje się algorytm.

Operacja elementarna

Operacja elementarna (inaczej operacja
dominujaca) to operacja
charakterystyczna dla danego algorytmu.

To taka operacja, której łączna liczba
wykonań jest proporcjonalna do rozmiaru
zadania, tzn. im większy rozmiar
zadania tym więcej razy realizuje się
operacja elementarna.

Nierozstrzygalność

algorytmów

Problem stopu- nazywamy nim taką sytuację,

gdy dla danego algorytmu i danych wejściowych

należy stwierdzić, czy program realizujący dany

algorytm zatrzyma się
Algorytm ma własność stopu, gdy dla każdych

danych początkowych wykonane obliczenia są

poprawne i skończone
Nie zawsze jest możliwe rozstrzygnięcie. Na

przykład nie istnieje algorytm, który rozstrzyga,

czy dwa λ-wyrażenia są równoważne lub czy

maszyna Turinga dla danego wejścia się zatrzyma

Dowód poprawności

algorytmu

Dowód poprawności algorytmu jest
rozumowaniem matematycznym
prowadzącym do formalnego
wykazania, że dany algorytm przy
poprawnych danych wejściowych
da nam wynik spełniający
wymagania

Dowód poprawności

algorytmu

Dowód poprawności algorytmu
zawsze składa się z dwóch części:

* dowód, że jeśli algorytm się

zakończy, to da poprawny wynik

* dowód, że przy poprawnych

danych

wejściowych algorytm

zawsze się zakończy

Dowód poprawności

algorytmu

W ogólnym przypadku pytanie Czy dany

algorytm jest poprawny? jest nierozstrzygalne
Dla większości języków opisu algorytmów

nierozstrzygalne są nawet pytania:

*

C

C

zy dane dwa algorytmy dają taki sam wynik

zy dane dwa algorytmy dają taki sam wynik

?

?

*

C

C

zy dany algorytm dla poprawnych danych

zy dany algorytm dla poprawnych danych

wejściowych się kończy

wejściowych się kończy

?

? (nawet przy

założeniu, że zawsze jesteśmy w stanie

zweryfikować poprawność danych

wejściowych)

Teoria obliczeń

Dział informatyki teoretycznej
Dzieli się na dwie główne części:

–

teorię obliczalności

teorię obliczalności (zajmuje się

odpowiedzią na pytanie, które problemy
dają się rozwiązać przy pomocy
komputera)

– oraz

złożoność obliczeniową

złożoność obliczeniową (zajmuje

się tym jak szybko da się rozwiązać
problem)

Teoria złożoności

obliczeniowej

Dział teorii obliczeń
Głównym jej celem jest określanie ilości zasobów

potrzebnych do rozwiązania problemów

obliczeniowych
Rozważanymi zasobami są takie wielkości jak

czas

czas,

pamięć

pamięć lub

liczba procesorów

liczba procesorów.

Za twórców tej teorii uważani są

Juris

Juris

Hartmanis

Hartmanis i

Richard Stearns

Richard Stearns

Jako przykłady problemów teorii można podać:

problem spełnialności, problem najkrótszej

problem spełnialności, problem najkrótszej

ścieżki, problem faktoryzacji

ścieżki, problem faktoryzacji

Czym jest złożoność

algorytmu?

Ilość zasobów komputerowych potrzebnych dla

działania algorytmu może być rozumiana jako

jego

złożoność

złożoność

Zasoby komputerowe

Zasoby komputerowe to czas działania i ilość

zajmowanej pamięci

W zależności od rozważanego zasobu mówimy

o złożoności

czasowej

czasowej lub

pamięciowej

pamięciowej

Złożoność algorytmu

Im większy rozmiar danych
wejściowych tym więcej zasobów
(czasu, procesorów, pamięci) jest
potrzebnych do rozwiązania
algorytmu

Złożoność algorytmu jest więc funkcją
rozmiaru danych wejściowych

Złożoność czasowa

algorytmu

Złożoność czasowa algorytmu określa „czas” realizacji

algorytmu
W charakterze czasu wykonania rozpatrujemy zwykle liczbę

operacji podstawowych (dominujących). Operacjami

podstawowymi mogą być na przykład: podstawienie,

porównanie lub prosta operacja arytmetyczna.
Złożoność czasowa musi być niezależna od:
- szybkości procesora, który wykonuje algorytm,
- wyboru języka programowania, w którym

wykonana jest implementacja algorytmu

Złożoność czasowa

algorytmu

Z

Z

łożoność

łożoność

czasowa pesymistyczna

czasowa pesymistyczna to

ilość wykonanych operacji elementarnych
dla danych „najgorszego” przypadku

Złożoność

Złożoność

czasowa oczekiwana

czasowa oczekiwana to ilość

wykonanych operacji elementarnych dla
danych „typowego” przypadku.

Złożoność pamięciowa

algorytmu

Złożoność pamięciowa jest miarą ilości
wykorzystanej pamięci
Jako tę ilość najczęściej przyjmuje się
użytą pamięć

maszyny abstakcyjnej

maszyny abstakcyjnej

(na przykład liczbę komórek pamięci
maszyny RAM) w funkcji rozmiaru wejścia
Możliwe jest również obliczanie rozmiaru
potrzebnej pamięci fizycznej wyrażonej w
bitach lub bajtach

Klasy złożoności

Klasa złożoności to zbiór problemów

obliczeniowych o podobnej złożoności

obliczeniowej - innymi słowy: problemy,

do których rozwiązania potrzebna jest

podobna ilość zasobów łączymy w klasy
Stosuje się też szersze pojęcia takie jak

– klasa P- decyzyjne problemy

wielomianowe

– NP- decyzyjne problemy podlegające

wielomianowej weryfikacji, jeśli

odpowiedź jest twierdząca

ZADANIA

1. Co to znaczy, że algorytm jest obliczalny?
2. Wskaż zdanie fałszywe:

Tablica, rekord, stos to przykładowe struktury

danych.
Im większa jest ilość danych wejściowych tym

krócej realizuje się algorytm.

3. Zajmuje się tym, jak szybko da się

rozwiązać problem:

Teoria obliczalności
Złożoność obliczeniowa

ZADANIA

4. Podaj nazwiska twórców teorii

złożoności obliczeniowej.

5. Co to jest złożoność algorytmu?
6. Jakie są rodzaje złożoności

algorytmu? Uzupełnij schemat:

Złożoność algorytmu

ZADANIA

7. Co to jest klasa złożoności?
8. Co określa złożoność czasowa

algorytmu?

9. Na czym polega problem stopu?
10.Czy pytanie „Czy dane dwa

algorytmy dają taki sam wynik?”
jest rozstrzygalne?