Rekurencja, algorytmy, sortowanie

Programowanie Teoria dodano: 30.05.2019
EDYCJA 30.05.2019

Sortowanie bąbelkowe, Quick sort, struktury danych: drzewo binarne, kolejka, lista, graf, kopiec.
Algorytmy (złożoność czasowa (s) i pamięciowa (ram) + struktury danych = programy
  • Rekurencja
    w programowaniu sytuacja w której funkcja wywołuje samą siebie w celu zwrócenia wyniku. Dokładniej: tworzy swoje własne kopie, aż do napotkania przypadku podstawowego, dla którego f. może wyznaczyć wynik.
  • Algorytm
    skończony ciąg operacji koniecznych do rozwiązania zadania / problemu. A. rekurencyjne okazują się szybsze niż te zrobione na pętlach iteracyjne. Program rekurencyjny zabiera dużo RAM. Rozwiązanie: iteracje dla małych danych, rekurencyjne dla dużych ?
  • Sortowanie bąbelkowe
    proces uporządkowania zbioru danych wg. jakiś cech charakterystycznych tego zbioru.
    - porównanie 2 wartości obok siebie i zamiana ich miejscami
    - rosnąco lub malejąco
    -mnóstwo iteracji - tyle ile jest elementów
    - wielokrotne stosowanie tej samej procedury
    Np. wyznacz największą liczbę w zbiorze.
  • Quick sort
    Wybiera się oś i pozycjonuje wg niej. Szybkie, rekurencyjne, dużo RAM.
  • Stos
    struktura liniowo uporządkowanych danych z których tylko ostatni element - wierzchołek - jest dostępny(dołącznie nowych elementów lub usuwanie). Bardzo szybki, brak dostępu. Tablice - dostęp do wszystkich elementów.
    Architektura LIFO Last Is First Out, ostatni który wpadł jest pierwszy do wyjazdu.
    ZMIENNA LOKALNA to STOS.
    push(), pop() usuwa, size() zwraca liczbę elementów empty() zwraca true / false gdy stos pusty / nie pusty
  • Kolejka
    przeciwieństwo stosu, liniowa str. danych. FIFO First In First Out element pierwszy, który został wstawiony pierwszy jest z niej pobierany.
    Zapytania do bazy danych.
  • Lista
    dynamicznie zaalokowana przez wskaźnik. Poszczególne komórki są połącznoe przez wskaźniki. Tyle komórek ile potrzeba, tego samego typu.
    L. jednokierunkowa / dwukierunkowa / cykliczna
  • Drzewo binarne
    hierarchiczna, dwójkowa str. danych, elementy to węzły. Każdy NODE posiada dwa potomki (CHILD NODE) i staje się PARENT. NODE to różne komórki w RAM połączone wskaźnikami. Skomplikowana, ale lepsza lista.
  • Kopiec
  • Progr obiektowe
    OBIEKTY - elementy łączce stan, czyli DANE, zwane POLAMI i zachowania czyli PROCEDURY i METODY. Obiekt to dający się wyodrębnić fragmęt rzeczywistości. Abstrakcja: zbiór obiektów komunikujący się ze sobą w celu wykonania zadań. Obiekty tworzy się wg przepisu zawartego w klasie.
    KLASA = zestaw atrybutów. Obiekt - reprezentant klasy wg przepisu zawartego w klasie.
  • operator zasięgu ::
    Mówi, do której klasy należy ta funkcja, dana metoda jest częścią składową tej klasy.
    Klasa : : metoda();
    Zob. metody statyczne.


Losowe zdjęcia


O sobie


gawronski
A.D. 2016

Lubię jazdę na rowerze, wspinaczkę, czytać książki i biegać. Studiowałem mechanikę i budowę maszyn oraz psychologię. Nie zostałem inżynierem ani psychologiem.