Prezentace na téma struktura algoritmů. Základní algoritmické struktury

Algoritmus a algoritmické struktury

Mosina A.Yu.

Algoritmus je přesně definovaný sled akcí při řešení problému.

Algoritmus obsahuje několik kroků.

Krok algoritmu je každá jednotlivá akce algoritmu.

"Algoritmus je pořadí akcí."

Vykonavatel je objekt, který provádí specifickou sadu akcí.

Účinkujícím může být člověk, robot, zvíře nebo počítač.

Exekutorský příkazový systém (LYŽE) je sada příkazů, které může umělec provádět.

Prostředí umělce – prostředí, ve kterém účinkující působí.

• Vyvíjí algoritmy: lidské
• Algoritmy provádějí: lidé a zařízení - počítače, roboti, stroje, satelity, komplex Spotřebiče, Dětské hračky.
• Interpret řeší problém podle daného algoritmu, striktně dodržuje instrukce (program), aniž by se nořil nebo diskutoval o tom, proč to dělá.

Cvičení: Vyjmenujte umělce následujících typů prací:

Úklid odpadků na dvoře

Výuka dětí ve škole

Řízení auta

Odpověď je na desce

Vaří jídlo

Tisk dokumentu na tiskárně

Končetina– každá jednotlivá akce a algoritmus jako celek musí být možné dokončit

Účinnost– získání výsledků v konečném počtu kroků

Diskrétnost(nespojitost, oddělenost) – rozdělení algoritmu na kroky

Determinismus(jistota, přesnost) – každá akce musí být striktně a jednoznačně definována

Masový charakter– použití algoritmu k řešení podobných problémů

Vlastnosti ALGORITU

Klasifikace algoritmů podle prezentační formy :

Slovní

Tabelární

Grafika (bloková schémata)

Software

Blokové schéma – grafický výkon algoritmus ve formě sekvence vzájemně propojených funkčních bloků ( standardní grafické prvky ), z nichž každá odpovídá provedení jedné nebo více akcí.

Základní konvence v blokových diagramech

Symbol

Účel bloku

Začátek nebo konec algoritmu

Vstup nebo výstup dat.

Uvnitř bloku jsou data uvedena oddělená čárkami.

Proces.

Uvnitř bloku je napsána matematika. vzorce a operace pro zpracování dat.

Kontrola stavu.

Uvnitř bloku jsou zapsány logické podmínky. Má dva výstupy Ano (+) a Ne (-).

Směr.

Klasifikace algoritmů podle struktury:

Lineární (následující)

Rozvětvený (pobočka, výběr, alternativa)

Smyčka (opakování)

Pomocný

Kombinovaný

Lineární algoritmus

Lineární algoritmus je algoritmus, jehož kroky se provádějí postupně jeden po druhém.

(Příklad: algoritmus sběru portfolia).

Základní struktura lineárního algoritmu:

Týmová série 1

Týmová série 2

Série týmu N

Úkol

Vypočítejte obvod libovolného trojúhelníku na základě jeho tří stran.

Řešení:

Fáze 1: Formulace problému.

Počáteční údaje: A, B, C – strany libovolného trojúhelníku

Výstup: P – obvod trojúhelníku.

Fáze 2: Matematický model.

P=A+B+C

Fáze 3: Sestavení algoritmu

Start

Vstupte

Závěr

Konec

№ 1 A pomocí vývojového diagramu algoritmu , vypočítat hodnotu funkce Y v X=2,

Start

vstup: X

Z = 8*X

• ŘEŠENÍ:

• X=2
• Z = 8 * 2 = 16
• Z = √16 = 4
• Z = 4 – 1 = 3
• Y = 3 * 2 = 6
• Y = 6/3 = 2

Z = Z-1

Y=3*X

Y=Y/Z

výstup: Y

