- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Zjednodušená ukázka:
Stáhnout celý tento materiálmůžeme použít tzv. invariant – tvrzení, které platí po celou dobu výpočtu. Nutné je také ověřit konečnost algoritmu (pro všechna přípustná data algoritmus po konečném počtu kroků skončí).
Konečnost algoritmu:
Konečnost algoritmu je často intuitivně zřejmá tím, že se pro vstupní data nemůže algoritmus zacyklit. Matematicky lze dokázat konečnost algoritmu takto: Pokud najdeme způsob, který každý stav výpočtu ohodnotí přirozeným číslem, a ukážeme, že provedením jednoho kroku algoritmu se tato hodnota zmenší, je jasné, že algoritmus po konečném počtu kroků skončí, neboť interval počtu průchodů algoritmem je konečný.
Druhy algoritmů:
Algoritmy můžeme klasifikovat různými způsoby. Mezi důležité druhy algoritmů patří:
Rekurzivní algoritmy – využívají (volají) samy sebe
Hladové algoritmy – se k řešení propracovávají po jednotlivých rozhodnutích, která, jakmile jsou jednou učiněna, už nejsou dále revidována
Algoritmy typu rozděl a panuj – dělí problém na menší podproblémy, na něž se rekurzivně aplikují (až po triviální podproblémy, které lze vyřešit přímo), po čemž se dílčí řešení vhodným způsobem sloučí.
Algoritmy dynamického programování – pracují tak, že postupně řeší části problému od nejjednodušších po složitější s tím, že využívají výsledky již vyřešených jednodušších podproblémů. Mnoho úloh se řeší převedením na grafovou úlohu a aplikací příslušného grafového algoritmu.
Pravděpodobnostní algoritmy (někdy též probabilistické) – provádějí některá rozhodnutí náhodně či pseudonáhodně.
Paralelní algoritmy – v případě, že máme k dispozici více počítačů (procesorů nebo jader), můžeme úlohu mezi ně rozdělit, což nám umožní ji vyřešit rychleji; tomuto cíli se věnují.
Genetické algoritmy – pracují na základě napodobování biologických evolučních procesů, postupným „pěstováním“ nejlepších řešení pomocí mutací a křížení. V genetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápany jako možná řešení daného problému.
Heuristické algoritmy – si za cíl nekladou nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používají se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy vůbec známy).
Vloženo: 20.12.2010
Velikost: 48,00 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2024 unium.cz