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?