• Algoritmy mohou popisovat transformační procesy široké škály objektů. Samotné slovo „algoritmus“ pochází z „algorithmi“ – latinského pravopisu jména vynikajícího matematika al-Khwarizmiho z 9. století, který formuloval pravidla pro provádění aritmetických operací.
• Algoritmus- soubor příkazů, které popisují pořadí akcí interpreta k dosažení výsledku řešení problému v konečném počtu akcí.

Vlastnosti algoritmů:

1. Diskrétnost- algoritmus musí představovat proces řešení problému jako sekvenční provádění určitého jednoduché kroky. V čem každý krok algoritmu vyžaduje konečné množství času na dokončení, to znamená, že transformace zdrojových dat na výsledky se provádí diskrétně v čase.

2. Determinismus (jistota). V každém okamžiku je další krok práce jednoznačně určen stavem systému. Algoritmus tedy produkuje stejný výsledek (odpověď) pro stejná počáteční data.

3. Jasnost- algoritmus by měl zahrnovat pouze ty příkazy, které jsou pro účinkujícího dostupné a jsou zahrnuty v jeho příkazovém systému.

4. Úplnost (extrémnost)- se správně zadanými počátečními daty musí algoritmus dokončit svou práci a vytvořit výsledek v konečném počtu kroků.

5. Masový charakter (univerzálnost). Algoritmus musí být použitelný pro různé sady vstupních dat.

6. Účinnost- dokončení algoritmu s určitými výsledky.

Způsoby zápisu algoritmů:

1. Metoda slovního záznamu

Verbální způsob zápisu algoritmů je popisem po sobě jdoucích fází zpracování dat. Algoritmus je specifikován v libovolné prezentaci v přirozeném jazyce .

Příklad

Jako příklad verbálního způsobu psaní algoritmu zvažte algoritmus pro nalezení oblasti obdélníku

kde S je plocha obdélníku; a, b – délky jeho stran.

Je zřejmé, že a, b musí být specifikovány předem, jinak nelze problém vyřešit.

Způsoby psaní algoritmů

Verbální způsob zápisu algoritmu vypadá takto:

• Začátek algoritmu.
• Nastavte číselnou hodnotu strany a.
• Nastavte číselnou hodnotu strany b.
• Vypočítejte plochu S obdélníku pomocí vzorce S=a*b.
• Výstup výsledku výpočtů.
• Konec algoritmu.

Způsoby psaní algoritmů

2. Grafická metoda

Při grafickém znázornění je algoritmus znázorněn jako sekvence vzájemně propojených funkčních bloků, z nichž každý odpovídá provedení jedné nebo více akcí.

Toto grafické znázornění se nazývá vývojový diagram nebo vývojový diagram. Ve vývojovém diagramu každý typ akce (zadání počátečních dat, výpočet hodnot výrazů, kontrola podmínek, řízení opakování akcí, dokončení zpracování atd.) odpovídá geometrickému obrazci reprezentovanému jako symbol bloku. Symboly bloků jsou propojeny přechodovými čarami, které určují pořadí, ve kterém se akce provádějí. Níže jsou uvedeny nejčastěji používané symboly.

Způsoby psaní algoritmů

Prvek vývojového diagramu

název

Výpočetní blok (výpočetní blok)

Výpočetní akce nebo sekvence akcí

Logický blok (blok podmínek)

Blok pro vstup/výstup dat

Volba směru provádění algoritmu v závislosti na nějaké podmínce

Obecné označení pro vstup (výstup) dat (bez ohledu na fyzické médium)

Začátek (konec)

Začátek nebo konec algoritmu, vstup nebo výstup v podprogramu

Způsoby psaní algoritmů

Prvek vývojového diagramu

název

Uživatelský proces (podprogram)

Výpočet pomocí standardního programu nebo podprogramu

Modifikační blok

Funkce provádí akce, které mění body (například záhlaví smyčky) algoritmu

Konektor

Označení spojení přerušovanými čarami mezi informačními toky

Způsoby psaní algoritmů

Příklad

Algoritmus pro výpočet plochy obdélníku

Způsoby psaní algoritmů

3. Pseudokódy

