Co je to algoritmus.pdf

Co je to algoritmus? • řešení určitého problému, který se skládá z řady kroků, které se musí postupně provést Jak lze znázornit algoritmus? • pseudokódem • vývojovým diagramem • strukturogramem (tabulka) • kódem v nějakém programovacím jazyce • matematicky (vzorcem) Jaké jsou druhy algor...

Co je to algoritmus? • řešení určitého problému, který se skládá z řady kroků, které se musí postupně provést Jak lze znázornit algoritmus? • pseudokódem • vývojovým diagramem • strukturogramem (tabulka) • kódem v nějakém programovacím jazyce • matematicky (vzorcem) Jaké jsou druhy algoritmů? • rekurzivní • iterativní • sériový • paralelní • distribuovaný Co je to algoritmizace? • proces tvorby algoritmu pro řešení konkrétního problému • název způsobu myšlení potřebný pro tvorbu algoritmů Co je to program? • implementace algoritmů • posloupnost instrukcí, která popisuje činnost počítače Co je to programovací jazyk? • jeden z nástrojů pro implementaci algoritmů a zápis programů • poskytuje programátorovi abstrakci nad binárním strojovým kódem • míru abstrakce určuje to, jestli je nízkoúrovňový, nebo vysokoúrovňový Jaké jsou druhy programovacích jazyků? • nízkoúrovňové • vysokoúrovňové • kompilované • interpretované • transpilované • imperativní • objektově orientované • procedurální • funkcionální Jaké jsou zásady tvorby algoritmů? • správně implementovaný algoritmus je dán množinou 6 vlastností • těmito vlastnostmi jsou konečnost, správnost, resultativnost, determinovanost a univerzálnost • Konečnost: algoritmus po určitém počtu kroků skončí (nezacyklí se) • Správnost: výsledek, který vznikne použitím algoritmu, musí být správný • Resultativnost: po konečném počtu kroků dospěje k řešení (nebo alespoň vrátí chybové hlášení) • Determinovanost: v každém kroku je jednoznačně určen způsob pokračování práce algoritmu • Univerzálnost: algoritmus lze použít pro řešení obecné úlohy (sčítání 2 čísel - chceme umět sčítat libovolné 2 čísla) • Opakovatelnost: algoritmus vede vždy ke stejným výsledkům, jsou-li zadána stejná data Jaké základní generace programovacích jazyků existují? • • • 1. generace = Strojový kód o jednoúčelové programy, obvykle s využitím v matematice a fyzice o instrukce jsou tvořeny posloupností nul a jedniček (bitů) o je hardwarově závislý o obtížné hledání chyb o prakticky nečitelný 2. generace = Jazyk symbolických adres o obecné příkazy (např. „načti data“, „zapiš data“) o ty jsou zkracovány pomocí symbolických názvů (MOV, JMP, ...) o příkazy překládá do strojového kódu procesoru speciální program – assembler o také hardwarově závislý o čitelnost je lepší o porozumění je stále těžké 3. generace = Procedurální jazyky o vyšší úroveň programování (podoba s lidským jazykem) o vznik hardwarově nezávislých programovacích jazyků • o přichází koncept strukturovaného programování (předchůzce OOP; návrh shora dolů) o přicházejí procedury (funkce) o jazyky: C, Pascal, SQL 4. generace = Objektově orientované jazyky o WYSIWYG o jedná se o jakousi snahu o reprezentaci reálného světa pomocí objektů o jazyky: C# Jaký je rozdíl mezi jazyky Wiring, PHP a C#? • liší se způsobem překladu jejich zdrojového kódu o kompilované jazyky: C#, Wiring o interpretované jazyky: PHP Jak vypadá základní struktura programu v jazyce C#? • základní struktura se liší vytvořeným řešením (konzolová aplikace, desktopová aplikace, ...) • seznam knihoven (= using) • jmenný prostor (= namespace) • třída (= zapouzdřuje hlavní metodu) • hlavní metoda (= spustí se po startu konzolové aplikace) using System; namespace test { internal class Program { static void Main(string[] args) { Console.WriteLine("Hello, World!"); } } } Jak vypadá základní struktura programu v jazyce Wiring? • metoda setup() = vykoná se při startu programu • metoda void() = vykonává se opakovaně po dobu běhu programu, a to ihned po dokončení metody setup() void setup() { } void loop() { } Jak vypadá základní struktura programu v jazyce PHP? • kód se píše mezi tagy do souboru s příponou .php <?php echo "Hello, World!"; ?> Jak vypadá základní struktura programu v jazyce JavaScript? • kód se (v základu) píše do souboru s příponou .js console.log("Hello, World!"); Jak vypadá základní struktura programu v jazyce Assembler? • kód se píše do souboru s příponou .asm MOV 30h, #51h Co jsou to identifikátory? • pojmenovávají entity jazyka, např. proměnné, typy, funkce, struktury, objekty • zásady názvů identifikátorů záleží na konkrétním jazyku, případně pojmenovávané entitě (jinak pojmenováváme funkce, jinak objekty, proměnné, konstanty, ...) • klíčová slova: příkazy, který mají svůj vlastní význam (mohou to být i aliasy - string = String) • název proměnné = identifikátor (nesmí mít stejný název jako klíčové slovo, nesmí začínat číslicí) Co jsou to oblasti platnosti (scopes)? • definují oblast, ze které je možné k vlastnosti přistupovat • základní oblasti platnosti: public, private, protected • obecně rozlišujeme oblasti: o Globální: identifikátor je přístupný v celém programu • o Modulová: identifikátor je přístupný pouze v konkrétním modulu o Funkční: identifikátor existuje pouze v konkrétní funkci o Kódového bloku: identifikátor je přístupný pouze ve složených závorkách {} (pokud se jimi v jazyce vymezuje kódový blok, např. tělo cyklu) oblasti v C#: o public ▪ o protected internal ▪ o k vlastnosti je možné přistoupit zevnitř třídy, mimo vnitřek třídy, a to pouze v rámci sestavení protected ▪ o k vlastnosti je možné přistoupit zevnitř třídy, mimo vnitřek třídy, a to pouze v rámci sestavení (případně z jiného sestavení, pokud se tam nachází odvozená třída, která z této třídy dědí) internal ▪ o k vlastnosti je možné přistoupit zevnitř třídy, mimo vnitřek třídy i mimo sestavení k vlastnosti je možné přistoupit pouze zevnitř třídy a ve třídách z ní dědící private ▪ k vlastnosti je možné přistoupit pouze zevnitř třídy Jak se dělí algoritmy podle implementace? • rekurzivní • iterativní Co je to rekurzivní algoritmus? • rekurzivní algoritmus si lze představit jako funkci, ve které je kód algoritmu zapouzdřený • rekurze spočívá v opakovaném volání této funkce • rozdělí problém na několik podproblémů, jejichž vysledky uchovává v zásobníku a následně je používá k získání kýženého výsledku • funkce je znovu volána dříve, než je dokončeno její předchozí volání • stejný postup opakuje na částech vstupních dat • musí obsahovat zarážku = podmínku, která má rekurzní volání ukončit a vrátit výsledek • zarážka indikuje, že již neexistuje žádný podproblém, který je nutno řešit rekurzivně • výsledek vrácený zarážkou je použit k získání mezivýsledků (výsledků podproblémů) • výsledky podproblémů postupně "vybublávají" napovrch, až je k dispozici výsledek pro vyřešení rozloženého problému • příklady rekurzivních algoritmů: výpočet faktoriálu, zjištění správnosti počtu otevíracích a uzavíracích závorek v matematickém příkladu Jaké jsou výhody rekurzivního algoritmu? • pro některé úlohy mohou být intuitivnější a snazší k implementaci • zápis kódu bývá kratší • u jednodušších problémů je přehledný Jaké jsou nevýhody rekurzivního algoritmu? • používá zásobník (LIFO - Last In First Out) pro předání parametrů volání - vyžaduje paměť navíc • třeba pečlivě zajistit, aby rekurze skutečně končila, jinak může dojít k nekonečnému volání • při špatné implementaci StackOverflow exception Co je to iterativní algoritmus? • algoritmus, který se opakuje v cyklu, dokud nedojde k požadovanému výsledku • spočívá v opakování určité své části kódu (bloku) • rekurzivní algoritmus lze vždy převést do iterativní podoby • př.: procházíme pole cyklem a poté vrátíme výsledek • příklady iterativních algoritmů: Bubble sort, Insertion sort Jaké jsou výhody iterativního algoritmu? • snazší k implementaci a čtení • menší spotřeba paměti Jaké jsou nevýhody iterativního algoritmu? • pro složité úlohy mohou být obtížné k implementaci Co je to sériový algoritmus? • vykonává všechny příkazy jeden po druhém (v sérii) • ne vždy lze převést sériový na paralelní • ne vždy dojde při převedení ze sériového na paralelní ke zrychlení o vhodné pro obrovské množství repetitivních příkazů, jejichž synchronní provedení je příliš pomalé o jsou-li příkazy nenáročné, synchronní přístup bývá rychlejší – nedochází k předávání dat mezi vlákny Co je to paralelní algoritmus? • vykonává všechny příkazy zároveň (ve více vláknech) • využívá vícevláknové zpracování o př.: Grafické rozhraní u procesu WPF aplikace běží v jednom, hlavním vlákně o pokud vytvoříme paralelní (asynchronní) algoritmus, nebude toto hlavní vlákno blokovat o spustí se totiž ve vlákně novém a grafické rozhraní tak nezamrzne (bude pro uživatele nadále responzivní a interaktivní) Co je to distribuovaný algoritmus? • vykonává všechny příkazy zároveň (na více strojích) • dosáhnutí rychlejšího výsledku Jak se dělí jazyky podle míry abstrakce? • nízkoúrovňové • vysokoúrovňové Co jsou to nízkoúrovňové jazyky? • svojí strukturou se blíží strojovému kódu • pracují s registry, paměťovými adresami a zásobníkem volání • jsou závislé na určitém typu procesoru • využití je dnes už výjimečné o psaní rychlých programů pro jednočipové počítače o psaní jader OS • jazyky symbolických adres: Assembly • (Assembler je název překladače pro překlad jazyka symbolických adres na strojový kód) Jaké jsou výhody nízkoúrovňových jazyků? • rychlost programu - nejvyšší, které lze programováním dosáhnout Jaké jsou nevýhody nízkoúrovňových jazyků? • nepřenositelnost na jiný typ procesoru • složité programování • ne příliš srozumitelný zápis Co jsou to vysokoúrovňové jazyky? • umožňují zapisovat programy, které se více blíží přirozenému lidskému jazyku • pracují s proměnnými, poli, objekty, funkcemi, cykly, vlákny • C#, Java, Python, C++ Jak se dělí vysokoúrovňových jazyků (dle spouštění programů)? • kompilované • interpretované • transpilované Co jsou to kompilované jazyky? • jsou převáděny přímo na strojový kód • zdrojový kód je přeložen překladačem (kompilátorem) na strojový kód • teprve po překladu lze program spustit • např.: Wiring, C#, C, C++, Go o C# (.NET využívá jak kompilátoru pro překlad do mezikódu, tak interpretu pro překlad do strojového kódu) Co je to kompilátor? • program, který převede/přeloží kód kompilovaného programovacího jazyka do strojového kódu Jaké jsou výhody kompilovaných jazyků? • pokud se překlad nepovede, spuštění programu nebude možné (chyby se odhalí hned při kompilaci) • přeložený program poté běží srovnatelně rychle, jako kdyby byl napsán např. v Assembleru • zkompilovaný kód nelze jednoduše modifikovat Jaké jsou nevýhody kompilovaných jazyků? • při změně zdrojového kódu je nutné provést znovu překlad • jakmile se program jednou zkompiluje do strojového kódu, nelze ho editovat jinak, než opětovnou kompilací • určitá závislost na platformě Co jsou to interpretované jazyky? • kód je vyhodnocován řádek po řádku při běhu programu • kód vyhodnocuje (interpretuje) program zvaný interpret • při každém volání se dané volání znovu analyzuje interpretem, a teprve poté jej provede interpret • např.: Python, PHP, Ruby, JavaScript Jaké jsou výhody interpretovaných jazyků? • řeší problém přenositelnosti programů mezi různými platformami • dynamické typování (=není možné nebo není povinné definovat datový typ) Jaké jsou nevýhody interpretovaných jazyků? • zjištění chyb až při spuštění chybného kódu • pomalejší než kompilované jazyky Co jsou to transpilované jazyky? • program se přeloží/transpiluje do zdrojového kódu v jiném jazyce • např.: zdrojový kód psaný v TypeScriptu se přeloží na JavaScript • využití: převod kódu ze staršího jazyka do nového; převod již existujícího kódu do modernější podoby Jaké jsou výhody transpilovaných jazyků? • můžeme psát kód v novějším jazyce, který se automaticky přeměnní na jazyk jiný Co je to transpilátor? • speciální typ kompilátoru • převádí zdrojový kód z jednoho vysokoúrovňového programovacího jazyka, na druhý Jak lze rozdělit vysokoúrovňové jazyky dle přístupu k psaní kódu? • imperativní • objektově orientované • procedurální • funkcionální Co jsou to imperativní vysokoúrovňové jazyky? • využívají příkazy, které mění stav programu (dokáží přepisovat hodnoty proměnných) • provádění příkazů je pevně definováno Co jsou to objektově orientované programovací jazyky? • objekt je nějaká skutečnost (např. konkrétní člověk, konkrétní firma), o níž uchováváme data a operace pro manipulaci s těmito daty • třída je kategorie, do níž daný objekt patří, např. třída všech lidí, třída všech firem • dědičnost je vztah mezi nižší a vyšší třídou, při němž třída – potomek převezme rysy od třídy – rodiče • polymorfismus – na stejný podnět reagují objekty různých tříd různě • C++, C#, Python, Javascript Co jsou to procedurální programovací jazyky? • skládá se z bloků příkazů - procedur/subrutin • mohou se volat kdykoliv při běhu programu, klidně i ostatními procedurami Co jsou to funkcionální programovací jazyky? • všechno se bere jako matematická funkce (pro stejné argumenty vrátí vždy stejný výsledek, neobsahuje vedlejší efekty) • Haskell, F# Co je to proměnná? • konkrétní adresa nebo oblast adres v paměti • její obsah se může za běhu programu měnit