Algorytmy i problemy

ALGORYTM



Algorytmem nazywamy skończony ciąg potencjalnie

wykonalnych instrukcji wyrażonych w określonym języku.



Słowo „algorytm” pochodzi od nazwiska Muhammad ibn

Musa al-Chuwarizmiego matematyka perskiego z IX

wieku



Od „dobrego” algorytmu wymagamy własności:

-skończoności

-określoności

-ogólności

-skuteczności



Przykład: przepis na zupę, program mnożenia na

maszynie Turinga

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ALGORYTM FORMALNIE



=<X,E,S,f>

gdzie:

X jest zbiorem wszystkich par (P,j) w których p jest

słowem w pewnym alfabecie A a j literą spoza tego

alfabetu oznaczającą dodatnią liczbę całkowitą (co

najwyżej ζ) para ta oznacza j-ty etap rachunku

E (podzbiór X) zawiera pary postaci (P, 1) czyli dane

wejściowe na poziomie każdego etapu

S (podzbiór X) jest zbiorem par (P,ζ) czyli zbiorem

wyników otrzymanych na poszczególnych etapach

f jest przekształceniem X w X (nakłada się kilka

warunków)

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ALGORYTMY SEKWENCYJNE I RÓWNOLEGŁE



Algorytm sekwencyjny wykonuje instrukcje
szeregowo, jedna po drugiej



Algorytm równoległy wykonuje pewną liczbę
instrukcji jednocześnie



Równoległe przetwarzanie informacji zachodzi
w mózgach i systemach nerwowych

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ALGORYTMY SEKWENCYJNE I RÓWNOLEGŁE



Jeżeli szukamy czegoś w pokoju sprawdzając

miejsce po miejscu to realizujemy sekwencyjny

algorytm przeszukiwania



Jeżeli szukamy ze znajomymi to równoległy



Zagadnienie równoważności przetwarzania

równoległego i sekwencyjnego jest ważne dla

rozumienia procesów zachodzących w układach

nerwowych, w szczególności jest powiązane z

występowaniem „nieświadomości” i kompleksów

autonomicznych

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ALGORYTM PROBABILISTYCZNY



Algorytm wykorzystujący generowanie losowe do

wykonania instrukcji,

np.:

jeżeli a<m to

a+random



albo wybierania instrukcji:

losowo jedno z (a,b,c) gdzie a,b,c są komendami

lub podprogramami



albo

tworzenia instrukcji (np. algorytmy genetyczne)



Albo…

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

METODY MONTE CARLO



Metody Monte Carlo wprowadził Stanisław Ulam



Przykład: obliczanie powierzchni koła
niech będzie dane koło o powierzchni x
umieszczone w kwadracie o powierzchni
jednostkowej.



Losowo wybieramy punkty w obrębie kwadratu,
ponieważ prawdopodobieństwo trafienia w każdy
punkt jest takie samo to stosunek liczby trafień w
koło do trafień w cały kwadrat dąży do x/1 czyli x.

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

LOGIKA ROZMYTA



W „klasycznych” rachunkach logicznych
przyjmujemy tylko dwie wartości v (verum, 1) i f
(faulus, 0) czyli prawdę i fałsz



W logice rozmytej dopuszczamy wartości
pośrednie



Twórcą logik rozmytych jest Lotfi Zadeh
(właściwie Lotfi Aliskerzadeh) urodzony w 1921
w Baku w Azerbejdżanie

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ZBIORY ROZMYTE



Podstawowym pojęciem logik rozmytych i
rozmytej teorii mnogości jest stopień
przynależności do zbioru:

Czytamy: x należy do zbioru w stopniu n gdzie n
należy do przedziału domkniętego [0,1]

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

]

[

;

)

