Algoritmy a štruktúry údajov Prednáška 1 PDF

Algoritmy a štruktúry údajov Prednáška 1 – Algoritmický problém. Algoritmus. Algoritmizácia. Vlastnosti algoritmov. Program. Programovanie. Programovacie paradigmy. Lietratúra  CORMEN, H. T. et al: Introduction to algorithms. The 2nd edition, Cambridge: MIT Press, 2001.  SKIENA, S. S.,...

Algoritmy a štruktúry údajov Prednáška 1 – Algoritmický problém. Algoritmus. Algoritmizácia. Vlastnosti algoritmov. Program. Programovanie. Programovacie paradigmy. Lietratúra  CORMEN, H. T. et al: Introduction to algorithms. The 2nd edition, Cambridge: MIT Press, 2001.  SKIENA, S. S., REVILLA, M.: Programming Challenges. USA: Springer, 2003.  KNUTH, D. E.: Umění programování 1. Základní algoritmy. Brno: Computer Press, 2008.  WRÓBLEWSKI, P.: Algoritmy. Datové struktury a programovací techniky. Brno: Computer Press, a.s., 2004.  GVOZDJAK, L. et al.: Počítače a programovanie. Bratislava: ALFA, 1987.  STN 36 9030 Počítače a systémy spracovania údajov. Symboly vývojových diagramov pre systémy spracovania údajov. Von Neumannova koncepcia ČP Reálny svet vs. Model sveta  Reálny svet vs. Model sveta „Snaha modelovať realitu ako by nás utvrdzovala vo videní dvoch svetov. Jedným z nich je svet abstraktný (teda ne- reálnych) modelových konštruktov, cez ktorý svet vnímame, druhý je svet an- sicht, svet empirický, nemodelovateľný (pretože je skutočný a nedá sa s ním hýbať ako s konštruktami.“ Sedláček, T. Programovacie paradigmy  štruktúrovaného programovania  procedurálneho programovania  objektovo-orientovaného programovania  logického programovania  funkcionálneho programovania Problém „Problém je charakterizovaný kvantitatívnym rozdielom dvoch stavov, a to stavu východzieho = počiatočného (ktorý je charakterizovaný absenciou istého poznatku) a požadovaného cieľového = koncového stavu (v ktorom sme hľadaný poznatok dosiahli, získali).“ Hvorecký, Burianová, Blahová Algoritmický problém Definícia Algoritmicky riešiteľný problém je taký problém, na ktorého riešenie môžeme použiť deterministický automat. Tri prípady: 1.triviálne riešenie (pozriem a vidím) 2.existuje algoritmus (stačí implementovať) 3.riešenie nepoznáme (musíme ho nájsť) Metódy riešenia algoritmického problému  dekompozícia na podproblémy riešenie zhora nadol riešenie zdola nahor  pohyb po strome hľadania riešení do hĺbky do šírky Algoritmus „Algoritmus je postup, pomocou ktorého môžeme vyriešiť zadaný problém.“ (Hála) „Algoritmus je konečná postupnosť postupov aplikovaných na konečný počet dát, ktorá dovoľuje riešiť približne rovnaké triedy problémov.“ (Dictionnaires le Robert) „Všeobecné pravidlá určujúce postupnú transformáciu vstupných údajov na výstupné nazývame algoritmus.“ (Gvozdiak) Algoritmus  Abu Ja’far Muhamad ibn Musa al-Khwarizmi  * 780 v Bagdade – 850  matematik  aritmetické operácie na desatinných číslach  Algoritmus Všeobecné pravidlá určujúce postupnú transformáciu vstupných údajov na výstupné nazývame algoritmus.  postupnú transformáciu (algoritmy)  vstupných údajov na výstupné (štruktúry údajov) Algoritmus – vlastnosti  hromadnosť (algoritmus je použiteľný pre ľubovoľné vstupné údaje spĺňajúce požadované vstupné podmienky);  determinovanosť (v každom kroku algoritmu je jednoznačne dané, čo sa má vykonať);  rezultatívnosť (transformácia predpísaná algoritmom sa po konečnom počte krokov zastaví a dá požadované výsledky). Zápis algoritmu  graficky (vývojový diagram, kopenogram – štruktúrogram);  slovne (prirodzený jazyk);  matematicky;  programovacím jazykom. Algoritmizácia vs. programovanie  algoritmizácia – zostavovanie algoritmu, aby spĺňal stanovené podmienky (vstup: problém, výstup: algoritmus);  programovanie – prepis algoritmu do programovacieho jazyka (vstup: algoritmus, výstup: program) Algoritmy – iný pohľad vlastnosti  činnosti Algoritmy – iný pohľad Zhrnutie algoritmus; vlastnosti algoritmov; zápis algoritmov; program.