Twoim problemem jest to, że powszechną NICOŚĆ mylisz z osobistą PUSTKĄ
POJĘCIE ALGORYTMU
Algorytm – ściśle określony sposób postępowania, który w skończonej liczbie kroków
daje oczekiwany wynik; przepis wykonania czynności.
Cechy algorytmu:
• jeśli posiada dane wejściowe, to pochodzą one z dobrze zdefiniowanego zbioru;
• daje pewien wynik;
• ciąg reguł jest skończony;
• jest precyzyjnie zdefiniowany.
PROJEKTOWANIE ZSTĘPUJĄCE I WSTĘPUJĄCE
Projektowanie zstępujące (top-down design) – zdefiniowany problem dzielony jest na mniejsze kroki, aż do uzyskania podproblemów łatwych do rozwiązania. Proces podziału
problemu nosi nazwę stopniowego uszczegółowiania. Należy tak dzielić problemy, aby końcowe podproblemy mogły być ozwiązywane niezależnie od siebie, a ich wyniki następnie łączone w celu otrzymania rozwiązania całego problemu.
Zalety:
– otrzymane rozwiązanie jest modularne,
– rozwiązanie jest łatwiejsze do zrozumienia i analizy,
– rozwiązania poszczególnych kroków mogą być wykorzystane wielokrotnie.
Projektowanie wstępujące (bottom-up design) – opierając się na istniejących (dostępnych) funkcjach języka należy wzbogacać język swoimi operacjami tak długo, dopóki nie będzie można rozwiązać problemu w rozszerzonym języku.
Przykład:
Obliczyć wyrażenie: ((A+l1)+(A*l2))*(B-l1)+(A+B), gdzie A i B są macierzami a l1 i l2 liczbami.
Projektowanie zstępujące – podział na podproblemy:
1)wprowadź dane
2)wykonaj operacje
3)wyświetl wynik – operacja elementarna
dalszy podział 1:
1.1) wprowadź macierze
1.2) wprowadź liczby
dalej:
1.1.1)wprowadź macierz A
1.1.2)wprowadź macierz B
- jest to ten sam problem, więc wystarczy jedna funkcja lub rocedura sparametryzowana
1.2.1)wprowadź liczbę l1
1.2.2)wprowadź liczbę l2
- analogicznie jak z macierzami
dalszy podział 2 – podział na poszczególne operacje:
2.1) macierz + liczba
2.2) macierz * liczba
2.3) macierz + macierz
2.4) macierz * macierz
2.5) macierz – liczba – można potraktować jako macierz + (– liczba)
Poszczególne problemy należy rozwiązać, a następnie złożyć w celu otrzymania wyniku problemu pierwotnego.
KLASY ALGORYTMÓW
Algorytm siłowy (brute-force) – rozwiązanie szukane jest najprostszymi środkami, np. przez rozpatrzenie wszystkich możliwych przypadków po kolei.
Przykład:
problem plecakowy:
dyskretny – w sklepie znajdują się przedmioty o podanej cenie i wadze; zapakować do plecaka o danej pojemności przedmioty tak, aby w sumie ich cena była maksymalna (przedmiotów nie
można dzielić):
ogólny – przedmioty są dostępne w nieograniczonej ilości
decyzyjny – dostępne jest po jednej sztuce danego przedmiotu
ciągły – jak wyżej, ale przedmioty (substancje) można dzielić
łamanie haseł;
poszukiwanie wzorca w tekście;
Zaleta: prosty, na pewno zawsze zadziała.
Wada: powolny, może zajmować dużo pamięci.
Algorytm zachłanny (żarłoczny, greedy algorithm) – wykonywane jest działanie najlepsze w danej chwili, bez analizowania jego skutków i przyszłości, wybór następnego kroku obywa się metodą decyzji lokalnie optymalnej.
Ogólny schemat:
zachłanny(W) {W – zbiór danych wejściowych}
begin
rozwiązanie=zbiór pusty;
while (nie znaleziono pełnego rozwiązania) i (W nie jest zbiorem pustym) do
begin
X=wybor(W); {gdzie wybor – funkcja wybierająca lokalnie
optymalny element ze zbioru W i usuwająca go z W}
if pasuje(X) then
rozwiązanie=rozwiązanie + X;
end;
end;
Przykłady:
problem kasjera – wydać resztę używając do tego minimalnej ilości monet;
problem wyboru zajęć – dany jest zbiór zajęć, z których każde ma określony czas rozpoczęcia
i zakończenia, znaleźć największy podzbiór niekolidujących zajęć;
problem komiwojażera – znaleźć najkrótszą drogę w grafie z wagami, przechodząc dokładnie raz przez wszystkie wierzchołki;
problem plecakowy;
Zalety: nie traci czasu na rozważanie następstw, w wielu wypadkach daje optymalne
rozwiązanie.
Wady: nie zawsze rozwiązanie zbudowane z rozwiązań lokalnie optymalnych jest globalnie optymalne.
Algorytm „dziel i zwyciężaj” („dziel i rządź”, divide and conquer) – problem jest dzielony na mniejsze części o tym samym charakterze, co problem pierwotny, aż do momentu, gdy otrzymane problemy są proste do rozwiązania (rozwiązanie jest oczywiste lub takie, do którego można zastosować którąś z istniejących metod); następnie rozwiązania podproblemów są łączone w celu uzyskania rozwiązania całego problemu. Zwykle implementowane za pomocą rekurencji.
Ogólny schemat: {N – rozmiar danych wejściowych}
dziel_i_zwyciezaj(N)
begin
if (N wystarczająco mały) then
zwróć przypadek elementarny(N)
else
begin
podziel problem (N) na k podproblemów
for i:=1 to k do
dziel_i_zwyciezaj(Ni)
zwróć wynik na podstawie wyników cząstkowych
end;
end;
Przykład:
szukanie maksimum/minimum ciągu;
sortowanie quicksort (szybkie), mergesort (przez scalanie) .
Zalety: po podziałach problem staje się trywialny, dzięki podziałowi na podproblemy o tym samym charakterze, wszystkie problemy mogą być rozwiązywane z użyciem tej samej procedury.
Wady: problemy związane z użyciem rekurencji (np. szybkie przepełnienie stosu), konieczność powtarzania pewnych obliczeń.
Algorytm oparty na programowaniu dynamicznym (dynamic programming) – ulepszenie metody „dziel i zwyciężaj”, rozwiązania kolejnych podproblemów są zapisywane w tablicy (jedno- lub wielowymiarowej), której już wyznaczone elementy służą do wyznaczania kolejnych.
Ogólny schemat:
tab:array [1..N] of rozwiązanie podproblemu
begin
for i:=1 to ilość przypadków elementarnych do
wypełnij tab[i]
for i:=(ilość przypadków elementarnych + 1) to N do
wyznacz tab[i] na podstawie elementów od tab[1] do tab[i-1]
end;
Przykłady:
obliczanie elementów ciągu Fibonacciego;
obliczanie symbolu Newtona;
obliczanie wierszy trójkąta Pascala;
problem plecakowy.
Zalety: oszczędność czasu, nie jest konieczna rekurencja.
Wady: większa zajętość pamięci koniecznej do kodowania ozwiązań cząstkowych.
Algorytmy z powrotami (backtracking) – stosowane do oblemów, w których rozwiązanie może być znalezione jedynie metodą „prób i błędów” - szukając rozwiązania wykonywane są kolejne kroki; jeżeli dany zestaw kroków doprowadził do poprawnego wyniku oznacza, że jest on rozwiązaniem, jeśli jednak któryś krok doprowadził do miejsca, z którego nie ma możliwości wykonania kolejnego kroku, należy cofnąć się do miejsca, z którego możliwe było wykonanie innego kroku.
Ogólny schemat:
próbuj następny krok
begin
repeat:
wybierz następnego kandydata
if (kandydat poprawny) then
begin
zapisz go
if (rozwiązanie niepełne) then
begin
próbuj następny krok
if (próba nieudana) then usuń zapis
end
end
until próba udana lub brak kandydata
Zwykle implementowane z pomocą rekurencji.
Przykłady:
problem skoczka szachowego;
problem 8-miu hetmanów;
szukanie drogi w labiryncie.
RODZINY ALGORYTMÓW
Oprócz podziału w oparciu o filozofię działania, można klasyfikować algorytmy ze względu na ich przeznaczenie, np.:
• sortowanie danych,
• wyszukiwanie danych, poszukiwanie wzorca,
• algorytmy numeryczne – do rozwiązywania problemów matematycznych (aproksymacja, interpolacja, całkowanie, różniczkowanie, rozwiązywanie równań),
• kodowanie, • kompresja.
POPRAWNOŚĆ ALGORYTMU
Sposoby sprawdzania poprawności:
• analiza kodu,
• sprawdzenie struktury programu,
• przeprowadzenie testów funkcjonalnych,
• przeprowadzenie weryfikacji programu, czyli logicznego dowodu poprawności kodu we wszystkich przypadkach.
Weryfikacja opiera się na specyfikacji. Specyfikacja jest niezależna od kodu. Określa, co program powinien robić oraz jakie są związki pomiędzy danymi wejściowymi i wyjściowymi. Weryfikacja powinna stwierdzić, że kod programu jest zgodny z jego pecyfikacją, czyli że program posiada własność częściowej poprawności. Poza tym trzeba mieć pewność, że program zakończy swoje działanie, czyli że posiada własność stopu.
W specyfikacji określone są dwa warunki:
warunek wstępny (precondition, asercja początkowa) – warunek określający dane wejściowe, który musi być spełniony na początku programu
warunek końcowy (postcondition, asercja końcowa) – dotyczy wyjścia programu, opisuje wartości, które program oblicza.
W niezmienniku pętli opisywane są zmienne pętli, jej wejście i wyjście, czyli warunki, które są spełnione przez zmienne pętli, przez wartości wczytywane lub wyświetlane (jeśli w pętli zachodzi zapis lub odczyt), przy czym warunki te muszą być prawdziwe przed pierwszym wykonaniem pętli oraz po każdym jej pełnym obrocie (nie koniecznie wewnątrz pętli).
Istnieją pewne typowe pętle, dla których określone są niezmienniki:
• pętle z wartownikiem,
• pętle z licznikiem.
Pozostałe pętle to tak zwane pętle ogólne, bez zdefiniowanego niezmiennika.
Pętla z wartownikiem wykonuje się do napotkania określonego, niedozwolonego elementu (wartownika). Wartownik nie jest przetwarzany. Pętla może wykonać się dowolną ilość razy lub nie wykonać wcale.
Niezmiennik pętli z wartownikiem:
Wszystkie wartości wejściowe, oprócz ostatniej, zostały przetworzone. Żadna z wartości wejściowych, oprócz być może ostatniej, nie jest wartownikiem.
Pętla z licznikiem wykonuje się z góry określoną ilość razy. Licznik służy do kontroli liczby przebiegów.
Niezmiennik pętli z licznikiem:
Elementy od a do i - 1 zostały przetworzone. a <= i. Jeżeli a <= b to i <= b + 1,
w przeciwnym wypadku i = a.
Aby udowodnić własność stopu dla pętli z wartownikiem w warunku wstępnym należy zapewnić, że dane wejściowe zawierają wartownika. Dla pozostałych pętli należy znaleźć wielkość całkowitoliczbową, ograniczoną z dołu, która w każdym przebiegu pętli będzie się zmniejszać (lub będzie ograniczona z góry i będzie się zwiększać).
ZŁOŻONOŚĆ OBLICZENIOWA
Złożoność obliczeniowa – miara służąca do porównywania efektywności algorytmów. Określa, ilu zasobów wymaga użycie danego algorytmu lub jak jest ono kosztowne. Koszt można mierzyć na wiele sposobów, zwykle bierze się pod uwagę dwa kryteria efektywności: czas i pamięć. Czasu nie powinno mierzyć się w konkretnych jednostkach czasu, ale powinno się znajdować zależności między ilością danych n a ilością czasu t potrzebnego do ich przetworzenia. Złożoność czasowa jest zwykle mierzona liczbą przypisań i porównań realizowanych podczas wykonywania programu.
Złożoność asymptotyczna – uproszczenie złożoności obliczeniowej, podaje przybliżoną miarę efektywności algorytmu. Przy jej bliczaniu pomija się te składniki, które nie zmieniają zasadniczo wielkości funkcji.
Złożoność przestrzenna – niezbędna ilość pamięci potrzebna do przechowywania danych i ewentualnych pośrednich wyników obliczeń.
TYPY DANYCH
OGÓLNE POJĘCIA
Typ charakteryzuje zakres wartości do którego należy stała, jakie może przyjmować zmienna lub wyrażenie, jakie mogą być enerowane przez funkcję. Określenie w programie typu jest niezbędne dla właściwego przydziału pamięci pod zmienną danego typu. Im większy zakres wartości, tym więcej pamięci potrzebne do przechowania zmiennej. Ilość pamięci potrzebnej do rzechowywania zmiennej danego typu określana jest na podstawie mocy typu.
Moc typu – ilość wszystkich różnych wartości należących do danego typu, liczebność. Na x bitach możemy zapisać 2x różnych wartości. W przypadku liczb ze znakiem pierwszy bit interpretowany jest jako znak, dopiero z pozostałych tworzona liczba.
Typ uporządkowany (skalarny) – typ, którego wartości są uporządkowane ((ci < cj) <=> (i<j)). W Pascalu i C wszystkie typy proste są uporządkowanymi. W przypadku jawnego wyliczenia wartości przyjmuje się, że wartości są uporządkowane zgodnie z kolejnością ich wyliczenia.
PLIK SEKWENCYJNY:
• jest zmienną strukturalną, przed wykonaniem programu nie ma ustalonej ilości elementów (w przeciwieństwie do poprzednich)
• dostęp sekwencyjny – w danej chwili bezpośrednio dostępny jest jedynie jeden, konkretny element; element ten jest określany przez bieżącą (aktualną) pozycję wskaźnika, każda operacja odczytu i zapisu przesuwa wskaźnik
• ze względu na fakt, że procesy konstruowania i przeglądania pliku mają odmienne mechanizmy, plik znajduje się w jednym z dwóch stanów: w stanie konstruowania (pisania) bądź przeglądania (czytania)
REKURENCJA:
Obiekt rekurencyjny – obiekt, który częściowo składa się z siebie samego lub jego definicja odwołuje się do jego samego. Rekurencja umożliwia definiowanie nieskończonego zbioru obiektów za pomocą skończonego wyrażenia.
Realizacja:
w momencie wywołania funkcji na stos odkładane są:
• adres powrotu (dynamiczne dowiązanie)
• wartość zmiennych lokalnych (jest to szczególnie ważne, jeśli nazwy zmiennych pokrywają się)
• wartości parametrów
• wartość zwracana (w przypadku funkcji).
Wartości te są zdejmowane ze stosu po zakończeniu funkcji.
Cechy algorytmów rekurencyjnych:
• zakończenie algorytmu jest jasno określone (wywołania rekurencyjne odbywają się pod warunkiem)
• problem został rozłożony na problem elementarny, którego rozwiązanie jest znane.
Nie należy stosować rekurencji:
• gdy ważna jest szybkość działania algorytmu – rozwiązanie iteracyjne jest zwykle dużo szybsze
• gdy można spodziewać się dużej ilości wywołań rekurencyjnych, ze względu na możliwość przepełnienia stosu
• pewne obliczenia będą musiały być powtórzone wielokrotnie
Dodatkowe pojęcia:
Rekurencja bezpośrednia: procedura (lub funkcja) P jest bezpośrednio rekurencyjna, jeśli zawiera odwołanie do samej siebie (w swoim kodzie wywołuje P).
Rekurencja pośrednia: procedura (lub funkcja) P jest pośrednio rekurencyjna, jeśli zawiera odwołanie do procedury (lub funkcji) Q, natomiast Q zawiera odwołanie do P (bezpośrednie lub pośrednie).
Rekurencja końcowa: w procedurze (lub funkcji) rekurencyjnej występuje tylko jedno wywołanie rekurencyjne i jest ono ostatnią instrukcją (znajduje się ono na samym końcu procedury). W przeciwnym wypadku mamy do czynienia z rekurencją niekońcową.
ZASTOSOWANIE REKURENCJI W ALGORYTMACH Z POWROTAMI:
Algorytmy z powrotami zwykle są implementowane z użyciem rekurencji, co stwarza niebezpieczeństwo przepełnienia stosu. Należy więc zminimalizować liczbę wywołań rekurencyjnych. Wpływ na ilość wywołań może mieć dokładność określenia warunku
poprawności kandydata oraz wstępne ustawienie kandydatów.
Odmianą algorytmów z powrotami jest algorytm podziału i ograniczeń (branch and bound algorithm). W algorytmie tym istnieje dodatkowy czynnik ograniczający – należy znaleźć rozwiązanie optymalne, spełniające dodatkowe założenia. Dla każdego elementu zbioru danych wejściowych rozpatrywane są dwie sytuacje: włączenie danego elementu do zbioru wynikowego lub wykluczenie go ze zbioru wynikowego.
WSKAŹNIKI (odniesienia – ang. pointer) – zmienne, które przechowują nie samą wartość, a jej adres w pamięci. Dzięki wskaźnikom możliwe jest tworzenie tak zwanych zmiennych dynamicznych. Zmienne dynamiczne – zmienne, pod które pamięć przydzielana jest dynamicznie – pamięć jest przydzielana w chwili ich tworzenia podczas wykonywania programu, a nie na początku programu, jak w przypadku zmiennych statycznych. Zalety:
oszczędność pamięci (przez eliminację redundancji – wystarczy odpowiednio przypisać wskaźniki, a nie trzeba powielać tych samych danych), skalowalność.
DYNAMICZNE STRUKTURY DANYCH – struktury implementowane za pomocą wskaźników, dzięki czemu pamięć pod nie przydzielana jest dynamicznie. Zalety: dzięki dynamicznemu przydziałowi pamięci, struktury te są skalowalne – mogą się rozrastać wraz z przybywaniem nowych danych, lub kurczyć po kasowaniu danych, lepiej wykorzys...