poloformalizované popisy algoritmů v podmíněném algoritmickém jazyce, včetně prvků programovacího jazyka a frází v přirozeném jazyce, obecně přijímané matematické zápisy atd.

Neexistuje jediná nebo formální definice pseudokódu, takže jsou možné různé pseudokódy, lišící se množinou funkčních slov a základních (základních) konstrukcí.

Způsoby psaní algoritmů

Příklad

• Start. Přejděte k bodu 2.
• Zadání čísel a a b. Přejděte na bod 3.
• Vypočítejte S=a*b. Přejděte na bod 4.
• Závěr S. Přejděte na krok 5.
• Konec.

Způsoby psaní algoritmů

4. Softwarová metoda

Záznam algoritmu ve zvoleném programovacím jazyce.

Příklad

Writeln('');

Writeln(‘S=‘ , S);

Typy algoritmů

1. Lineární algoritmus

Toto je algoritmus, ve kterém existuje pouze následující struktura.

Následující- Toto je uspořádání akcí jedna po druhé.

Typy algoritmů

2. Algoritmus větvení (pokud... pak... jinak...)

Jedná se o algoritmus, který má větvenou strukturu.

Větvení- jde o volbu akce v závislosti na splnění nějaké podmínky.

Typy algoritmů

3. Cyklický algoritmus

Jedná se o algoritmus, který má strukturu smyčky.

Cyklus- Toto je opakované opakování jakékoli akce.

Typy algoritmů

4. Kombinovaný algoritmus

Algoritmus, který obsahuje několik struktur současně.

Šířka bloku px

Zkopírujte tento kód a vložte jej na svůj web

Popisky snímků:

Algoritmy a datové struktury Literatura:

• D. Knut. Umění počítačového programování. T. 1-3, M.: Mir, 1978, 1995 atd.
• N. Wirth. Algoritmy a datové struktury. M.: Mir, 1989.

Koncept datového typu

• Informace který musí být zpracován na počítači je abstrakce, zobrazující nějaký fragment skutečného světa. Konkrétně fragment, který je předmětem řešeného problému. Abychom to vyřešili, nejprve zkonstruujeme informační a v obecném případě matematický Modelka studoval předmětová oblast a vybere se stávající nebo se postaví nový algoritmusřešení problému.

• Informace vždy se zhmotňuje, je zastoupena ve tvaru zprávy. Obecně platí, že zpráva představuje nějaké registrovaný fyzický signál . Signál- Tento změna v čase nebo prostoru nějakého objektu, zejména parametr nějaké fyzikální veličiny, například indukce magnetického pole (při ukládání informace, přesněji zprávy na magnetických médiích) nebo úroveň napětí v elektrickém obvodu (v procesorových čipech nebo RAM).

• Oddělený zpráva je sekvence znamení(hodnoty signálu) od některých finále abeceda(konečná množina hodnot parametrů signálu), zejména pro počítač posloupnost znaků binární abecedy, tedy posloupnost bitů.

• Počítačová data jedná se o diskrétní zprávy, které jsou prezentovány ve formě použitelné pro počítač, počítačově srozumitelné. Pro počítačový procesor jsou jakákoli data nestrukturované posloupnost bitů (někdy se používá termín tok bity).

• Konkrétní interpretace této sekvence závisí na programu, na prezentační formuláře a datové struktury, které jsou vybrány programátor. Tato volba nakonec závisí na řešeném problému a pohodlnosti provádění akcí s daty.

• Bezprostřední významy Tento neměnný programové objekty, které se reprezentují: čísla (25, 1.34E-20), symboly ('A', '!'), řetězce ('Zadejte prvky matice');
• Konstanty jsou jména přiřazená určitým hodnotám (const pi=3,1415926).
• Proměnné to jsou objekty, které mohou převzít hodnotu, uložit ji beze změny a změnit ji při provádění určitých akcí (var k:integer, x:real, a:array).
• Hodnoty výrazů a funkcí. Výrazy a funkce jsou pravidla pro výpočet hodnot zapsaných určitým způsobem: k*x+ sqrt(x).

• Data v programech zahrnují:

• Datový typ je nejdůležitější charakteristikou, která určuje:

• sada platných hodnot;
• mnoho operací, které lze provést s hodnotou;
• hodnotová struktura (skalární, vektorová atd.);
• metoda strojové reprezentace významu.

• K zobrazení vlastností počítačové reprezentace dat různé povahy v informatice využívají počítačové obory to nejdůležitější koncept datového typu.

• Typ konstanty, proměnné nebo výrazu lze určit pomocí vzhled(z obrázku) nebo z popisu bez provedení jakýchkoliv výpočtů.
• Jakákoli operace nebo funkce vyžaduje argumenty a vrací výsledek velmi specifického typu. Typy argumentů a výsledky operací jsou určeny podle dobře definovaných pravidel jazyka.

• Základní principy konceptu datových typů
• v programovacích jazycích:

• Varianty datových typů a struktur

• Informatika používá velké množství různých typy, rozličný datové struktury, které se používají pro modelování objekty, se kterými se setkáváme v uvažovaných problémech.

• Pokud se struktura daného algoritmu během provádění nezmění, je taková struktura uvažována statický , Statické datové struktury existovat beze změny během celou dobu provádění algoritmu.

• Význam skalární(jednoduché, atomové) prezentovaný typ hladký jeden složka (příklad: čas, teplota).

• Dynamické struktury jsou vytvářeny, upravovány a ničeny podle potřeby kdykoli během provádění algoritmu.

• Význam strukturovaný(složený) prezentovaný typ více jak jeden komponenta (příklad: vektor, matice, tabulka atd.).

• Existují předdefinované (předdefinované) - standardní a programově definované typy. Pro Standard typy v popisu programovacího jazyka definují všechny jeho charakteristiky - množinu hodnot, množinu operací, strukturu a strojovou reprezentaci hodnoty. Pro nově definované typů, jazyk poskytuje mechanismus pro specifikaci sady hodnot v programu a strukturu hodnoty. Obvykle se staví nový typ na základě stávajících standardních. Proto je mnoho operací a strojové znázornění takových typů pevně stanoveno v popisu jazyka.

• skalární (jednoduché, atomové) typy:
• Celý;
• nemovitý;
• logický (booleovský);
• symbolický;
• strukturované (kompozitní) typy:
• pole;
• záznam;
• soubor (sekvence);
• hromada;
• objekt (třída) typ;
• všechny možné kombinace skalárních a strukturovaných typů;
• referenční typ.

• Statické typy (datové struktury)

• Nejčastěji používané předdefinované skalární typy jsou: integer ( celé číslo), skutečný ( nemovitý), symbolický ( char), booleovský ( booleovský).

• Přesné celočíselné hodnoty. Příklady: 73, -98, 5, 19674.
• Zobrazení stroje: formát s pevnou čárkou. Rozsah hodnot je určen délkou pole. Operace: +, -, *, div, mod,=,<, и т.д.

• Typ celé číslo

• Neceločíselné aproximace. Příklady: 0,195, -91,84, 5,0
• Strojová reprezentace: formát s plovoucí desetinnou čárkou. Rozsah a přesnost hodnot je určena délkou pole. Operace: +, -, *, /, =,<, и т.д.

• Typ nemovitý

• Jednotlivé textové znaky. Příklady: 'a', '!', '5'.
• Reprezentace stroje: formát ASCII. Sada hodnot je určena tabulkou kódů a možnostmi klávesnice. Operace: +, =,<, и т.д.

• Typ char

• Dvě booleovské hodnoty false a true. Navíc falešné
• Reprezentace stroje ─ nula a jedna bitová hodnota: false je zakódováno 0, pravda ─ 1. Operace: , , , =,< и т.д.

• Typ booleovský

