Egzamin Teoria

1. Przez czasową złożoność obliczeniową (ang. time computational complexity lub time complexity) rozumiemy ilość czasu niezbędnego do rozwiązania problemu w zależności od liczby danych wejściowych. Złożoność czasowa jest zatem pewną funkcją liczby danych wejściowych:

T(n) = f(n)

Na przykład:

T(n) = 4n2 - 3n + 15

Złożoność czasową wyrażamy albo w jednostkach czasu, albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie problemu. Operacja dominująca jest operacją, której wykonanie bezpośrednio wpływa na czas wykonania całego algorytmu. Podawanie złożoności czasowej w jednostkach czasu jest niewygodne, ponieważ wynik zależy od szybkości komputera, na którym dokonano pomiarów - trudno takie wyniki odnieść do innych komputerów, szczególnie wyposażonych w inne procesory, gdzie czas wykonania podobnych operacji może znacznie się różnić. Dlatego częściej złożoność czasową wyrażamy w liczbie operacji dominujących, gdyż każdy komputer, bez względu na swoje własności, operacje te musi wykonać. Dzięki temu wynik uniezależniamy od faktycznej szybkości komputerów.

2. Złożoność pamięciowa (ang. space computational complexity lub space complexity) określa z kolei liczbę komórek pamięci, która będzie zajęta przez dane i wyniki pośrednie tworzone w trakcie pracy algorytmu.

Zatem podsumowując:

Złożoność optymistyczna określa zużycie zasobów dla najkorzystniejszego zestawu danych.

Złożoność średnia określa zużycie zasobów dla typowych (tzw. losowych) danych.

Złożoność pesymistyczna określa zużycie zasobów dla najbardziej niekorzystnego zestawu danych.

3. Poprawność algorytmów

Algorytm A jest semantycznie poprawny względem warunku początkowego α i warunku końcowego β, gdy dla każdych danych spełniających warunek α działanie algorytmu A dochodzi do końca i wyniki spełniają warunek β.

sp(α, A, β)

A jest częściowo poprawny względem α i β, gdy dla każdych danych spełniających α: jeżeli działanie A

dochodzi do końca, to wyniki spełniają β. cp(α, A, β)

A spełnia warunek określoności obliczeń, gdy A zadziała (obliczenia nie zostaną przerwane) dla każdych danych spełniających warunek α.

obl(α, A)

A ma własność stopu, gdy dochodzi do końca dla każdych danych spełniających α (obliczenia nie są nieskończone).

stop(α, A)

sp(α, A, β) wtw cp(α, A, β) i obl(α, A) i stop(α, A)

4. Metody dokładne rozwiązywania problemów pozwalają uzyskać dokładne, czyli optymalne rozwiązanie badanych problemów.

»Efektem działania tych metod jest więc wskazanie jednego lub kilku konkretnych stanów pochodzących z przestrzeni stanów, dokładnie odpowiadających specyfikacji stanu końcowego w tej przestrzeni.

»Aby osiągnąć ten cel, metody dokładne muszą zwykle w jakiś sposób przeglądać całą przestrzeń stanów, co często powoduje, że nie są one na tyle efektywne, aby mogły być stosowane do rozwiązywania nietrywialnych problemów, czyli takich, które dotyczą przeszukiwania przestrzeni o dużej liczbie stanów.

Strategie heurystyczne

Poprawa skuteczności i efektywności metod dokładnych jest możliwa poprzez dopasowanie kierunków przeszukiwania przestrzenia stanów do potrzeb aktualnie rozwiązywanego problemu.

Metody aproksymacyjne

•W rzeczywistości ścieżka badana przez strategie heurystyczne nie zawsze musi zaprowadzić do optymalnego stanu końcowego.

»Dlatego metody heurystyczne często prowadzą do znalezienia rozwiązania prawie optymalnego, czyli takiego, które nie jest wprawdzie rozwiązaniem optymalnym, ale jest zadawalające z punktu widzenia wymagań stawianych szukanemu rozwiązaniu w obliczu praktycznych zastosowań tego rozwiązania.

•Rozwiązania takie często nazywamy rozwiązaniami aproksymacyjnymi lub inaczej rozwiązaniami przybliżonymi.

•Metody pozwalające uzyskać rozwiązania aproksymacyjne nazywamy metodami aproksymacyjnymi lub inaczej metodami przybliżonymi.

Metody dokładne różnią się od aproksymacyjnych tym, że dokładne zawsze znajdują optymalne rozwiązanie problemu, natomiast aproksymacyjne często znajdują rozwiązanie prawie optymalne oraz tym, że metody dokładne przeszukują całą przestrzeń stanów, natomiast aproksymacyjne przy użyciu strategii heurystycznych przeszukują tylko daną cześć tych stanów.

5. Działanie metod „brutalnej siły” polega na mechanicznym przeglądaniu wszystkich stanów należących do przestrzeni przeszukiwania. Nazwa tych metod bierze się stąd, że nie wykorzystują one zwykle żadnych informacji o strukturze przestrzenie stanów, a komputer wykorzystują jedynie jako szybkie narzędzie do „mało inteligentnego” przeszukiwania.

Dobra metoda „brutalnej siły” musi zagwarantować, aby każdy stan był sprawdzany dokładnie jeden raz.

Oznacza to, że nie może być pominięty żaden ze stanów, gdyż w ten sposób podczas poszukiwań mógłby być pominięty poszukiwany stan końcowy. Oprócz tego żaden ze stanów nie powinien być sprawdzany wielokrotnie, gdyż tak sytuacja mogłaby znacznie spowolnić przeszukiwanie przestrzeni stanów. Zastosowanie tej metody wymaga więc ustalenia pewnego porządku zgodnie z którym będą przeglądane stany. Porządek przeglądania stanów zwykle jest ustalany zupełnie bez uwzględnienia ewentualnych reguł (zasad) przechodzenia pomiędzy stanami.

Etapy rozwiązywania:

1. Zdefiniowanie przestrzeni stanów zawierającą wszystkie możliwe konfiguracje tych obiektów

środowiska badanego problemu, od których zależy rozwiązanie tego problemu.

2. Wyspecyfikowanie opisu stanów końcowych, które mogą być zaakceptowane jako rozwiązanie problemu.

3. Określenie porządku przeglądania wszystkich stanów gwarantujący dotarcie do każdego stanu

dokładnie jeden raz.

4. Dokonanie przeglądu wszystkich stanów według ustalonego wcześniej porządku, w celu znalezienia stanu lub stanów końcowych, przy czym możliwe są trzy następujące sytuacje:

» znalezienie tylko jednego stanu końcowego o zadanych własnościach,

» wyszukanie wszystkich stanów końcowych,

» wyszukanie jednego, ale optymalnego pod jakimś względem stanu końcowego.

5. Zinterpretowanie stanu końcowego jako rozwiązanie problemu

6. Przeszukiwanie z powracaniem

•W literaturze opisywane jest wiele metod wyboru operatorów podczas eksploracji przestrzeni stanów w celu wygenerowania i sprawdzenia nowego stanu.

•Jedną z nich jest metoda oparta na tzw. strategii przeszukiwania z powracaniem (z nawrotami)

»Polega ona na tym, że dla wybranego stanu generowany jest za pomocą jednego z operatorów tylko jeden stan potomny i jeżeli ten nowy stan można dalej rozszerzać przez stosowanie operatorów i nie jest on końcowy, to jest dalej rozszerzany (tylko ten jeden stan potomny).

»Gdy po kolejnych rozszerzeniach otrzymywany stan nie można już rozszerzać i nie jest on stanem końcowym, to wtedy w strategii z powracaniem następuje powrót do najbliższego przodka, dla którego możliwe jest wygenerowanie innych stanów potomnych.

7. Metoda „dziel i zwyciężaj”

•Stosowanie metody „dziel i zwyciężaj” polega na tym, że zamiast rozwiązywać wejściowy problem, który może być problemem trudnym, próbuje się wskazać jeden lub więcej innych problemów, które są łatwiejsze do rozwiązania, a ich rozwiązanie pozwala na skonstruowanie rozwiązania problemu wejściowego.

•Jedno z praktycznych podejść do rozwiązywania problemów metodą „dziel i zwyciężaj” jest następujące:

»Wejściowy problem jest dzielony na kilka mniejszych podproblemów podobnych do początkowego problemu, ale mających mniejsze rozmiary.

»Następnie podproblemy te są rozwiązywane.

»Na koniec rozwiązania wszystkich podproblemów są łączone w celu utworzenia rozwiązania problemu wejściowego.

Przykład: problem Fibonacciego(dwa podproblemy)

silnia(jeden podproblem)

8. Funkcje heurystyczne

•Przy przeszukiwaniu przestrzeni stanów strategie heurystyczne często wykorzystują wiedzę o dziedzinie danego problemu.

»Wiedza ta umożliwia charakterystykę analizowanych stanów i może być przydatna przy wyborze najbardziej obiecujących kierunków przeszukiwania.

•Do reprezentowania wspomnianej wiedzy zwykle wykorzystuje się pewne funkcje, zwane funkcjami heurystycznymi.

»Funkcje heurystyczne przyporządkowują poszczególnym stanom wartości numeryczne, które charakteryzują badane stany z punktu widzenia możliwości osiągnięcia z nich stanu końcowego.

•Wykorzystanie pojęcia funkcji heurystycznej natrafia jednak na pewną trudność

»Funkcje heurystyczne muszą być niestety konstruowane w sposób specyficzny do każdego z rozwiązywanych problemów.

Co wyraża funkcja heurystyczna?

•Numeryczna wartość funkcji heurystycznej f(s) wyraża ocenę stanu s ze względu na dwa następujące kryteria:

»zbieżność do stanu końcowego, czyli bliskość badanego stanu do stanu końcowego,

»koszt drogi wyznaczonej od stanu początkowego do stanu bieżącego.

•Z punktu widzenia funkcji heurystycznej, lepszym stanem jest zawsze taki stan, który jest bliższy stanowi końcowemu i koszt drogi do tego stanu od stanu początkowego jest możliwie najmniejszy.

9. Metoda wspinaczkowa

Strategia wspinaczkowa

•Postępowanie podejmowane w niesystematycznej strategii zachłannej jest podobne do akcji turysty atakującej szczyt wzniesienia.

»Chcąc jak najszybciej osiągnąć sukces, wybiera on aktualnie najlepszy kierunek, chociaż w trakcie dalszej wspinaczki decyzja ta może okazać się błędna i kierunek w danej chwili gorszy, może być w perspektywie całej wspinaczki lepszy.

•Ze względu na powyższą analogię, niesystematyczną strategię zachłanną nazywamy strategią wspinaczkową lub strategią wspinaczki górskiej.

Wada strategii wspinaczkowej

•Strategia wspinaczkowa ze względu na prostotę obliczeniową jest bardzo popularna.

•Jednak jej wadą jest brak możliwości powrotu do kierunków przeszukiwania, które na pewnym etapie były lokalnie gorsze.

•Może to oczywiście prowadzić do badania drogi prowadzącej do nie końcowego stanu, z którego nie można wygenerować żadnego innego stanu.

10. Algorytmy zachłanne

•Idee leżące u podstaw strategii wspinaczkowej formułuje się bardziej ogólnie w postaci tzw. algorytmów zachłannych.

•Algorytmy zachłanne cechują się tym, że zawsze wykonują działania, które w danej chwili wydają się najkorzystniejsze.

»W dłuższej perspektywie czasowej może się okazać, że działania te nie były takie korzystne...

