Wp/isv/Algoritm
V informatikě algoritm jest detaljny plan rěšenja danogo problema, prědstavjeny s pomočju ograničenogo čisla krokov, pri ktorom kriterije uspěhu (često vzajemno protivne) sut čas, košt i lihva.
Zapytanjami svezanymi s optimalizacijeju algoritmov zajmaje se Teorija sistem.
Kroky
[edit | edit source]Tipične kroky v razvoju algoritmov:
- Definicija problema
- Razvivanje modela
- Specifikacija algoritma
- Dizajn algoritma
- Prověrjanje popravnosti algoritma
- Analiza algoritma
- Implementacija algoritma
- Testovanje programa
- Prigotovjenje dokumentacije
Algoritmy v informatikě
[edit | edit source]Rekurencija i iteracija
[edit | edit source]Rekurencija znači to, že algoritm zna někaku bazovu osnovu svojego rabotanja, a ine vyše složene slučaje sut rěšene prěz navodženje samogo sebe. Tuta metoda javi se vyše prosta v implementaciji, ale problem nastaje kogdy kolikost navedenij je vysša než dozvaljaje programny stog.
Iteracija znači to, že někaka akcija je dělana každogo hodu, np. dodavanje čisla 1 do čisla, ktore ty uže imaš. Prěd jej implementacijeju ty potrěbuješ znati točnu kolikost razov koliko iteracij bude sdělanyh.
Priměry v Python
[edit | edit source]Evklidov algoritm, stvorjeny grečskym matematikom Evklidom i objasnjeny jim v dělu Elementy, izčisljaje največši obči dělitelj dvoh čisl:
def gcd(a, b):
while b:
a, b = b, a % b
return a
Složenost čisljenja
[edit | edit source]Každy algoritm ima někaky čas, ktory potrěbuje da by rabotati i zakončiti svoje rabotanje v někakom ograničonom času.
Zavisno od togo, kako informacije sut upravjane. Složenost algoritmov naznača se velikoju bukvoju O(n). Objasnjenje priměrami:
O(1) - ty jesi bibliotekar. Každy čitatelj, ktory prihodi, dostavaje od tebe knigu. Konec historije.
O(n) - imaš sbirku knig, ktorih je n. Ne znaš, kde je ta jedna, ktoru hčeš. Iščeš prěgledajuči každu iz njih.
O(log n) - imaš veliky sbornik knig. Vse knigi s zaglavjami, ktore počinajut se od bukvy A do poloviny alfabeta sut po tvojej lěvoj straně, ostale od poloviny alfabeta do konca sut po tvojej pravoj straně. Ne trěbuješ prěgledati vsih knig, da by najdti tu jednu - gledaš toliko po někakoj větkě.
Žrla
[edit | edit source]- Popularna Encyklopedia Powszechna, Fogra Oficyna Wydawnicza, Kraków 1994
- Cory Althoff, Informatyk samouk, wydawnictwo Helion, prěvod: Piotr Rajca
- "Euclidean Algorithm / GCD in Python". stackoverflow.com.