• Základní mechanismy pro konstrukci nových skalárních diskrétních typů: výčet, omezení. V definici přenosný typů, seznam všech možných hodnot je pevně daný, mnoho operací je definováno předem v jazyce. V definici omezený typů, protože sada platných hodnot je pevná podmnožina množina hodnot nějakého diskrétního typu, který se v tomto případě nazývá základní typ ve vztahu k definovanému.

• Existují diskrétní a spojité skalární typy. Více významů oddělený zadejte konečný nebo spočetný. Více významů kontinuální více než počitatelný typ. Mezi diskrétní standardní typy patří celočíselné, znakové a logické. Průběžné standardní typy zahrnují skutečné.

• Strukturované (složené) typy se vyznačují: počtem a možným typem hodnotových složek a také způsobem, jakým se přistupuje k jednotlivé hodnotové složce.

• Obvykle se nazývají struktury podobné vektorům a maticím v informatice pole. Všechny prvky pole musí být Jeden a ten samý typ.

• Pole nebo běžný typ

• Pro přístup (odkaz na) k jednotlivému prvku pole se používá index nebo několik indexů (w; w; A). Indexy mohou být výrazy, jejichž hodnoty se mohou libovolně měnit v rámci předem definovaných limitů. Proto říkají, že prvky pole mají přímý přístup.

• Volají se struktury podobné řádkům tabulky evidence. Složky záznamů se obvykle nazývají pole. Mohou být různá pole (sloupce tabulky). odlišný typy. Pro přístup k jednotlivým polím záznamu jsou pevná a neměnná jména. Například: Den vítězství. Měsíc:= květen. Pole lze vybrat ke zpracování v libovolném pořadí, takže se říká, že přístup ke komponentám záznamu je rovný.

• Záznam nebo kombinovaný typ

• Den vítězství:

• Soubor (sekvence)

• Hlavní datová struktura, která slouží k ukládání informací na externích zařízeních (magnetické disky, pásky atd.), je soubory nebo sekvence. Soubor je považován za vždy na externím zařízení. V tomto případě je počet součástí souboru neznámý, všechny součásti musí být stejného typu. Přístup ke komponentám ─ konzistentní.

• Gagarinův let:

• hromada

• V mnoha matematických a informačních problémech je potřeba přímo nebo nepřímo použít hlavní matematický objekt sady. Datový typ odpovídající množině je z definice strukturovaný, protože v obecném případě může množina sestávat z více než jednoho prvku a zároveň musí být operace prováděny se všemi prvky množiny jako s jedním celkem. Počet prvků v sadě není předem určen a v průběhu času se může měnit. Všechny prvky sady musí být stejného typu. Přístup k jednotlivým prvkům sestavy Ne. Můžete pouze zjistit, zda prvek patří do množiny či nikoli, zařadit prvek do množiny nebo jej z množiny vyloučit. K dispozici jsou také standardní operace na množinách: sjednocení, průnik, odčítání atd.

• X1 X5 X4

• Dynamické datové struktury

• Data s dynamickou strukturou v čase Změny sebe struktura a nejen počet prvků, jako jsou soubory nebo sekvence. Základní dynamické datové struktury jsou:

• objekt;
• lineární seznam;
• strom;
• graf.

• V lineárním seznamu se každý prvek vztahuje k prvku před ním. U lineárního seznamu víme, který prvek je na začátku seznamu, který je na konci a také, který prvek je před aktuálním. V lineárním seznamu se můžete přesunout z aktuálního prvku na další pouze pomocí zadaných spojení mezi sousedními prvky.

• Lineární seznam

• Obecně se získá řetězec prvků, ve kterém můžete vyhledávat, do kterého můžete prvky vkládat nebo je vyloučit.

• Mnoho dalších typů dynamických struktur je organizováno na základě lineárního seznamu. Jedná se zejména o: kroužky, fronty, paluby A hromady.

• Prstencová struktura

• Rozdíl mezi kruhovým a lineárním seznamem je v tom, že kruh má spojení mezi posledním prvkem seznamu a jeho prvním prvkem.

