ALGORYTMY I PROBLEMY

W ujęciu kognitywistycznym

kognitywistyka 2010 Kajetan Młynarski ZFNP UJ

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



A

=<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

]

1

,

0

[

;

)

(

n

n

Z

x

f

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

PHYSARUM

kognitywistyka 2010 Kajetan Młynarski zfnp uj

PHYSARUM OBLICZA

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

z

)

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

n

)



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

PARKIETAŻE PENROSEA

kognitywistyka 2010 Kajetan Młynarski zfnp uj

PARKIETAŻE PENROSEA

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