Problémy a algoritmy

Obsah cvičení

• Pojmy z přednášky: problém, instrukce, algoritmus, časová složitost algoritmu

• Pseudokód

• Příklady problémů, algoritmů a jejich složitostí.

  ---

• (z minula) Něco málo k logaritmům, faktoriálů a kombinatorice.

Opakování z přednášky

• problém?
• instrukce?
• algoritmus?
• časová složitost algoritmu?

Zápis algoritmu pseudokódem

Pár základních konstrukcí, které budeme potřebovat. Další na přednášce, případně v Cormen et al.: Introduction to algorithms.

Přiřazení

“Do proměnné a ulož hodnotu b.”
a ← b

x ← 2 * y − 3/5

Podmíněný příkaz

“Pokud platí podmínka, tak udělej …, jinak udělej …”

1. if a = b then c ← 1
2.                      print(c je jedna)
3.              else c ← 2
4.                      print(c je dva)

Odsazení řádků je důležité.

Cykly

Cyklus for

Cyklus s řídící proměnnou.
“Pro i od … do … udělej …”

1. for i ← 0 to 10 do
2.    k ← i * i
3.    print(k*k)

Cyklus while-do

Cyklus opakující se dokud platí podmínka.
“Dokud platí podmínka opakuj …”

1. i ← 0
2. while (i <= 10)
3.    k ← i * i
4.    print(k*k)
5.    i++

Cyklus repeat-until

Cyklus opakující se dokud neplatí podmínka, který ale vždy proběhne alespoň jednou.
“Opakuj … dokud neplatí podmínka”

1. i ← 0
2. repeat
3.    k ← i * i
4.    print(k*k)
5.     i++
6. until (i = 11)

Existuje i cyklus do-while, který opakuje činnost, dokud podmínka platí.

Příklady na cvičení

(tabule): Následující problémy popište pomocí možných vstupů a odpovídajících výstupů. Navrhněte a nejprve slovně a poté pseudokódem popište algoritmus pro jejich řešení. Jako má navržený algoritmus časovou složitost?

1. Pro zadané číslo n vypište druhé mocniny všech čísel od 1 do n.
2. Pro zadané číslo n vypište “násobilku” až do hodnoty n ⋅ n.
3. Pro zadané slovo spočítejte, kolikrát obsahuje jednotlivá písmena abecedy (nerozlišujte velikost).

Logaritmy

Stručný přehled toho, co byste měli znát.

(tabule): Význam, graf a pár základních vlastností.

Faktoriál

Stručný přehled toho, co byste měli znát.

(tabule): Význam a graf. Shrnutí pro nás důležitých rysů doposoud zmíněných funkcí.

Kombinatorika

Stručný přehled toho, co byste měli znát.

(tabule): Permutace, variace, kombinace. Permutace a počet pořadí prvků.

Úkoly k procvičení

Následující problémy popište pomocí možných vstupů a odpovídajících výstupů. Navrhněte a nejprve slovně a poté pseudokódem popište algoritmus pro jejich řešení. Algoritmus implementujte v jazyce C.

1. Je zadané číslo sudé nebo liché?
2. Řešení lineární rovnice a ⋅ x + b = 0.
3. Násobení dvou přirozených čísel. Zkuste navrhnout algoritmus používající z aritmetických operací pouze sčítání a odčítání.