Algorytmy zachłanne w życiu codziennym

•Podczas swej codziennej działalności, ludzie często stosują algorytmy zachłanne.

» Objawia się to tym, że rozwiązując jakieś zadanie zadawalamy się jego szybkim i w miarę poprawnym rozwiązaniem, choć niekoniecznie optymalnym.

•Algorytmy zachłanne nie zawsze prowadzą do optymalnych rozwiązań, choć dla wielu problemów rozwiązania jakie dostarczają algorytmy zachłanne są zupełnie wystarczające.

Stosowanie algorytmów zachłannych

•Algorytmy zachłanne stosujemy wtedy, gdy na podstawie pewnych danych wejściowych, należy szybko skonstruować rozwiązanie danego problemu.

»Algorytm zachłanny zawsze stara się jak najszybciej skonstruować rozwiązanie problemu, używając tych fragmentów danych wejściowych, które na danym etapie konstrukcji rozwiązania wydają się najbardziej użyteczne, tzn. w danym momencie najbardziej przybliżają do skonstruowania ostatecznego rozwiązania.

Przykład: problem wydawania reszty

•Klasycznym przypadkiem problemu, który można rozwiązać za pomocą algorytmu zachłannego jest problem wydawania reszty.

»Aby rozwiązać ten problem wystarczy zauważyć, że aby szybko wydać ustaloną kwotę pieniędzy (tzn. minimalną liczbą monet), trzeba wydawać możliwie największe nominały, aż do wydania całej reszty.

11. Metody stochastyczne (losowe)

•Działanie metod stochastycznych polega na tym, że zamiast systematycznie przeszukiwać całą przestrzeń stanów w celu znalezienia stanu końcowego, przegląda się tylko pewną liczbę stanów wybraną w większym lub mniejszym stopniu losowo, mając nadzieje, że pośród nich znajdzie się stan końcowy, będący rozwiązaniem optymalnym badanego problemu lub chociaż stan końcowy, będący zadawalającym nas rozwiązaniem prawie optymalnym.

»Każde rozwiązanie stochastyczne ma w sobie pewien element losowy, wyrażający się w niedeterministycznym wyborze kolejnych stanów, które są badane w czasie przeszukiwania przestrzeni stanów.

Metody globalne Stochastyczne metody globalne losowo przeszukują całą przestrzeń stanów traktując podobnie każdy z analizowanych stanów.

»Stochastyczne metody globalne nie wyróżniają podczas przeszukiwania żadnych konkretnych stanów.

»„Interesuje” je tylko to, na ile analizowany stan jest bliski stanowi końcowemu.

Metoda Monte Carlo

•Jedną z najprostszych stochastycznych metod globalnych jest metoda Monte Carlo.

•Metod Monte Carlo działa według następujących trzech kroków:

»losowana jest pewna liczba stanów,

»spośród wylosowanych stanów wybierany jest taki stan, który najbardziej jest zbliżony do wymagań stawianych optymalnemu stanowi końcowemu,

»otrzymany stan zwracany jest

Przykład: problem wydawania reszty

•Dla przykładu, zastosujemy metodę Monte Carlo do rozwiązania problemu wydawania reszty.

•Najprościej można to zrobić w ten sposób, że losuje się pewną liczbę konfiguracji monet, które pozwalają na wydanie ustalonej reszty i jako wynik zwracana jest ta konfiguracja, która ma najmniejszą liczbę monet.

12. Metody lokalne

•Stochastyczne metody lokalne charakteryzują się tym, że przeszukiwanie przestrzeni stanów rozpoczynają od jednego lub czasem kilku losowo wybranych stanów.

•Następnie sprawdzany jest stan (wybrany w większym lub mniejszym stopniu losowo), który w jakimś sensie jest stanem sąsiednim do analizowanego wcześniej stanu

»Na przykład stan ten jest bardzo bliski w sensie definiowanej wcześniej odległości pomiędzy stanami).

Błądzenie losowe

Strategia błądzenie losowe działa w ten sposób, że kolejny stan wybierany jest losowo spośród tych stanów, które możliwe są do osiągnięcia ze stanu bieżącego.

»Zatem strategia błądzenie losowe wykorzystuje operatory przejścia od stanu do stanu, przy czym przy każdym przejściu od stanu do stanu, wybierany jest losowo jeden operator spośród tych, które są możliwe do zastosowania w danym momencie.

Wady metody błądzenia losowego

•Strategia błądzenia losowego jest intuicyjnie zrozumiała i łatwa do zaimplementowania.

•Niestety posiada dwie następujące wady:

»jeśli w trakcie przeszukiwania przestrzeni stanów natrafimy na stan, który nie jest stanem końcowym i z którego nie można wygenerować innego stanu, to przeszukanie pozostałych stanów nie będzie możliwe,

»jeśli przeszukaliśmy już pewną liczbę stanów, to i tak nie jesteśmy w stanie określić, jaki czas pozostał do zakończenia procesu przeszukiwania.

Ograniczenie stosowania metody błądzenia losowego związane z koniecznością podania operatorów przejścia pomiędzy stanami

•Stosowanie strategii błądzenia losowego wymaga podania operatorów przejścia od stanu do stanu.

•W ogólnym przypadku podanie tych operatorów nie zawsze może być łatwe lub może ich być bardzo dużo.

•Dlatego metodę błądzenia losowego wygodnie jest stosować do problemów, dla których operatory przejścia od stanu do stanu są z góry określone lub są łatwe do zdefiniowania.

•Przy stosowaniu metody błądzenia losowego bardzo często otrzymujemy rozwiązania nieoptymalne.

13. Struktura danych (ang. data structure) to sposób uporządkowania informacji (danych).

»Na strukturach danych operują algorytmy.

Dwa sposoby spojrzenia na struktury danych

»abstrakcyjne struktury danych – koncepcyjne (twórcze, myślowe) ułożenie danych (informacji) w celu rozwiązania jakiegoś problemu algorytmicznego

–Przykłady: stos, kolejka, lista, słownik, drzewo, graf

»konkretne struktury danych – ułożenie danych w pamięci komputera z użyciem zmiennych konkretnych typów danych oraz rozmaitych technik programowania (np. reprezentowanie danych przy wykorzystaniu złożonych typów danych jak tablice, rekordy lub klasy, realizacja powiązań pomiędzy danymi przy zastosowaniu wskaźników lub referencji do porcji danych)

–Przykłady: tablica dynamiczna, lista powiązana, drzewo binarne, tablica haszująca

Konkretne struktury danych służą do implementacji abstrakcyjnych struktur danych

14. Lista w sensie abstrakcyjnym, to ciąg ponumerowanych elementów L=[x1,..., xn].

Skrajne elementy listy x1 i xn nazywają się końcami listy (lewy i prawy).

Liczba |L|=n jest długością (rozmiarem) listy L.

Szczególnym przypadkiem listy jest lista pusta: L=[]

Operacje na listach

Wstawianie elementu na listę

Usuwanie elementu z listy

Wyszukiwanie elementu na liście

Przeglądanie elementów z listy

Reprezentacja zbioru matematycznego

– brak relacji porządku wewnątrz zbioru

– brak duplikatów

• Brak nowych metod w stosunku do Collection

• najwaŜniejsze implementacje: HashSet, TreeSet

Insert(x,S) – wstawienie elementu x do zbioru S

Delete(x,S) – usunięcie elementu x ze zbioru S

