Użyteczność algorytmu:
poprawność
złożoność obliczeniowa
złożoność czasu
Złożoność obliczeniowa – ilość zasobów systemu liczącego potrzebny do jednego działania.
Zasoby podstawowe – czas procesora, obszar pamięci
Złożoność czasowa – zależy od wszystkich jednostkowych czynności wykonywanych podczas realizacji algorytmu;
Największy wpływ ma złożoność obliczeniowa
Najczęściej algorytmy mają złożoność czasową proporcjonalną funkcji:
log(n)-złożoność logarytmiczna
n- złożoność liniowa
n log(n) – liniowo – logarytmiczna
n^2- kwadratowa
n^k – wielomianowa
2^n – wykładnicza
n! – wykładnicza ponieważ n!>2n już od n=4
Czynności jednostkowa:
wykrywanie operacji arytmetycznych (dodawanie, odejmowanie, mnożenie…)
nadanie wartości zmiennej
zbadanie relacji lub wykonanie operacji logicznej
wprowadzenie danej
Własności poprawnie skonstruowanego algorytmu:
Uniwersalność – pozwala rozwiązać całą klasę działań
Ścisłość –zarówno czynności algorytmu jak i kolejność wykonywania operacji dostatecznie jasno i wyraźnie
Jednoznaczność – wykonanie prowadzi do tych samych wyników
Kompletność – algorytm uwzględnia wszystkie możliwe przypadki
Skończoność – rozwiązanie po skończonej ilości kroków
Struktura danych:
sposób uporządkowania informacji w komputerze np. rekord, tablica, graf, kolejka i stos
Grafy to struktura danych która odgrywa ważną role w algorytmice. Stosuje się je do rozwiązań różnego rodzaju problemów algorytmicznych – znajdowanie optymalnych dróg, obmyślanie strategii gry, rozwiązywania łamigłówek oraz rozwiązywanie wielu złożonych problemów technicznych.
Graf drzewa:
do reprezentacji hierarchii np. mistrzostwa sportowych
do opisu rozwoju populacji
GPS
gry komputerowe, systemy sztucznej inteligencji
projektowanie robotów mobilnych
przedstawiania sieci komputerowych
protokół RIP
Rodzaje grafów:
Eulera
Hamiltona
Algorytmy obliczania optymalnych dróg w grafie:
Roy-Warshall
Floyd – Warshall
Dijkstry
Bellmana – Forda
Algorytm Dijkstry
służy do wyznaczania najmniejszej odległości do ustalonego wierzchołka.
graf nie może zawierać krawędzi o ujemnych wagach.
zbiór Q wierzchołków dla których nie obliczono jeszcze najkrótszej scieżki
wektor D[i] odległość od wierzchołka s do i
Q – zawiera wszystkie wierzchołki
D – pierwszy wiersz macierzy wag krawędzi A
s – początek
Relaksacja krawędzi – sprawdzanie czy przy przejściu daną krawędzią grafu (u,v) „u” do „v” nie otrzymamy krótszej niż dotychczasowa ścieżka z „s” do „v”
Algorytm Dijkstry jest oparty o strategie zachłanną
Algorytm Bellmana – Forda:
opiera się na założeniu że wagi są w grafie ujemne
bazuje na tym protokół RIP
wyższa złożoność czasowa
Eksploracja danych:
integruje dyscypliny: statystyka, systemy baz danych, sztuczna inteligencja, optymalizacja, obliczanie równoległe, algorytmy
z eksploracją danych mamy takie styczności podczas wyszukiwania danych w sieci Internet
Odkrywanie asocjacji – najszersza klasa metod obejmująca odkrywanie różnego rodzaju niezależnych zależności w bazie danych. Metody te obejmują głównie odkrywanie asocjacji pomiędzy obiektami. Generalnie odkrywanie zależności posiadają pewne miary statystyczne określające ich wsparcie i ufność.
Klastrowanie – celem tych metod jest znajdowanie skończonego zbioru klas obiektów w bazie danych posiadających podobne cechy
Odkrywanie wzorców sekwencji – odkrywanie czasowych wzorców zachowań
Odkrywanie klasyfikacji – zależność pomiędzy klasyfikacją obiektów a ich charakterystyką
Odkrywanie prawdopodobieństw w przebiegach czasowych - znajdowanie podobieństw czasowych opisujących określone procesy
Wykrywanie zmian i odchyleń – znajdowanie różnic pomiędzy aktualnymi a oczekiwanymi wartościami danych.
Odkrywanie asocjacji jest prostym probabilistycznym stwierdzeniem o współwystępowaniu zdarzeń w zbiorze danych i ma szczególne zastosowanie przy rzadkich zbiorach transmisyjnych.
Dokładniejsze charakterystyki algorytmów odkrywania asocjacji dokonanym na przykładzie ich najczęstszego wykorzystania czyli w tzw. podejścia do analizy koszykowej (MBA)
Problem: Analiza koszyków zakupowych klienta :
Dane zgromadzone są w bazie w której obserwacje składają się z bieżącego koszyka produktów a zmienne wskazują czy produkt został zakupiony
Dane w takim podejściu (binarnym) można przedstawić jako macierz o „n” wierszach i „p” kolumnach
Rozmiar takiej macierzy może być bardzo duży
CEL: odnalezienie grup produktów zakupionych razem przez klientów
Celem MBA – znalezienie wzorca zachowań klientów sklepów, marketów czy hali targowych
Dzięki analizie MBA odkrywamy preferencje zakupowe klientów i ich upodobania i przyzwyczajenia
Odkryte wzorce zachowań są następnie wykorzystywane w celu organizacji produktów na półkach sklepowych
DANY JEST ZBIÓR ATRYBUTÓW(PRODUKTÓW)
P{P1,P2,P3…P8}
OBSERWACJA
{01,…,012}
Jedynki i zera w tablicy obserwacji oznaczają czy dany produkt został zakupiony
Wynikiem odkrywania asocjacji są reguły asocjacyjne mające postać:
IF A=1 AND B=1 THEN C=1
Z prawdopodobieństwiem “p” gdzie A,B,C są zmiennymi binarnymi a p=p(C=1, A=1, B=1) tzw. jest prawdopodobieństwem warunkowym C=1 pod warunkiem A=1, B=1
Prawdopodobieństwo warunkowe „p” jest nazywane ufnością lub dokładnością a p(C=1, A=1, B=1)
wsparciem
PROGI:
pa- minimalna ufność (miniconf)
ps- minimalne wsparcia(minsup)
Analiza sytuacji: minsup=50% minconf=50%
Transakcja Produkty
1 A,B,C
2 A,C
3 A,D
4 B,E,F
A=>C gdzie Sup=50% i conf = 66,6%
C=>A gdzie Sup=50% i conf=100%
W przedstawionej powyżej bazie danych mamy transakcje oraz produkty (A,B,C,D,E,F). Dla założenia że interesują nas reguły malejące minsup=50% oraz min conf = 50% możemy wyróżnić następujące reguły asocjacyjne:
A=>C gdzie Sup=50% i conf = 66,6%
C=>A gdzie Sup=50% i conf=100%
Wsparcie- określa liczbę transakcji w analizowanych zbiorze D.
Wsparcie reguły określa liczbę klientów których zachowanie jest zgodne z dana regułą
Reguły mające niewielkie wsparcie są mało reprezentatywne. Natomiast reguły mające wysokie wsparcie są najczęściej mało interesujące dla analityka
Ufność danej reguły oznacza jej poziom pewności. Reguły mające ufność są mało wiarygodne.
SORTOWANIA
Algorytm stabilny – elementy o równej wartości będą występowały po posortowaniu w takiej samej kolejności jak w zbiorze nie posortowanym
bąbelkowy O(n^2)
przez wstawianie O(n^2)
przez scalanie O(n log(n))
kubełkowy O(n)
Niestabilny:
przez wybieranie O(n^2)
grzebieniowe (nieznana)
szybkie: optymistyczny O(n log(n));pesymistyczny O(n^2)
przez kopcowanie O(n log(n))
Klasyfikacja:
złożoność- zależność liczby wykonywanych operacji w stosunku od liczebności sortowanego zbioru (n). Typową złożonością jest średnia złożoność O(n log(n)), pesymistyczną O(n^2) a idealną O(n).
sposób działania – algorytmy sortujące za pomocą porównań to takie algorytmy sortowania których sposób wyznaczania porządku jest oparty wyłącznie na wynikach porównań między elementami. Dla takich algorytmów dobre ograniczenie złożoności O(n log(n)).
stabilność – trzymanie kolejności wystąpień dla elementu o tym samym kluczu.
SORTOWANIE KUBEŁKOWE
algorytm działa w czasie liniowym O(n)
najlepiej działa dla dużej ilości elementów
pesymistyczna złożoność O(n^2)
sortowanie liczb od 0 do 1
klasa złożoności O(m+n) gdzie „m” ilość możliwych wartości a „n” ilość sortowanych elementów
Dynamiczne struktury danych – zespół elementów inaczej węzły które są reprezentowane przez rekordy, zmieniają skład, wymiary i strukturę podczas wykonywania programu. Przykładem są: listy i drzewa. Do konstrukcji dynamicznych struktur danych stosuję się wskaźniki. Typy wskaźnikowe nie są strukturalne więc należą do typów skalarny.
Liść – to element nie mający potomków
Węzeł wewnętrzny – to każdy węzeł w strukturze drzewa nie będący korzeniem ani liściem.
Stopniem węzła – określamy liczbę przyporządkowanych mu potomków
Długość ścieżki wewnętrznej drzewa określamy jako sumę długości ścieżek wszystkich elementów drzewa.
LISTA JEDNOKIERUNKOWA:
Każdy element jest pojedynczym rekordem składający się z co najmniej dwóch wartości pól: pola wartości i wskaźnika. Nie jest możliwy bezpośredni dostęp do dowolnego jej elementu. Dotarcie do n-tego elementu listy wymaga wcześniejszego przejścia przez n-1 poprzedników.
Możliwość operacji na liście:
wstawanie na początek
wstawanie elementu na koniec
usunięcie pierwszego
odczyt pierwszego
LISTA DWUKIERUNKOWA:
Dla każdego składnika poza pierwszym i ostatnim jest określony składnik poprzedni i następny.
STOS: możliwe wstawianie, odczytywanie i usuwanie pierwszego (LIFO)
KOLEJKA(pojedyncza, jednokierunkowa):wstawianie elementu na koniec listy, odczyt i usuwanie pierwszego(FIFO)
Najszybsze sortowania:
szybkie
kubełkowe
wybór
bąbelkowe
Drzewo binarne
drzewem drugiego stopnia każdy jego węzeł może mieć co najwyżej dwóch potomków.
typ podstawy T
skończony zbiór elementów który jest pusty
zawiera korzeń z dwoma rozłączonymi binarnymi drzewami lewym i prawym pod drzewem korzenia
Przykład:
drzewo genetyczne
zapis rozgrywanych turniej
Operacje:
metody przeglądania drzewa:
PREORDER przejście wzdłużne
POSTORED przejście wsteczne
INORDER przejście poprzeczne
KRYPTOGRAFIA
cel – umożliwienie bezpiecznego przesyłu danych
Wymagania wobec szyfru:
algorytm SiD powinny być wydajny
dla dowolnych MiK musi zachodzić D(K,S(K,M)) = M
szyfr musi być bezpieczny
Jak zdefiniować bezpieczny szyfr:
Zasada KERCKHOFFS:
Szyfr (S,D)musi być bezpieczny nawet jeśli Ewa zna algorytm SiD. Ewa nie zna klucza K.
Zły pomysł:
Szyfr jest bezpieczny jeśli Ewa nie potrafi zgadnąć wiadomości M na podstawie szyfrogramu
C=S(K,M)
Definicja bezpieczeństwa mówimy że szyfr jest (t,α) bezpieczny jeśli żadna Ewa dysponująca czasem t nie potrafi zgadnąć czy Alicja wybrała M czy N prawdopodobieństwem większym 0,5t α
Idealny szyfr powinien być bezpieczny (∞,0)
Doskonały szyfr Vermana mówi że klucz musi być tej samej długości co wiadomość. Nie można używać klucza wielokrotnie.
Twierdzenie Shannona – każdy doskonałym szyfrze klucz nie może być krótszy niż wiadomość
Takie szyfry są niepraktyczne
Wyjątki: korespondencja dyplomatyczna i wojskowa
Szyfry stosowane w praktyce(np. t=10000000 i α=0,0000001)
Powszechnie używane są szyfry: RSA, DES, AES.
Hipoteza P= NP algorytm dla pewnej klasy problemów. Hipoteza dotycz szybkich algorytmów działających w czasie wielomianowym.
Algorytm RSA
jednym z 1. i najpopularniejszych asymetrycznych algorytmów kryptograficznych
kryptografia klucza publicznego to rodzaj kryptografii który używa się zestawu dwu lub więcej powiązanych kluczy umożliwiających wykonanie wielu czynności kryptograficznych. Jeden może być udostępniony publicznie bez utraty bezpieczeństwa
pierwszy który można było używać do szyfrowania i podpisów szyfrowych
bezpieczeństwo szyfrów opiera się na trudności faktoryzacji
Generowanie kluczy:
Wybieramy dwie liczby pierwsze p i q
Obliczamy n=pq
Obliczamy wartość Eulera ϕ(n)= (p-1)(q-1)
wybieramy liczbę e(1<e<ϕ(n)) pierwszą z ϕ(n)
Znajdujemy liczbę d odwrotną do e mod ϕ(n) d=e-1mod ϕ(n)
Klucz publiczny jest definiowany jako para liczb (n,e) natomiast kluczem prywatnym jest para (n,d)
Problem korni wojażera
Podróż z miasta do miasta sprzedając swoje produkty. Wyrusza z rodzinnego miasta po czym jego trasa przebiega dokładnie jeden raz przez każde miasto.
Miasta to wierzchołki grafów a trasy to krawędzie z wagami
Waga krawędzi odpowiada odległości pomiędzy miastami
Problem jest oparty o cykl Hammiltona.
Przykład:
Ile różnych cykli Hammiltona zawiera taki graf:
jedną krawędź cyklu można wybrać na 9 sposobów
po wyborze 1 krawędzi pozostaje 8,…7,…6,….
w efekcie otrzymujemy LH=9*8*7*6*5*4*3*2*1=9! `Złożoność obliczeniowa równa O(n!)
dla każdego znalezionego cyklu Hammiltona liczymy sumę wag krawędzi i zapamiętujemy cykl o najmniejszej sumie wag
Przykład 2.
Gaf ma 100 wierzchołków
każdy wierzchołek łączy się z czterem innymi wierzchołkami grafu zatem ilość stopni. Z jednego wierzchołka możemy iść na cztery różne sposoby, z drugiego na 3 a 98 na 3. Z czego wynika LH=4*3^99
Zatem graf LH w przybliżeniu (S-1)^n
Podsumowanie:
liczba cykli lub ścieżek do przechodzenia rośnie wykładniczo
duże wartości mogą być rozwiązywane przez stulecia
istnieją algorytmy o zbliżonych rozwiązaniach ale są trudne w implementacji
ALGORYTMY GENETYCZNE :
ALGORYTMY GENETYCZNE SŁUŻĄ do optymalizacji zadań.
Optymalizacja jest to wyznaczanie sposobów dopuszczalnych rozwiązań najlepszego ze względu na przyjęte kryterium.
- Metoda ukierunkowanego przeszukiwanie optymalnego(żródłem problemeu głównie są ekstrema lokalne )
- Metoda przypadkowego przeszukiwania
Funkcja Rastragina obrazuje trudności jakie można napotkać przy poszukiwaniu optimum.
Od problemu minimów lokalnych wolne są propabilistycznie metody optymalizacji.
Stochastyczne przeszukiwanie rozwiązań nie gwarantuje sukcesu.
Metody wyspecjalizowane są dobre przy specyficznych cechach zadania.
Na bazie tych obserwacji, powstała koncepcja żeby przeszukiwaniami optymalnego rozwiązania uzyskanego za pomocą komputera kierował proces ewolucji.
Obliczenia ewolucyjne – algorytmy genetyczne, programowanie ewolucyjne, strategie ewolucyjne.
Metody ewolucyjne:
- powstały i zostały rozwinięte w celu żeby znajdować przybliżone rozwiązania, problemów optymalizacji(znajdować szybko i unikać płapek lokalnych)
- rozwój technik obliczeniowych
- postęp wiedzy o ewolucji biologicznej
- osiągnieć nowych teori optymalizacji
Sposób działania algorytmu genetycznego:
- określenie sposobu kodowania żeczywistych parametrów problemu w postaci hromosomu
- przyjęcie postaci funkci przystosowania oceniającej analizowany zestaw parametrów pod względem jakosci poszukiwanego rozwiązania
- losowy dobór punktów startowego zestawów parametrów
- selekca najlepiej przystosowanych hromosomów do nowej poplacji
- zastosowanie na nowej populacji operatorów genetycznych w postaci krzyżowania i mutacji
- sprawdzenie wartości funkcji przystosowania
Chromosom – to forma organizacji materiału genetyzcnego wewnątrz komórki
Punktem wejścia jest opisanie rozważanego zadania w kategoriach wektora (najczęściej binarnego zwanego chromosomem)
00101001 < - cecha kodowania na tej pozycji występuje w rozwiązaniu.
^ cecha kodowania na tej pozycji nie występuje w rozwiązaniu.
Wprzypadku algorytmów genetycznych można mówić o dwóch typach interpretacji podejść.
- Michigan (wszystkie osobniki są traktowane jako jednoski. Poszczególne osobniki populacji rywalizują ze sobą, chcą przetrwać )
- Pittsburg (całą populacje traktuję się jako jednostkę która podlega działaniu operatorów genetycznych)