Zestaw 4.

1. Złożoność czasowa i pesymistyczna,

2. Sortowanie bąbelkowe,

3. Derekursywacja

4. Lista jednokierunkowa (właściwości)

5. Dwukopiec,

6. Graf,

7. Cykl Eulera,

8. Jaka złożoność czasową ma Hornet, omówić ją

9. Wymienić wszystkie  sortowania

10. Scalanie (na czym polega + rysunek)

1. Złożoność czasowa-czas działania algorytmu, wyrażony liczbą jego operacji
   Złożoność czasowa pesymistyczna- ilość wykonywanych operacji elementarnych dla danych „najgorszego” przypadku.
   Pesymistyczna złożoność czasowa algorytmu to funkcja(max-to kres górny zbioru)

2. Bębelkowe - polega na porządkowaniu ciągów, kóra polega na przestawianiu sąsiednich par elementów znajdujących się w nieodpowiedniej kolejności, przy czym ciąg jest tak długo przeglądany w tym samym kierunku tak długo, jak może w nim wystąpić jeszcze para elementów o niewłaściwym porządku. Dane: liczba naturalna n i ciąg n liczb x1,x2.. Wynik: Uporządkowanie tego ciągu liczb od najmniejszej do największej. Krok1: Kres:=n {kres określa miejsce w ciągu stanowiące granicę poszukiwania pary elementów do przestawienia} Krok2: Przyjmij i:=1 oraz k:=0 {k jest wskaźnikiem przestawnej pary} Krok3: Dopóki i<Kres, wykonaj: jeśli xi>xi+1, to przestaw te elementy przyjmij k:=i , zwiększ i:=i+1. Krok4: Jeśli k>1, to przyjmij kres:=k i wróć do kroku 2, w przeciwnym razie zakończ algorytm.

3. DEREKURSYWACJAWadą większości funkcji rekurencyjnych jest intensywne wykorzystanie stosu ,który służy do przechowywania rekurencyjnych odwołań tej samej funkcji. Oprogramowanie tworzone jest w oparciu o eleganckie algorytmy rekurencyjne .Wersja końcowa (użyta w praktycznym zastosowaniu) powstaje wyniku transformacji algorytmu rekurencyjnego na iteracyjny. Zaletą transformacji jest jej pełna równoważność funkcyjna tzn.prawidłowo działający algorytm rekurencyjny po przetransportowaniu na algorytm iteracyjny dalej działa prawidłowo. Procedura iteracyjna jest równoważna procedurze rekurencyjnej P, jeśli wykonuje dokładnie to samo zadanie co P ,dając identyczne rezultaty.Wywoływanie rekurencyjne procedury P jest zwane terminalnym ,jeśli nie następuje po nim już żadna instrukcja tej proceduryProcedury P1 i P2 są wzajemnie równoważne pod warunkiem że P1 zawiera tylko jedno rekurencyjne wywołanie terminalne.

4. Lista jednokierunkowa jest oszczedna pamieciowa struktura danych pozwalajaca grupowac dodolna - ograniczona iloscia dostepnej pamieci. Do budowy list jednokierunkowej uzywane sa dwa typy komorek Pamieci. Pierwszy jest zwyklym rekordem natury informacyjnej, drugi jest rekordem lecz ma on charakter roboczy.
   Wlasnosci listy jednokierunkowej: Jeżeli list jest pusta to strukt. Informacyjna zawiera dwa wskazniki null.

5. Dwukopiec- swoja budowa przypomina kopiec, posiada dwoch potomkow i dwoch przodkow, na pierwszym miejscu jestt korzen, interpretacja- tablica, kopiec est dzrewem binarnym

6. GRAFY
   Stopien wierzcholka - l. krawędzi do niego przyległych
   Graf regularny - w którym każdy wierzcholek ma taki sam stopien
   Graf pla**ny - w którym można przedstawic na płaszczyźnie tak, by żadne dwie krawędzie się nie przecinaly
   f - graf - z ograniczonym stopniem wierzcholka tzn jego stopien nie może być wiekszy niż f.
   Graf prosty - bez petli wlasnych i krawędzi równoległych.
   Niezmiennik grafu - to liczba lub ciag liczb który zalezy tylko od struktury grafu a nie od sposobu jego poetykietowania (np. l. wierzchokliw, l. krawędzi)
   L. chromatyczn grafu - to najmniejszya liczba kolorow potrzebnych do pokolorowania wierzchołków grafu tak, by żadne dwa przylegle wierzcholki nie były tego samego koloru.

7. CYKL EULERA w grafie.
   Cykl l- droga która zaczyna się i konczy w tym samym wierzchołku l, który zawiera kazda krawędź dokladnie raz.
   Łańcuchem Eulera w grafie nazywamy droge który zawiera kazda krawędź dokladnie raz
   Warunki istnienia C.EULERA:
   - graf musi być spojny (musi istniec droga laczaca kazda pare wierzchołków) i skierowany (wektory)
   - jeżeli graf jest spojny i niekierowany, to liczba wychodzących krawędzi z każdego wierzcholka musi być parzysta.

9. bąbelkowe, przez wstawianie przez wstawianie bnarne, przez wybor, przez scalanie, przez scalanie rozszerzone, szybkie, stogowe stogowe rozszerzone

10. Porządkowany ciąg liczb jest dzielony w każdym kroku na dwa, niemal równej długości podciągi, które rekurencyjnie są porządkowane tą samą metodą.
    Warunkiem zakończenia rekurencji w tym algorytmie jest moment, gdy ciąg ma jeden element, nie można go wtedy podzielić na podciągi - jest to ciąg uporządkowany. Powrót z wywołań rekurencyjnych rozpoczyna się z ciągami złożonymi z pojedynczych elementów, które są scalane w ciągi o długości dwa, następnie w ciągi o długości trzy lub cztery elementy.

---