Wykład pierwszy

Question 1

Teoria obliczeniowa?

Answer 1

jest nauką o procesach algorytmicznych, czyli analizy, projektowanie, efektywność,
implementacja,zastosowanie

Question 2

Algorytm?

Answer 2

opisuje procedure złożoną ze skończonej liczby kroków, jakie należy wykonać dla uzyskania wynikow bedacych celem tego algorytmu

Question 3

Czy problem Collatza zakończy się dla dowolnego x?

Answer 3

Nie

Question 4

Inserion sort co to?

Answer 4

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:

Question 5

Co jest podstawowym model obliczeń?

Answer 5

jednoprocesowa maszyna z dostępem do Random Access Machine

Question 6

Selection sort co to?

Answer 6

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.

Question 7

Bubble sort co to?

Answer 7

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.

Question 8

Czym jest algorytm stabilny?

Answer 8

zawsze zachowuje wejsciowy porzadek elementow o tej samej wartosci.

Question 9

Czym jest algorytm niestabilny?

Answer 9

nie gwarantuje, ze elementy o tej samej wartosci beda wzgledem siebie uporzadkowane
na wyjsciu tak samo jak w ciagu wejsciowym.

Question 10

Shell sort co to?

Answer 10

Jest to uogolnienie sortowania
przez wstawianie lub sortowania babelkowego, dopuszczajace porownania i zamiany elementow polozonych daleko
od siebie

Question 11

Counting sort co to?

Answer 11

jest to metoda sortowania danych, ktora polega na sprawdzeniu ile wystapien kluczy mniejszych
od danego wystepuje w sortowanej tablicy.

Question 12

Merge sort co to?

Answer 12

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.

Question 13

Quick sort co to?

Answer 13

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.

Question 14

Stack overflow co to?

Answer 14

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.

Question 15

Czym moze być pivot w quick sorcie?

Answer 15

srodkowy element, pierwszy/koncowy element ciągu, losowy element ciągu, mediana z trzech elementów ciągu

Question 16

Jaki należy użyć pivot aby uzyskać optymalny podział ciągu?

Answer 16

jeśli pivot będzie medianą wartości znajdujących się w sortowanym ciągu

Question 17

Heap sort co to?

Answer 17

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

Question 18

Czego zalety wykorzystuje Tim sort?

Answer 18

wykorzystuje zalety insertion sort oraz merge sort

Question 19

Gdzie stosujemy radix sort?

Answer 19

stosowany do sortowania kart

Question 20

Bucket sort co to?

Answer 20

sortowanie polega na podziale danych wejsciowych na n podprzedziałow o równym rozmiarze. Nastepnie sortujemy elementy oddzielnie w kazdym kubełku

Question 21

Jakie algortmy sortują w miejscu?

Answer 21

Insertion Sort,Selection Sort,Bubble Sort,Shell Sort,Heap Sort,Quick Sort

Question 22

Jakie algorytmy nie sortują w miejscu?

Answer 22

Merge Sort,Counting Sort,Radix Sort

Question 23

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Insertion sort??

Answer 23

O(n) O(n2) O(n2)

Question 24

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla selection sort??

Answer 24

O(n2) O(n2) O(n2)

Question 25

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla bubble sort??

Answer 25

O(n) O(n2) O(n2)

Question 26

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla shell sort??

Answer 26

O(n log2n) O(n1.25) O(n2)

Question 27

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Heap sort??

Answer 27

O(n log2n) O(n log2n) O(n log2n)

Question 28

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Merge sort??

Answer 28

O(n log2n) O(n log2n) O(n log2n)

Question 29

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla quick sort??

Answer 29

O(n log2n) O(n log2n) O(n2)

Question 30

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla counting sort??

Answer 30

O(n+k) O(n+k) O(n+k)

Question 31

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla radix sort??

Answer 31

O(d(n+k)) O(d(n+k)) O(d*(n+k))

Question 32

Jaka jest optymistyczna, średnia i pesymistyczna złozoność dla Bucket sort??

Answer 32

O(n) O(n) O(n2)