Príprava na skúšku

Čisla sa porovnávajú a v prípade potreby vymieňajú.
Varianty:

• Maximum sa presúva dozadu:

for i in range(n - 1):
    for j in range(n -1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
Copy

• Minimum sa presúva dopredu:

for i in range(n - 1):
    for j in range(n - 1, i, -1):
        if a[j - 1] > a[j]:
            a[j - 1], a[j] = a[j], a[j - 1]
Copy

Pre zníženie počtu porovnávaní môžeme vykonať nasledovné optimalizácie:

• meniť smer porovnávanie (pretriasenie - shakesort)
• sledovať, či sa uskutočnila výmena, ak nie, cyklus sa ukončí
• zapamätať si index poslednej výmeny a porovnávať len po tento index

ČVZ:

Čísla sa porovnávajú a vymieňajú sa prvky na väčšie vzdialenosti. Pri každej výmene sa odstráni aspoň jedna inverzia. Platí, že čýčí. Alternatívne sa nazýva "rozdeluj a panuj."

Varianty:

1. Výber pivota
   1. Prvý prvok
   2. Prostredný prvok
   3. Náhodný prvok
2. Rozdelenie podľa pivota :
   1. , ,
   2. ,
   3. , ,
3. Rekurzívne triedenie rozdelených častí poľa.

Implementácia pomocou pomocného poľa:

def qsort(a):
    n = len(a)
    if n <= 1:
        return a
    else:
        pivot = a[0]
        men = [a[i] for i in range(1, n) if a[i] < pivot]
        vacs_rov = [a[i] for i in range(1, n) if a[i] >= pivot]
        return qsort(men) + [pivot] + qsort(vacs_rov)
Copy

Ďalšie variácie sú:

• Bentley
• Wirth

ČVZ:

1. Najhorší prípad:
   • Za pivota sa vyberie v každom rozdeľovaní minimum alebo maximum
2. Najlepší prípad:
   • Za pivota vyberie v každom rozdeľovaní medián (stredná hodnota).
3. Priemerný prípad:
4. Pamäťová výpočtová zložitosť:
   • Triedi sa na mieste a pri rekurzii sa obsadí zásobník veľkosti primerne .

Používa metódu "rozdeluj a panuj":

• postupnosť sa rozdelí na dve polovice, ktoré sa utriedia (rozdeľuj)
• utriedené polovice sa zlúčia do jednej utriedenej postupnosti (panuj)

Je vhodný aj na triedenie súborov.

Varianty:

1. Dvojcestné
2. Viaccestné zlučovanie

Implementácia triedenia zlučovaním:

def mergesort(a):
    if len(a) <= 1:
        return a
    else:
        s = len(a) // 2
        a1 = mergesort(a[:s])
        a2 = mergesort(a[s:])

        # zlučovanie
        i, j = 0, 0
        b = []
        while (i < len(a1)) and (j < len(a2)):
            if a1[i] < a2[j]:
                b.append(a1[i])
            else:
                b.append(a2[j])
                j += 1
        while i < len(a1):
            b.append(a1[i])
            i += 1
        while j < len(a2):
            b.append(a2[j])
            j += 1
        return b
Copy

PVZ:

Na zlučovanie je potrebná pomocná pamäť veľkosti vstupnej postupnosti - spolu a zásobník veľkosti .

ČVZ:

Variácie:

1. Triedenie výberom maxima
2. Triedenie výberom minima
3. Haldové triedenie
   • čiastočné usporiadanie poľa do haldy, v ktorej je maximum v koreni .

Implementácia triedením minima:

def maxsort(a):
    n = len(a)
    for j in range(n - 1, 0, -1):
        imax = j
        for i in range(j):
            if a[ i] > a[imax]:
                imax = i
        a[imax], a[j] = a[j], a[imax]
    return a
Copy

Implementácia triedením maxima:

def minsort(a):
    n = len(a)
    for j in range(n - 1):
        imin = j
        for i in range(j + 1, n):
            if a[i] > a[imin]:
                imin = i
        a[imin], a[j] = a[j], a[imin]
    return a
Copy

Haldové triedenie (heapsort):

• Halda - binárny strom s vlastnosťami:
  • Usporiadanie: č
  • Tvar: listy sú najviac v dvoch úrovniach čo najviac vľavo
  • ČVZ vytvorenia:
  • Opakuje sa -krát:
    • výmena maxima z koreňa s prvkom na konci haldy, zníženie počtu prvkov haldy,
    • obnovenie haldy

Implementácia heapsortu:

def heapify(a, l, r):
    p = l
    ch = 2 * p + 1
    if ch + 1 < r:
        if a[ch] < a[ch + 1]: ch += 1
    while ch < r:
        if a[p] < a[ch]:
            a[p], a[ch] = a[ch], a[p]
            p = ch
            ch = 2 * p + 1
            if ch + 1 < r:
                if a[ch] < a[ch + 1]:
                    ch += 1
        else:
            break

def heapsort(a):
    n = len(a)
    for i in range((n - 1) // 2, -1, -1):
        heapify(a,i,n)
    for i in range(n - 1, 1, -1):
        a[0], a[i] = a[i], a[0]
        heapify(a,0,i - 1)
    return a
Copy

Časová výpočtová zložitosť (alebo pamäťová ) problému rozsahu je minimum z výpočtových zložitostí (alebo ) všetkých algoritmov , ktoré riešia problém .

Napríklad:
je problém triedenia, jeho časová výpočtová zložitosť je minimum zo zložitostí všetkých triediacich algoritmov, napr. bubblesort , selectsort , mergesort , quicksort , heapsort .
Časová výpočtová zložitosť problému triedenia je .
Časová výpočtová zložitosť problému triedenia je .

Jednoduchá implementácia

m = a[0]
for i in range(1, n):
    if a[i] > m: m = a[i]
Copy

Implementácia pomocou RaP:

def max_rozdeluj(z, k):
    if z == k:
        return a[k]
    else:
        s = (z + k) // 2
        m1 = max_rozdeluj(z,s)
        m2 = max_rozdeluj(s+1,k)
        if m1 > m2:
            return m1
        else:
            return m2

def max(a):
    return max_rozdeluj(0, len(a) - 1)
Copy

Počet porovnaní:

• Úloha sa rozdelí na nezávislé podúlohy menšieho rozsahu
• Z výsledkov podúloh sa vytvorí riešenie celej úlohy
• quicksort, mergesort
• Zložitosti - lepšie ako priame metódy so zložitosťou

Iné algoritmy typu RaP:

• Strassenov algoritmus na násobenie matíc

ČVZ závisí od implementácie grafu a komponentov súvislosti. Pre graf daný zoznamom hrán s najviac komponentmi súvislosti implementovanými poľom:

• usporiadanie hrán:
• inicializácia komponentov súvislosti pre všetky vrcholy:
• pridávanie hrán do kostry :

Začneme z ľubovoľného domu. K nemu pripojíme najbližšieho suseda. Spomedzi nepripojených domov pripájame vždy ten, ktorý vieme pripojiť najkratšou cestou k minimálnej kostre.

Nedeterministický algoritmus môže generovať pre jeden vstup viac možných výpočtov. Možné výpočty znázorňuje výpočtový strom, v ktorom cesta od koreňa k listu predstavuje jeden možný výpočet.
Príklad: Prejdime všetky polia šachovnice šachovým koňom tak, že každé pole navštívi práve raz.
Výpočtová zložitosť nedeterministického algoritmu je hĺbka výpočtového stromu (dĺžka najdlhšej vetvy).

Výpočtová zložitosť deterministického algoritmu je súčet výpočtových zložitostí všetkých možných výpočtov nedeterministického algoritmu – exponenciálna.

Je taká úloha (problém), ktorá sa dá riešiť nedeterministicky v polynomiálnom čase. Hĺbka výpočtového stromu závisí od vstupu polynomiálne. Každá vetva stromu – nedeterministický výpočet – má polynomiálnu dĺžku. Ak existuje riešenie problému, vieme overiť jeho správnosť deterministicky v polynomiálnom čase. Na overenie neexistencie riešenia treba prehľadať celý výpočtový strom – v exponenciálnom čase.

Príklady:

• Vynásobte dve n-ciferné čísla. (P)
• Vyfarbite vrcholy grafu tromi farbami tak, aby vrcholy spojené hranou mali rôznu farbu. (NP)
• Prejdite šachovnicu koňom tak, aby na každé pole stúpil práve raz. (NP)
• Problém Hanojských veží. Preložte n kotúčov usporiadaných od najväčšieho dolu po najmenší hore z jednej tyče na druhú pomocou tretej tak, aby v žiadnom kroku výpočtu nebol väčší kotúč na menšom. (EXP)

Pre jeden vstup môžu generovať rôzne výpočty, ktorý z nich sa uskutoční, je vecou náhody.

Rozdelenie podľa umiestnenia náhodnej voľby:

• Algoritmus generuje výpočet, ktorý je v istých krokoch nedeterministický – príklad randomizovaný QuickSort.
• Algoritmus generuje výpočet, ktorý na začiatku náhodne volí z množiny deterministických stratégií – príklad nasleduje.

Rozdelenie podľa typu chyby:

• Las Vegas algoritmy – dajú správny výsledok
• Monte Carlo – dajú správny výsledok s požadovanou pravdepodobnosťou

Príklad: Máme dva počítače M1 , M2 spojené sieťou, ktoré majú uchovávať rovnakú databázu údajov. Ako zistíme, či je to tak?