(

ZBIORY ROZMYTE



Narzędzie jakim są zbiory rozmyte umożliwia
opisywanie przypadków przejść ciągłych np.
„problemu łysiny” (od utraty którego włosa
zaczyna się łysina)

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ALGORYTM ROZMYTY



To algorytm korzystający z rozmytej logiki/teorii
mnogości



Najczęściej przez algorytm rozmyty rozumie się
algorytm zawierający instrukcje rozmyte



Na przykład instrukcje w rodzaju „dodaj trochę
soli”

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

REALIZACJA INSTRUKCJI ROZMYTEJ



Instrukcja rozmyta realizowana jest w praktyce
zazwyczaj przez losowanie (z zastosowaniem
generatora losowego lub pseudolosowego)
wartości z pewnego uprzednio wyznaczonego
przedziału (określa się np. zakres
odpowiadający sformułowaniu „trochę soli”)

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ZASTOSOWANIA ALGORYTMÓW ROZMYTYCH



Algorytmy rozmyte są stosowane w budowie
systemów ekspertowych, zastosowaniach
inżynierskich, eksploracji danych



Wchodzą w skład systemów inteligentnych
(wraz z np. ewolucyjnymi czy sieciami
neuronowymi)

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

LOSOWOŚĆ VS PSEUDOLOSOWOŚĆ



Generator pseudolosowy oblicza łańcuch liczb stosując

określoną formułę obliczeniową. Na przykład wartość pewnej

funkcji. W kolejnych krokach wartość wprowadzana jest jako

argument. Wybieramy funkcje, które dają w efekcie wartości

odpowiadające pewnemu rozkładowi prawdopodobieństwa



Generatory pseudolosowe generują łańcuchy

kompresowalne ponieważ dają się one skompresować do

długości kodu. Dlatego ich użycie (np. w kryptografii) jest

ograniczone



Generatory losowe nie bazują na obliczeniach lecz są

urządzeniami fizycznymi



Generatory losowe dają (z największym

prawdopodobieństwem) łańcuchy niekompresowalne

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

HEURYSTYKI



Heurystyki nie gwarantują ściśle optymalnego
rozwiązania problemu (podobnie jak algorytmy
probabilistyczne) a sposób rozwiązywania nie
jest „teoretycznie” dokładnie ustalony



Przykład: przeszukiwanie „intuicyjne” pokoju w
którym coś zgubiliśmy



Heurystykami są np. algorytmy ewolucyjne,
genetyczne, mrówkowe itp.

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ALGORYTMY GENETYCZNE



Pierwsze opracował John Henry Holland ale już

Turing zajmował się ich teorią



Algorytmy genetyczne odtwarzają procesy

zachodzące w przyrodzie takie jak:

- rozmnażanie

-zmienność losowa

-krzyżowanie (kombinowanie „genów”)

-selekcja (funkcja dostosowania)



Niestety nie mamy czasu na dokładniejsze

omówienie

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ALGORYTM MRÓWKOWY



Mrówki poruszają się losowo



Po znalezieniu pokarmu mrówka wraca do
mrowiska pozostawiając ślad feromonalny



Po pewnym czasie feromon wietrzeje



To wystarczy do rozwiązywania np. problemu
komiwojażera i podobnych

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

PHYSARUM



Śluzowiec też potrafi rozwiązywać rozmaite
problemy



Przykład heurystyki „naturalnej”

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

ZŁOŻONOŚĆ OBLICZENIOWA



Złożoność obliczeniową problemu określamy
jako czas (maszynowy) potrzebny do jego
rozwiązania



Jest to złożoność czasowa



Stosujemy też wskaźnik złożoności pamięciowej
wyznaczanej przez wymaganą pojemność
pamięci

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

PROBLEMY ŁATWE, P



Problemy łatwe to takie, które dają się
rozwiązać w czasie wielomianowym: O(an

)

gdzie a,z są stałymi a n oznacza rozmiar danych
wejściowych



Problemy takie potrafimy rozwiązywać w
praktyce przy pomocy realnych komputerów i
„zwykłych” algorytmów sekwencyjnych

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

PROBLEMY TRUDNE



Problemy nazywamy trudnymi jeżeli potrzebny
na ich rozwiązanie czas jest większy niż
wielomianowy, np. wykładniczy : O(z

)



W praktyce takie problemy są często
nierozwiązywalne ponieważ nie mamy
wystarczających mocy obliczeniowych ale
„teoretycznie” nie sprawiają kłopotów (Bogu
Laplace’a)

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

PROBLEMY NP I NPC



Problem (decyzyjny!) nazywamy problemem NP.

jeżeli jest sprawdzalny w czasie wielomianowym

ale niekoniecznie rozwiązywalny w takim czasie.



Przykład: czy zbiór {1, 2, 7, -3, 12, -5} zawiera

podzbiór sumujący się do zera?



Problem nazywamy NP zupełnym (NPC) jeżeli jest

tak trudny jak dowolny inny problem NP (istnieje

sposób przekształcenia go w dowolny inny)



Dlatego rozwiązanie jednego NPC jest

równoznaczne z rozwiązaniem wszystkich

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

PROBLEM MILENIJNY: PvsNP



Czy każdy problem NP jest problemem P?



Wystarczy rozwiązać zagadnienie dla jednego
problemu NP-zupełnego aby rozwiązać je dla
wszystkich



Uważa się, że P≠NP przedstawiono kilka
dowodów jeszcze nie zweryfikowanych

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

PROBLEMY NIEROZSTRZYGALNE



Problem nazywamy nierozstrzygalnym jeżeli dla
każdego algorytmu istnieje dowolnie wiele
zestawów danych przy których algorytm jest
nieefektywny

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

PROBLEMY WYSOCE NIEROZSTRZYGALNE



Problem nazywamy wysoce nierozstrzygalnym

jeżeli sprowadzenie go do nierozstrzygalnego jest

także nierozstrzygalne



Problemy nierozstrzygalne i wysoce

nierozstrzygalne nie należą do rzadkich. Wiele

problemów związanych z pokrywaniem powierzchni

dominem lub parkietażem należy do tej klasy



Uwaga! Heurystyki radzą sobie ze wszystkimi

takimi problemami, choć oczywiście na swój,

specyficznie ograniczony, sposób

kognitywistyka 2010 Kajetan Młynarski

zfnp uj

GRANICE MATEMATYKI



Przyczyna dla której systemy nerwowe nie

realizują (wyłącznie) algorytmów sekwencyjnych

jest natura naszego świata obfitującego w

problemy nierozstrzygalne



Istnieją twierdzenia, które są prawdziwe ale nie

da się ich dowieść, wiele z nich jest ważnych

dla życia, można je odkrywać metodami

heurystycznymi (filozofowie często próbowali

dowodzenia lub uzasadniania)

kognitywistyka 2010 Kajetan Młynarski

zfnp uj