• Pro lineární seznam a kruh je možný přístup k jakémukoli prvku struktury. Chcete-li to provést, musíte postupně přejít z jednoho prvku do druhého. V mnoha situacích reálného světa takový přístup nepřítomný. Můžete interagovat pouze s prvním a posledním prvkem nebo pouze s jedním z nich. K modelování takových objektů se používají fronty, balíčky a hromádky.

• Struktura fronty

• Konec fronty je k dispozici pro zahrnutí a začátek je k dispozici pro vyloučení (výběr). Prvek, který dorazil do fronty dříve a je obsluhován jako první. Říká se, že fronta je struktura s disciplínou obsluhy FIFO (F první já n, F první Ó ut) ─ „kdo dřív přijde, ten dřív odejde“.

• Struktura paluby

• Balíček má k dispozici oba konce, jak pro zahrnutí, tak pro odběr vzorků. Můžeme tedy říci, že prosinec ─ je obousměrná fronta.

• Stack struktura

• Zásobník má k dispozici pro interakci pouze jeden konec struktury: horní část zásobníku. Jak zahrnutí nového prvku do zásobníku, tak výběr posledního dříve zahrnutého prvku prochází horní částí zásobníku. Položka, která dorazila jako poslední, je tedy zpracována jako první. Říká se, že zásobník je struktura s disciplínou údržby LIFO (L ast já n, F první Ó ut) ─ „poslední přijde, první odchází“.

• DĚKUJI ZA POZORNOST!

Základní struktury algoritmů Uveďme některá omezení
struktura vývojového diagramu.
Sestavíme algoritmus pouze pomocí
tři fragmenty jisté
konfigurace.
Říkejme jim základní struktury
algoritmy.

První základní struktura je následující
sestává z řetězce bloků bez
důsledky.

Větvení

Ano
Ne
stav

Zvláštní případ větvení
stav

Větvení se používá v případech, kdy
když si potřebujete jednu vybrat
dva způsoby, jak problém vyřešit.

Cyklus

Cyklus se používá v případech, kdy
k vyřešení problému je to nutné
opakovat stejné věci znovu a znovu
akce.

Smyčka s dodatečnou podmínkou

Smyčka s předpokladem

Parametrický cyklus

Řízený parametrický cyklus
parametr.
Parametr smyčky je proměnná
který se v cyklu monotónně mění,
a na tom závisí výstupní kritérium
cyklus.

i:= in
Tělo
cyklus
i:= i + di
Ne
Ano
i > ik

i:=in
i>ik
Tělo
cyklus
i:=i+di

Navrhování komplexních algoritmů

Metoda návrhu algoritmu shora dolů

Metoda se skládá z následujících kroků:
původní úkol je rozdělen na dílčí úkoly,
propojeno nějakým algoritmem;
tento algoritmus se ladí;
každý dílčí úkol je považován za
úkol;
proces pokračuje až do
původní úkol nebude úplně
vyřešeno.

Příklad

Je dána rovnice ax2 + bx + c = 0 a funkce
f(x).
Pokud má rovnice dvě reálné hodnoty
kořeny x1 a x2, vytvořte tabulku hodnot
funkce na segmentu sestávajícím z n
body.

Algoritmus nejvyšší úrovně
Vstup a,b,c
Řešení
rovnic
Ne
x1, x2
nalezeno
Ano
Zadejte n
Konstrukce
tabulky
Neexistuje žádné rozhodnutí
STOP

Algoritmus, který implementuje dílčí problém řešení
kvadratická rovnice
d:=b2 – 4ac
Ne
D>0
Ano
X1 = (- b + √ d)/2/a
X2= (- b - √ d)/2/a

Algoritmus pro konstrukci tabulky hodnot
funkcí
h=(x2-x1)/(n-1)
x = x1
i=1
Výstup x, f(x)
x=x+h
i = i +1
Ano
Ne
i>n

Tedy řešení problému
problém se skládá z horního algoritmu
úroveň a dva dílčí úkoly.
Algoritmus propojování dílčích úkolů
Řešení
rovnic
Konstrukce
tabulky f(x)