zpět

Algoritmy I

Hodnocení aktivity: skupina 14:15 skupina 16:00

Cvičení 1 - Implementace a využití zásobníku

Zásobník na wikipedii.
Rozhraní k implementaci zde.
Řešení zde.

Cvičení 2 - Implementace fronty

Implementace fronty v poli zde.
Spojová implementace fronty zde.

Cvičení 3 - Rozšíření fronty o funkce typické pro seznam

Implementace zde.

Cvičení 4 - Analýza složitosti iterativních algoritmů

Základní funkce pro práci s poli a ukázka měření času v c++ zde.

Pseudokódy k implementaci a analýze:

    MatrixMultiplication(A[0..n − 1, 0..n − 1], B[0..n − 1, 0..n − 1])
        //Multiplies two square matrices of order n by the definition-based algorithm
        //Input: Two n × n matrices A and B
        //Output: Matrix C = AB
        for i ← 0 to n − 1 do
            for j ← 0 to n − 1 do
                C[i, j] ← 0.0
                for k ← 0 to n − 1 do
                    C[i,j] ← C[i,j] + A[i,k] * B[k,j]
        return C

    Enigma(A[0..n − 1, 0..n − 1])
        //Input: A matrix A[0..n − 1, 0..n − 1] of real numbers
        for i ← 0 to n − 2 do
            for j ← i + 1 to n − 1 do
                if A[i,j] = A[j,i]
                    return false
        return true
    
Implementace zde.

Cvičení 5 - Analýza složitosti rekurzivních algoritmů

Samostudium z knihy „Introduction to the design and analysis of algorithms.“ Kapitola 2.4 + Apendix B (strany 479-482).
Kniha zde.

Úkoly: