Wykład pierwszy Flashcards
Teoria obliczeniowa?
jest nauką o procesach algorytmicznych, czyli analizy, projektowanie, efektywność,
implementacja,zastosowanie
Algorytm?
opisuje procedure złożoną ze skończonej liczby kroków, jakie należy wykonać dla uzyskania wynikow bedacych celem tego algorytmu
Czy problem Collatza zakończy się dla dowolnego x?
Nie
Inserion sort co to?
jest to algorytm wydajny dla zbiorów o niewielkiej liczebności. Jest to jeden z najprostrzych algorytmów sortowania. Działa on bardzo prosto, albowiem potrzebujemy nowej tablicy do której przeniesiemy dowolny element z tablicy nie posortowanej. Następnie bierzemy dowolny element ze zbioru nieposortowanego i porównujemy go z elementem w tablicy posortowanej, dopóki ten element nie napotka elementu, który jest większy, będzie porównywany do samego końca. I tak robimy dopóki nie weźmiemy każdego elementu z tablicy nieposortowanej. Jest to algorytm stabilny.
Pseudokod:
Co jest podstawowym model obliczeń?
jednoprocesowa maszyna z dostępem do Random Access Machine
Selection sort co to?
kolejny juz jeden z prostszych algorytmow sortowania. Polega on na wyszukaniu elementu znalezc się na ządanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Jest to algorytm niestabilny.
Bubble sort co to?
bruh algorytm, który polega na porównaniu dwóch kolejnych elementów i zamianie ich kolejności, jezeli zaburza ona porzadek, w jakim sie sortuje tablice. Sortowanie konczy sie, gdy podcxas kolejnego przejscia nie dokonano zadnej zmiany.
Czym jest algorytm stabilny?
zawsze zachowuje wejsciowy porzadek elementow o tej samej wartosci.
Czym jest algorytm niestabilny?
nie gwarantuje, ze elementy o tej samej wartosci beda wzgledem siebie uporzadkowane
na wyjsciu tak samo jak w ciagu wejsciowym.
Shell sort co to?
Jest to uogolnienie sortowania
przez wstawianie lub sortowania babelkowego, dopuszczajace porownania i zamiany elementow polozonych daleko
od siebie
Counting sort co to?
jest to metoda sortowania danych, ktora polega na sprawdzeniu ile wystapien kluczy mniejszych
od danego wystepuje w sortowanej tablicy.
Merge sort co to?
rekurencyjny algorytm sortowania danych, stosujacy metode dziel i zwyciezaj. Dziel i zwyciezaj polega poprostu na dzieleniu danego problemu rekurencyjnie na dwa lub wiecej mniejszych podproblemow, az fragmenty stana sie wystarczajaco proste do bezposredniego rozwiazania.
Quick sort co to?
polega na wybraniu elementu rozdzielajacego (pivota) na mniejsze tablice. Do pierwszej tablicy przenoszone sa elementy mniejsze lub rowne pivotowi a do drugiej wieksze od pivota. Dzielimy tak tablice dopoki nie zostanie jeden element a nastepnie łączymy ale juz w wersji posortowanej.
Stack overflow co to?
błąd w programie polegający na próbie dostępu do pamięci, wiekszej niż dostępny rozmiar
przewidzianego na program. Powoduje przerwaie działania programu.
Czym moze być pivot w quick sorcie?
srodkowy element, pierwszy/koncowy element ciągu, losowy element ciągu, mediana z trzech elementów ciągu
Jaki należy użyć pivot aby uzyskać optymalny podział ciągu?
jeśli pivot będzie medianą wartości znajdujących się w sortowanym ciągu
Heap sort co to?
Jest to algorytm niestabilny ale za to szybki i niepochłaniający wiele pamięci. Tworzy on kopiec. Zaleta tego algorytmu jest to, że do tworzenie tego kopca mozemy wykorzystac tę samą tablicę, w której początkowo znajdują się nieposortowane elementy
Czego zalety wykorzystuje Tim sort?
wykorzystuje zalety insertion sort oraz merge sort
Gdzie stosujemy radix sort?
stosowany do sortowania kart
Bucket sort co to?
sortowanie polega na podziale danych wejsciowych na n podprzedziałow o równym rozmiarze. Nastepnie sortujemy elementy oddzielnie w kazdym kubełku
Jakie algortmy sortują w miejscu?
Insertion Sort,Selection Sort,Bubble Sort,Shell Sort,Heap Sort,Quick Sort
Jakie algorytmy nie sortują w miejscu?
Merge Sort,Counting Sort,Radix Sort
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Insertion sort??
O(n) O(n2) O(n2)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla selection sort??
O(n2) O(n2) O(n2)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla bubble sort??
O(n) O(n2) O(n2)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla shell sort??
O(n log2n) O(n1.25) O(n2)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Heap sort??
O(n log2n) O(n log2n) O(n log2n)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Merge sort??
O(n log2n) O(n log2n) O(n log2n)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla quick sort??
O(n log2n) O(n log2n) O(n2)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla counting sort??
O(n+k) O(n+k) O(n+k)
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla radix sort??
O(d(n+k)) O(d(n+k)) O(d*(n+k))
Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Bucket sort??
O(n) O(n) O(n2)