Member(x,S) – sprawdzenie czy element x należy do zbioru S (wynikiem jest wartość true, gdy x należy do S i false wpp.

Union(A,B) – obliczenie sumy zbiorów A i B; zwraca nowy zbiór będący sumą A i B

Intersection(A,B) – obliczenie iloczynu zbiorów A i B; zwraca nowy zbiór będący iloczynem A i B

Difference(A,B) – obliczeni e różnicy pomiędzy zbiorami A i B

implementacje zbioru:

Tablicowa – elementy zbioru są reprezentowane w tablicy dynamicznej

Dowiązaniowa – elementy listy oraz struktura powiązań między nimi są przechowywane w pamięci za pomocą zmiennych wskaźnikowych (np. z użyciem listy powiązanej lub drzewa binarnego)

Za pomocą tablicy haszującej (podejście najefektywniejsze)

Zbiór posiada, odmienną niż lista, semantykę: nie zachowuje kolejności

elementów, natomiast wyklucza istnienie duplikatów. O elemencie można

zatem powiedzieć jedynie, czy należy do zbioru (w jednym egzemplarzu),

czy nie. Co ciekawe, interfejs ten nie definiuje żadnych nowych metod w

porównaniu do interfejsu Collection. Wynika to z faktu, że trudno wskazać

funkcjonalność, która wyróżniałaby zbiór od kolekcji. Warto zadać pytanie,

dlaczego zatem do jego reprezentacji powołano specjalny interfejs? Otóż

wskazanie, że określony obiekt jest typu Set niesie informację bardziej

szczegółową niż w przypadku zwykłej kolekcji, dlatego zostało to

podkreślone przez specjalny typ obiektu.

Podobnie, jak w przypadku listy, zbiór posiada w JDK kilka gotowych

implementacji. Jedną z nich jest HashSet, w którym unikatowość

elementów jest zapewniona przez zastosowanie tablicy asocjacyjnej; w

przypadku klasy TreeSet rolę tablicy pełni drzewo dwukolorowe.

15. Grafem G nazywamy uporządkowaną parę G=(V,E) składającą się z niepustego, skończonego zbioru wierzchołków (węzłów) V oraz zbioru krawędzi E czyli par wierzchołków ze zbioru V.

Rozpatrywane są dwa następujące rodzaje grafów:

»graf skierowany (zorientowany, digraf), gdy E jest podzbiorem zbioru par uporządkowanych ze zbioru V, tzn. EVxV

»graf nieskierowany (niezorientowany), gdy E jest podzbiorem zbioru wszystkich dwuelementowych podzbiorów zbioru V

Podstawowe nazewnictwo dotyczące grafów

Niech będzie dany n-wierzchołkowy graf G=(V,E) (skierowany lub nieskierowany).

»Drogą (ścieżką) w grafie G jest każdy skończony ciąg wierzchołków v0,v1,...,vk taki, że dla każdego i=0,...,k-1 krawędź pomiędzy vi i vi+1 jest krawędzią grafu G.

»Liczba k jest długością ścieżki

»O ścieżce v0,v1,...,vk mówimy, że łączy wierzchołki v0 i vk (lub prowadzi od v0 do vk, gdy graf jest skierowany)

»Wierzchołki v0 i vk nazywamy odpowiednio początkiem i końcem ścieżki

»O krawędzi łączącej dwa kolejne wierzchołki na ścieżce mówimy, że należy do tej ścieżki

»Długość najkrótszej ścieżki łączącej dwa wierzchołki v i w nazywamy ich odległością w grafie

Implementacje grafu

Podstawową implementacją grafu jest implementacja tablicowa

»Tablica służy do implementacji listy lub macierzy sąsiedztwa

Możliwa jest także implementacja dowiązaniowa

»Każdy wierzchołek „pamięta” wskaźniki do wierzchołków będących jego sąsiadami (dość niewygodne)

Drzewo

Drzewo to dowolny, nieskierowany graf spójny i acykliczny składający się z wierzchołków (węzłów) oraz łączących je krawędzi.

»Jeśli drzewo nie jest puste, tzn. liczba wierzchołków jest większa od zera, jeden z nich jest wyróżniony i nazywany korzeniem drzewa (na rysunku jest to F)

Ciąg krawędzi łączących węzły nazywa się ścieżką.

»Istnieje dokładnie jedna ścieżka łącząca korzeń z wszystkimi pozostałymi wierzchołkami.

Liczba krawędzi w ścieżce od korzenia do węzła jest nazywana długością ścieżki i liczba ta określa poziom węzła.

»Np. korzeń znajduje się na 0 poziomie, węzły A, D i I na poziomie 2

Wysokością drzewa jest liczba poziomów istniejących w drzewie

–Np. drzewo z rysunku ma wysokość 3

Podstawowe pojęcia dotyczące drzew

Wierzchołek jest rodzicem dla każdego swojego dziecka.

»Każdy węzeł ma dokładnie jednego rodzica, wyjątkiem jest korzeń drzewa, który nie ma rodzica.

Wszystkie wierzchołki połączone z danym wierzchołkiem, a leżące na następnym poziomie są nazywane dziećmi tego węzła

»Np. dziećmi wierzchołka F są B i G, natomiast wierzchołka B: A i D.

Wierzchołek może mieć dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest liściem

»Liśćmi w przykładowym drzewie są A, C, E, H.

Implementacja drzewa

Podstawową implementacją drzewa jest implementacja dowiązaniowa

Każdy wierzchołek „pamięta” wskaźniki do wierzchołków będących jego dziećmi

Możliwa jest także implementacja tablicowa tak jak w przypadku typowego grafu

16. Zbiór

Zbiór w sensie abstrakcyjnym, to kolekcja elementów S={x1,..., xn}, które nie są podane w żadnym ustalonym porządku.

Liczba |S|=n jest rozmiarem zbioru S.

Szczególnym przypadkiem zbioru jest zbiór pusty: S={}

Słownik

Słownik (mapa) – abstrakcyjny typ danych, który jest zbiorem par: (unikatowy klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza.

Podstawowe operacje na słowniku:

»Put(M,k,v) – wstawienie do słownika M wartości v z kluczem k. tj. pary (k,v)

»Get(M,k) – pobranie wartości dla klucza k

–Zwraca wartość dla klucza k lub wartość NULL, gdy nie ma takiej wartości

»ContainsKey(M,k) – sprawdzenie czy w słowniku jest wartość dla klucza k

–Zwraca true. gdy jest taka wartość lub false wpp.

»ContainsValue(M,v) - sprawdzenie czy w słowniku jest jeden lub więcej kluczy dla wartości v

–Zwraca true, gdy są takie klucze, wpp. zwraca false

»Remove(M,k) – usunięcie wszystkich par w których kluczem jest k

Implementacje słownika: za pomocą tablicy dynamicznej, listy powiązanej, drzewa binarnego lub tablicy haszowanej

Słownik jest zbiorem na którym możemy wykonywać tylko określone operacje, dodawania, wyszukiwania i usuwaniu elementów.

17. Tablica dynamiczna (zwana np. DynArray)

Konkretna struktura danych implementowana jako klasa oparta na tablicy, w której wprost przechowywane są elementy lub referencje (adresy) przechowywanych w strukturze elementów

»Pierwszy przypadek dotyczy sytuacji gdy elementy są wartościami typów konkretnych, tj. int, double, float, byte, char itd

»Drugi przypadek dotyczy sytuacji, gdy przechowywane elementy są wartościami typów obiektowych, czyli są egzemplarzami klas, np. String

W klasie jest prywatna zmienna tablicowa np. table, prywatna zmienna o nazwie np. nElems przechowująca aktualną liczbę elementów wstawionych do tablicy oraz publiczna metoda (np. size()), która zwraca wartość tej zmiennej

Konstruktor klasy zwykle określa maksymalną liczbę elementów które mogą zmieścić się w tablicy

W klasie jest metoda np. add, która wstawia element będący jej argumentem do tablicy (jednocześnie metoda ta zwiększa wartość licznika elementów)

W klasie jest metoda np. get, która zwraca element tablicy o podanym numerze (indeksie), przy czym numery elementów są od 0 do nElemes-1

W klasie jest metoda np. remove, która usuwa element o podanym numerze; jednocześnie metoda ta zmniejsza wartość licznika elementów

Relokacja tablicy.

Wstawienie elementu odbywa się na końcu tablicy O(1)

Wyszukiwanie jest liniowe O(n)

Usunięcie wymaga wyszukania elementu i przesunięcia elementów O(n)

18. Elementy uporządkowanej tablicy dynamicznej zawsze są ułożone względem jakiegoś porządku

W związku z tym metoda add musi wstawiać elementy w odpowiednim miejscu tablicy co zajmuje czas liniowy względem liczby elementów w tablicy

Dzięki uporządkowaniu elementów metoda find może wykorzystać wyszukiwanie binarne

Wstawienie elementu odbywa się za pomocą wyszukania liniowego i wymaga przekładania elementów O(n)

Wyszukiwanie jest binarne O(log n)

Usunięcie wymaga wyszukania elementu i przesunięcia elementów (przesunięcie powoduje, że pesymistyczna złożoność jest liniowa) O(n)

Zalety:

»Łatwe do zaprogramowania

»Dostęp swobodny (w czasie stałym) do elementów

»Możliwość przeglądania uporządkowanych danych, ale tylko dla tablicy uporządkowanej

»Dosyć szybkie wyszukiwanie danych dla tablic uporządkowanych

Wady:

»Utrudnione usuwanie elementów

»Potrzeba przewidywania wielkości tablicy lub zgoda na czasochłonną relokację

»Nadmiar użytej pamięci (na nieużywany jeszcze fragment wewnętrznej tablicy)

»Utrudnione wstawianie elementów dla tablicy uporządkowanej

»Wolne wyszukiwanie danych dla tablic nieuporządkowanych

19.Listy powiązane

Każda klasa może mieć dodatkowe pole typu tej właśnie klasy

W obiektach klasy takie pole może przechowywać referencję do innego obiektu tej samej klasy

Dzięki takim połączeniom można tworzyć w pamięci komputera listy elementów będących obiektami tej klasy

Dla zapewnienia dostępu do tego typu list, w programie musi być jeszcze jedna zmienna typu tej samej klasy, która przechowuje referencję do pierwszego elementu listy (zmienna first)

»Z tej racji, że ostatni element listy nie wskazuje już na żaden obiekt, wprowadzono specjalną wartość na którą zmienna next w tym obiekcie powinna wskazywać (wartość null)

Tego typu listy nazywamy listami powiązanymi

Wstawienie elementu odbywa się na początku listy O(1)

Wyszukiwanie jest liniowe O(n)

Usunięcie wymaga wyszukania elementu O(n)

20.

Elementy uporządkowanej listy powiązanej zawsze są ułożone względem jakiegoś porządku

W związku z tym metoda insert musi wstawiać elementy w odpowiednim miejscu listy co zajmuje czas liniowy względem liczby elementów na liście

Wstawienie elementu wymaga wyszukania miejsca na ten element O(n)

Wyszukiwanie jest liniowe O(n)

Usunięcie wymaga wyszukania elementu O(n)

21. Na liście powiązanej dwustronnej istnieje dostęp zarówno do pierwszego, jak i do ostatniego elementu listy

Dla zapewnienia takiego dostępu, w programie musi być jeszcze jedna zmienna typu tej samej klasy, która przechowuje referencję do ostatniego elementu listy (zmienna last)

Dzięki dostępowi do ostatniego elementu listy możliwe jest szybkie wstawianie (nie usuwanie!) elementu na końcu listy

22. Na liście powiązanej dwukierunkowej istnieje dostęp zarówno do pierwszego, jak i do ostatniego elementu listy

Ponadto istnieją powiązania elementów w obydwie strony

»Dla zapewnienia takiego dostępu w klasie elementu musi być jeszcze jedna zmienna typu tej samej klasy (zmienna previous)

Dzięki dostępowi do ostatniego elementu listy możliwe jest szybkie wstawianie i usuwanie elementu na końcu listy

Zalety:

»Wykorzystuje pamięć tylko w takim stopniu, jak to jest konieczne (nie ma nadmiaru wykorzystania pamięci jak w przypadku tablic dynamicznych)

»Możliwość przeglądania uporządkowanych danych, ale tylko dla listy uporządkowanej

Wady:

»Trudniejsze programowanie niż dla tablic dynamicznych

»Szybkość wyszukiwania i usuwania jest tylko liniowa

»Dla listy uporządkowanej wzrasta czas wstawiania elementów

23. Drzewo poszukiwań binarnych

Zwane pod nazwą drzewa BST (ang. Binary Search Tree)

»Struktura danych będąca drzewem binarnym, tzn. takim drzewem, że każdy węzeł drzewa ma co najwyższej dwa węzły będące jego dziećmi (synami)

Z każdym węzłem wiąże się wartość klucza, która służy do konstrukcji struktury drzewa, ale także jest daną węzła

»W węźle mogą być także inne dane. np. jakieś teksty lub liczby ułamkowe

Ponadto, w BST lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach nie większych niż klucz tego węzła, a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła.

Węzły, oprócz klucza i ewentualnych danych, przechowują wskaźniki (adresy) na swojego lewego i prawego syna oraz na swojego ojca.

Wyszukiwanie elementu jest po ścieżce

Wstawienie elementu wymaga wyszukania miejsca na ten element

Usunięcie elementu wymaga wyszukania elementu i wykonania algorytmu usunięcia w czasie stałym lub w czasie log n (wyszukanie następnika)

O(log n)

Zalety:

»Szybkie wstawianie, wyszukiwanie i usuwanie elementów (znacznie szybsze niż w przypadku tablic dynamicznych i list powiązanych), szczególnie do danych o charakterze losowym

»Możliwość przeglądania uporządkowanych danych

Wady:

»Drzewo powinno być zrównoważone; jeśli tak nie będzie, to może bardzo wzrosnąć czas wyszukania i usuwania elementów (nawet do złożoności O(n))

24. odpuszczam

25.odpuszczam

26. Stos (ang. stack)LIFO – rodzaj listy w której nowe dane dopisywane są na końcu listy oraz z końca listy dane są pobierane do dalszego przetwarzania

»Koniec listy (tam gdzie wstawiono ostatnio element) jest tutaj nazywany szczytem stosu

»Idę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze.

»Elementy stosu poniżej szczytu można obejrzeć przez ściągniecie elementów nad nimi.

Operacje na stosie:

»IsEmpty(L) – sprawdzenie, czy lista (stos) jest pusta

»AddLast(L,x) – wstawienie elementu x na prawy koniec listy

»Operacja zwyczajowo zwana dla stosu: push (wypchnąć na stos)

»GetLast(L) – pobranie informacji o ostatnim elemencie listy

»Operacja zwyczajowo zwana dla stosu: peek (zerknąć na stos)

»RemoveLast(L,x) – usunięcie elementu na prawym końcu listy

»Operacja zwyczajowo zwana dla stosu: pop

27. Kolejka (ang. queue)FIFO – rodzaj listy, w której nowe dane dopisywane są na końcu listy, a z początku listy pobierane są dane do dalszego przetwarzania.

»Koniec listy (tam gdzie wstawiono ostatnio element, prawy koniec listy) jest tutaj nazywany tyłem kolejki (ang. back)

»Początek listy (tam gdzie pobierane są elementy) jest tutaj nazywany przodem kolejki (ang. front)

»Element kolejki za przodem kolejki obejrzeć przez usunięcie z kolejki elementów przed nim.

Operacje na kolejce:

»IsEmpty(L) – sprawdzenie, czy lista (kolejka) jest pusta

»AddLast(L,x) – wstawienie elementu x do listy na tył kolejki (na prawy koniec listy)

»Operacja zwyczajowo zwana dla kolejki: insert

»GetFirst(L) – pobranie informacji o pierwszym elemencie listy, który jest na początku kolejki

»Operacja zwyczajowo zwana dla kolejki: peek

»RemoveFirst(L,x) – usunięcie pierwszego elementu listy (na początku kolejki)

»Operacja zwyczajowo zwana dla kolejki : remove

28. Kolejka priorytetowa (specyficzny rodzaj kolejki)

Specjalną modyfikacją kolejki jest kolejka priorytetowa

Każdy element ma przypisany priorytet, który modyfikuje kolejność późniejszego pobierania elementów z kolejki

»Przy wstawianiu elementów do kolejki elementu muszą zostać wstawione na miejsce o odpowiednim priorytecie (szybkie pobieranie elementów z kolejki)

»albo

»przy pobieraniu elementów z kolejki wyszukiwany jest element o najwyższym priorytecie (szybkie wstawianie elementów do kolejki)

Przy pobieraniu elementów na wyjściu kolejki niekoniecznie pojawią się te elementy, które w kolejce oczekują najdłużej, lecz te o największym priorytecie.

Operacje na kolejce priorytetowej opartej na idei uporządkowania elementów względem priorytetu :

»IsEmpty(L) – sprawdzenie, czy lista (kolejka) jest pusta

»AddByPriority(L,x) – wstawienie elementu x do listy w odpowiednie miejsce zgodnie z ustalonym priorytetem dla x

–Operacja zwyczajowo zwana dla kolejki: insertByPriority

»GetFirst(L) – pobranie informacji o pierwszym elemencie listy, który jest na początku kolejki

–Operacja zwyczajowo zwana dla kolejki: peek

»RemoveFirst(L,x) – usunięcie pierwszego elementu listy (na początku kolejki)

»Operacja zwyczajowo zwana dla kolejki : remove

Zwykła listę (jednokierunkową lub dwukierunkową) można łatwo zamienić na kolejkę priorytetową

»Warunkiem jest, aby można było przeglądać tę listę

Zmiana polega na tym, że procedury pobrania informacji i usunięcia elementu pierwszego w kolejce muszą przeglądać cała kolejkę celem znalezienia elementu o najwyższym priorytecie

Operacje na kolejce:

»IsEmpty(L) – sprawdzenie, czy lista (kolejka) jest pusta

»AddLast(L,x) – wstawienie elementu x do listy na tył kolejki (na prawy koniec listy)

»Operacja zwyczajowo zwana dla kolejki: insert

»GetFirstByPriority(L) – pobranie informacji o elemencie listy, który ma najwyższy priorytet

»Operacja zwana dla kolejki priorytetowej: peekByPriority

»RemoveFirstByPriority(L,x) – usunięcie elementu listy , który ma najwyższy priorytet

»Operacja zwana dla kolejki priorytetowej: removeByPriority

29. Problem obliczeniowy to zadanie, które może być rozwiązane za pomocą komputera lub innej maszyny liczącej.

»Istnieją dwa rodzaje problemów obliczeniowych: problemy decyzyjne i problemy optymalizacyjne.

Problem decyzyjny to pewien zbiór parametrów oraz pytanie, na które odpowiedź brzmi „tak” lub „nie”

»Ustalając wartości tych parametrów otrzymujemy instancję, czyli konkretny przypadek problemu.

Problem optymalizacyjny, to taki problem, w którym należy ekstremalizować (maksymalizować lub minimalizować) pewną funkcję celu

»Rozwiązaniem jest konkretna instancja, dla której zostało osiągnięte ekstremum

Wiele problemów może być formułowane zarówno w wersji decyzyjnej, jak i w wersji optymalizacyjnej

Przykład sformułowania problemu jako problem decyzyjny i optymalizacyjny dla problemu plecakowego

Dany jest skończony zbiór elementów A={a1,...,an}, ciąg rozmiarów tych elementów s(a1),...,s(an), ich wartości w(a1),...,w(an) oraz stałe b i t.

Wersja decyzyjna: Czy istnieje podzbiór BA taki, że

»Innymi słowy: Czy istnieje taki podzbiór zbioru elementów A, że elementy z tego podzbioru mieszczą się do plecaka o objętości b, a ich wartość jest nie mniejsza niż t ?

Wersja optymalizacyjna: Znaleźć podzbiór zbioru BA taki, że

osiąga wartość maksymalną.

»Innymi słowy: Znajdź taki podzbiór zbioru A, że elementy z tego podzbioru mieszczą się do plecaka o objętości b, a ich wartość jest możliwie największa.

Problemy decyzyjne a optymalizacyjne

Z danym problemem optymalizacyjnym można związać odpowiadający mu problem decyzyjny i taki problem decyzyjny jest obliczeniowo nie trudniejszy, niż odpowiadający mu pierwotny problem optymalizacyjny (uproszczenie).

Jeśli problem decyzyjny jest obliczeniowo „trudny”, to „trudny” jest również odpowiadający mu problem optymalizacyjny (utrudnienie).

Obserwacja 1: Jeśli da się w "prosty" sposób rozwiązać problem optymalizacyjny, to można również "prosto" rozwiązać związany z nim problem decyzyjny.

Np. jeśli potrafimy rozwiązać problem optymalizacyjny plecakowy, to potrafimy rozwiązać odpowiadający mu problem decyzyjny

Obserwacja 2: Jeśli problem decyzyjny jest „trudny”, to odpowiadający mu problem optymalizacyjny również jest „trudny” (pytamy o coś więcej).

Np. jeśli problem plecakowy w wersji decyzyjnej jest trudny, to na pewno problem plecakowy w wersji optymalizacyjnej także jest trudny

Wniosek1: W celu wykazania "łatwości" problemu decyzyjnego wystarczy wykazać łatwość problemu optymalizacyjnego (np. zaproponować szybki algorytm).

Wniosek 2: Dla wykazania "trudności" problemu optymalizacyjnego wystarczy wykazać "trudność" związanego z nim problemu decyzyjnego.

30. Transformacja wielomianowa problemów

Załóżmy, że są dane dwa problemy decyzyjne P1 i P2, które posiadają dwa zbiory instancji odpowiednio D1 i D2

Transformacja wielomianowa problemu P2 do problemu P1 to taka funkcja f: D2 -> D1, która spełnia dwa następujące warunki:

1.dla każdej instancji I2 należącej do D2 odpowiedź brzmi "tak" wtedy i tylko wtedy, gdy dla instancji f(I2) odpowiedź brzmi również "tak"

2.czas deterministycznego obliczania wartości funkcji f dla każdej instancji I2 należącej do D2 jest ograniczony od góry przez wielomian zależny od rozmiaru instancji I2, czyli od N(I2)

Jeśli istnieje transformacja wielomianowa problemu P2 do problemu P1 to mówimy, że problem P2 jest redukowalny do problemu P1

»Oznacza to, że jeśli potrafimy rozwiązać wielomianowo problem P2, to również wielomianowo potrafimy rozwiązać problem P1

31. Klasa NP problemów

Problemami klasy NP nazywamy problemy decyzyjne w których sprawdzenie poprawności określonego rozwiązania wymaga złożoności obliczeniowej wielomianowej.

Z powyższego stwierdzenia wynika więc, że znalezienie rozwiązania dla problemów NP wymaga złożoności co najmniej wielomianowej

Klasa problemów P

Problemami klasy P nazywamy problemy decyzyjne w których znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej.

Problemy P należą do zbioru problemów NP, czyli sprawdzenie poprawności rozwiązania danego problemu jest możliwe w czasie wielomianowym;

Jednak znalezienie rozwiązania problemu z klasy P jest możliwe również w czasie wielomianowym.

Różnica pomiędzy problemami P i NP polega więc na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma właśnie złożoność wielomianową.

Pytanie: P=NP ?

Każdy problem P jest NP, jednak nie wiadomo, czy każdy problem NP jest P.

Jest to jedno z wielkich nierozwiązanych dotychczas zagadnień informatyki.

»Najważniejsze pytanie teoretycznej informatyki i jest jednym z problemów milenijnych.

32. Klasa problemów NP-zupełnych

Do klasy problemów NP-zupełnych należy każdy problem decyzyjny spełniający trzy poniższe

warunki:

»nie jest znany algorytm rozwiązujący ten problem w czasie wielomianowym,

»należy do klasy NP (rozwiązania problemu dla konkretnych danych dają się weryfikować w czasie wielomianowym),

»dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym.

Pierwszym problemem, którego NP-zupełność wykazano, był problem SAT, czyli problem spełnialności formuł zdaniowych (Stephen Cook, 1971).

»SAT to pytanie rachunku zdań - czy dla danej formuły logicznej istnieje takie podstawienie (wartościowanie) zmiennych zdaniowych, żeby formuła była prawdziwa.

»Cook podał dowód, ze problem SAT należy do NP oraz każdy problem z klasy NP jest redukowalny do tego problemu

Dowodzenie NP-zupełności problemów

Dla wykazania NP-zupełności badanego problemu P1 decyzyjnego wystarczy udowodnić, że ten problem należy do klasy NP oraz przetransformować do niego wielomianowo dowolny znany problem NP-zupełny.

Uzasadnienie: Jeśli problem P1 jest z klasy NP i istnieje problem P2 redukowalny do P1, to wszystkie problemy z klasy NP są redukowalne do P1. Wynika to z faktu, że wszystkie problemy były redukowalne do problemu SAT, a zatem pośrednio są one redukowalne do P2, a więc i do P1 (poprzez złożenie transformacji wielomianowych, które także jest transformacją wielomianową)

33. Klasa problemów NP-trudnych

Do klasy problemów NP-trudnych należą problemy spełniające dwa poniższe warunki:

»nie jest znany algorytm rozwiązujący ten problem w czasie wielomianowym (mogą być znane rozwiązania wykładnicze),

»dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym.

Każdy problem NP-zupełny jest problemem NP-trudnym

Istnieją problemy NP-zupełne, które nie są NP-trudne (w definicji NP-trudności nie wymaga się należenia do klasy NP, a jedynie redukowalności wszystkich problemów z klasy NP do danego problemu)

Ponieważ dla problemu NP-trudnego, każdy problem z klasy problemów NP-zupełnych może być zredukowany (sprowadzony) do tego problemu, zatem problem NP-trudny to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.

Zasady dowodzenie NP-trudności problemów

Każdy problem optymalizacyjny, którego wersja decyzyjna jest NP-zupełna jest problemem NP-trudnym

Dla wykazania trudności rozważanego problemu optymalizacyjnego wystarcza wykazanie NP-zupełności odpowiadającego mu problemu decyzyjnego.

»Mówimy wtedy, że dany problem optymalizacyjny jest NP-trudny.

–Np: problem decyzyjny plecakowy jest NP-zupełny i dlatego problem optymalizacyjny plecakowy jest NP-trudny

34. Hierarchia(kółeczke):

NP:

P zawiera się w NP, NP-zupełne zawiera się w NP i ma część wspólną z NP-trudne, a NP-trudne ma część wspólną właśnie z NP-zupełne czyli też z NP

Znaczenie klasyfikacji problemów jako uzasadnienie naszej niemocy

Jeśli udowodnimy NP-zupełność swojego problemu to znaczy, że jesteśmy w takiej sytuacji jak wiele innych osób

Jeśli udowodnimy NP-trudność, to sytuacja jest jeszcze gorsza, gdyż być może wychodzimy poza klasę NP