Workshop o řešení úloh na počítači: Vzdělávací a metodická příručka. Workshop řešení úloh na počítači: Vzdělávací a metodická příručka Základní algoritmy na grafech
(Dokument)
n1.doc
Ministerstvo školství Ruské federace
STÁTNÍ TECHNICKÁ UNIVERZITA NOVOSIBIRSK
Workshop na počítači
ALGORITHMY
Schváleno redakční a vydavatelskou radou univerzity
jako učební pomůcka
pro studenty prvního ročníku FPMiI
(směr 510200 – Aplikovaná matematika
a informatika, obor 351500 –
Software a administrace
informační systémy) prezenční vzdělávání
Novosibirsk
2004
T. A. Shaposhnikovová, Umění. učitel
Recenzenti: S .X. Royak, Ph.D. tech. vědy, docent,
L.V. tyunina, Ph.D. tech. vědy, docent
Práce byla zpracována na Katedře aplikované matematiky
Workshop na počítači. Algoritmy
P 691 Učebnice / V.P. Khitsenko, T.A. Šapošnikovová. – Novosibirsk: Nakladatelství NSTU, 2004. – 112 s.
Za hlavní algoritmy probrané v kurzu „Dílna na počítači“ jsou považovány: grafové algoritmy, kombinatorické algoritmy, algoritmy vyčerpávajícího vyhledávání. Pro ilustraci teoretického materiálu je uvedeno mnoho příkladů.
MDT 004.421+519.1](075.8)
Stát Novosibirsk
Technická univerzita, 2004
obsah
Kurz „Dílna na počítači“ je první základní disciplínou mezi programátorskými disciplínami. Bez znalosti nejdůležitějších a nejznámějších algoritmů nemůžete ovládat programování. Tento tutoriál podrobně pojednává o algoritmech, které se široce používají při řešení různých tříd problémů: základní grafové algoritmy, vyčerpávající vyhledávací algoritmus a metody jeho zdokonalování (algoritmy dynamického programování, „chamtivý“ algoritmus, metoda větvení a vazeb), algoritmy pro generování základních kombinatorických objektů.
Učebnice je určena nejen studentům, kteří studují počáteční části programování, ale také těm, kteří si chtějí obohatit své dovednosti v konstruování algoritmů (místo „vynalézání dalšího kola“). Rozdíl mezi špatnými a dobrými algoritmy je často významnější než mezi rychlými a pomalými počítači. Například chceme seřadit pole milionů čísel. Co je rychlejší - řazení vkládání na superpočítači (100 milionů operací za sekundu) nebo slučování na domácím počítači (1 milion operací)? Navíc, pokud je řazení vložení napsáno v jazyce symbolických instrukcí extrémně ekonomicky, pro řazení n potřebujete přibližně 2 čísla n 2 operace. Současně je slučovací algoritmus napsán bez velkého zájmu o efektivitu a vyžaduje 50 n log n operace. V prvním případě k seřazení 1 milionu čísel dostaneme:
pro super počítač:
pro domácí počítač:
To ukazuje, že vývoj efektivních algoritmů není o nic méně důležitý než vývoj rychlé elektroniky.
Učebnice doplňuje přednáškový a praktický materiál oboru „Praktikum na počítači“ a je zaměřena především na podporu samostatné práce studentů při provádění RGR a ročníkových prací. Proto je každý algoritmus prezentovaný v učebnici analyzován na praktickém příkladu, u některých je uvedena softwarová implementace v programovacím jazyce (C). U algoritmů jsou také uvedeny odhady jejich složitosti.
Algoritmy jsou psány ve formě „pseudokódu“, komentovány v textu a přehledně prezentovány v obrázcích a tabulkách.
1. Základní algoritmy na grafech
Matematické modely velkého množství problémů lze popsat pomocí teorie grafů, proto jsou velmi důležité algoritmy pro studium struktury (zpracování) grafů a také metody pro jejich reprezentaci.
1.1. Některé základní definice
Graf (neorientovaný graf) G(PROTI, E) je sbírka dvou sad, kde PROTI je konečná neprázdná množina prvků zvaných vrcholy a E– soubor neuspořádaných dvojic různých prvků souboru PROTI(tyto dvojice se nazývají hrany). Nazývá se graf skládající se z jednoho vrcholu triviální.
Říká se, že žebro E = (u, proti) spojuje vrcholy u A proti. Okraj E a vrchol u (a E A proti) jsou nazývány vedlejší a vrcholy u A proti – přilehlý. Také se nazývají hrany spadající do stejného vrcholu přilehlý.
Nejvyšší stupeň je počet hran, které k němu přiléhají. Vrchol grafu, který má stupeň 0, se nazývá izolovaný a mající stupeň 1, – závěsný.
Li E není množina, ale kolekce obsahující několik stejných prvků, pak se tyto prvky nazývají více hran a graf – multigraf.
Pokud prvek množiny E může existovat dvojice identických (nikoli různých) prvků PROTI, pak takový prvek E nazývaná smyčka. Pseudograf je graf, ve kterém jsou spolu s více hranami povoleny také smyčky a dokonce i několik smyček v jednom vrcholu.
Graf se nazývá jednoduchý, pokud je jakákoliv dvojice vrcholů spojena nejvýše jednou hranou a graf nemá žádné smyčky.
Trasa (cesta) je střídavá sekvence
a = v 0 , E 1 , proti 1 , E 2 , ..., vn – 1 , e n,v n =b
Vrcholy a hrany grafu jsou takové, že E i = (proti já- 1 , proti i), 1 ? i ? n. Říká se, že trasa spojuje vrcholy A A b– konce trasy. V jednoduchém grafu lze trasu specifikovat uvedením pouze jejích vrcholů A = proti 0 , proti 1 , …, proti n = b nebo jeho žebra E 1 , E 2 , …, E n .
Trasa se nazývá řetěz, pokud jsou všechny jeho okraje odlišné. Trasa se nazývá ZAVŘENO, Pokud proti 0 = proti n .
Uzavřený okruh se nazývá cyklus. Řetěz se nazývá jednoduchý, pokud neobsahuje shodné vrcholy. Nazývá se jednoduchý uzavřený okruh jednoduchý cyklus.
Hamiltonův řetěz je jednoduchý řetězec obsahující všechny vrcholy grafu. Hamiltonovský cyklus nazýváme jednoduchý cyklus obsahující všechny vrcholy grafu.
Vrchol u dosažitelný z vrchu proti, pokud existuje cesta z proti PROTI u.
Délka cesty proti 0 , proti 1 , …, proti n rovný počtu jeho hran, tzn. n.
Vzdálenost mezi dvěma vrcholy je délka nejkratší cesty spojující tyto vrcholy.
Část grafu G(PROTI, E) - to je takový graf G"(PROTI", E"), Co PROTI" PROTI A E" E.
Podgraf graf G tato část se nazývá G" , který spolu s libovolnou dvojicí vrcholů ty,proti obsahuje hranu (u, proti) , pokud je v G.
Doplněk graf G nazval graf G" se stejnou množinou vrcholů jako G, a dva různé vrcholy sousedí v G" právě tehdy, když spolu nesousedí G. Okraje grafu G A G" dohromady tvoří plný graf. Graf se nazývá kompletní, pokud jsou libovolné dva jeho vrcholy sousední.
Dva počty G 1 a G 2 jsou izomorfní, pokud existuje zobrazení množiny vrcholů grafu jedna ku jedné G 1 na sadu vrcholů grafu G 2, zachování spojitosti.
Graf se nazývá koherentní, pokud pro kterýkoli pár vrcholů existuje cesta, která je spojuje. Maximální souvislý podgraf nesouvislého grafu se nazývá připojený komponent tohoto grafu.
Pokud je funkce zadána F: PROTI?M, pak sadu M se nazývá sada štítků a graf je výrazný. Pokud je funkce zadána F: E?M, tj. okrajem grafu jsou přiřazeny váhy, pak je graf volán vážený.
Hrana grafu se nazývá orientované, pokud je důležité pořadí jeho konců. Nazýváme graf, jehož hrany jsou všechny orientované orientované počítat (resp digraf). V tomto případě prvky sady PROTI jsou nazývány uzly a prvky sady E – oblouky. Oblouk (u, proti) vede z vrcholu u na vrchol proti, Horní proti zvaný nástupce apexu u, A ty – předchůdce summitu proti. Koncepty části digrafu, cesta, vzdálenost, jednoduchá a uzavřená cesta, cyklus jsou určeny pro digraf stejným způsobem jako pro graf, ale s přihlédnutím k orientaci oblouků.
Zdroj digrafu je vrchol, ze kterého jsou dosažitelné všechny ostatní vrcholy. Digraph odtok je vrchol, který je dosažitelný ze všech ostatních vrcholů.
strom nazýváme souvislý graf bez cyklů.
kořenový strom je souvislý digraf bez cyklů, který splňuje podmínky:
existuje jediný vrchol, nazývaný kořen, který neobsahuje žádný oblouk;
jeden oblouk vede ke každému nekořenovému vrcholu.
1.2. Reprezentace grafů v počítači
Reprezentace objektů matematického modelu v programu je důležitou součástí programování. Výběr nejlepší reprezentace je dán požadavky konkrétního úkolu. Existují různé způsoby, jak znázornit grafy v paměti počítače. Liší se velikostí paměti, kterou zabírají, a rychlostí provádění operací s grafy. Je třeba poznamenat, že v mnoha problémech s grafy je volba reprezentace rozhodující pro účinnost algoritmů. Na Obr. 1.1 pro nepřímé ( abeceda) a orientované ( d, f, g, h) grafy ukazují různé reprezentace: b, f- matice sousednosti; c, g– matice výskytu; G– seznam sousedství neorientovaného grafu se sousedním umístěním prvků seznamu; h– seznam sousedství orientovaného grafu se souvislým uspořádáním prvků seznamu.
1.2.1. Matice sousedství grafu
Matice sousedství označeného grafu s n vrcholy je matice A = [ A ij ], i, j = 1, 2, ..., n, kde
Matice sousedství jednoznačně definuje graf (obr. 1.1, a–c, d–f). Pro neorientovaný graf je matice A symetrická vzhledem k hlavní diagonále. Počet jedniček v řádku se rovná stupni odpovídajícího vrcholu. Smyčka v matici sousednosti může být reprezentována odpovídajícím jednotkovým diagonálním prvkem. Více hran lze reprezentovat tak, že prvek matice bude větší než 1.
Výhodou tohoto zobrazení je „přímý přístup“ k okrajům grafu, tzn. je možné získat odpověď na otázku "je v grafu hrana v jednom kroku?" (X, y) ? U malých grafů, kdy je dostatek místa v paměti, je často snazší pracovat s maticí sousednosti. Nevýhodou je, že bez ohledu na počet hran je paměťová stopa n n nebo n n/2 – n, pokud použijete symetrii a uložíte pouze trojúhelníkovou podmatici matice sousednosti. Navíc stačí reprezentovat každý prvek matice jednou binární číslicí.
1.2.2. Graf Incidence Matrix
Incidenční matice je matice B = [ b ij ], i = 1, 2, ..., n, j = 1, 2, ..., m(Kde n je počet vrcholů a m – počet hran grafu), jejichž řádky odpovídají vrcholům a sloupce – hranám. Prvek matice v neorientovaném grafu je:
V případě orientovaného grafu s n vrcholy a m oblouky, prvek matice dopadu se rovná:
Řádky matice také odpovídají vrcholům a sloupce obloukům.
Incidenční matice jednoznačně určuje strukturu grafu (obr. 1.1, A–PROTI,d–f). Každý sloupec matice B obsahuje právě dvě jedničky. Neexistují žádné stejné sloupce.
Nevýhodou tohoto nápadu je, že vyžaduje n m paměťové jednotky, z nichž většinu zaberou nuly. Přístup k informacím není vždy pohodlný. Chcete-li například odpovědět na otázky „je v grafu oblouk? (X, y) ? nebo „do kterých vrcholů vedou hrany z vrcholu X? Může být nutné opakovat všechny sloupce matice.
1.2.3. Hmotnostní matice grafu
Jednoduchý vážený graf může být reprezentován jeho váhovou maticí W = [ w ij], kde w ij– váha hrany spojující vrcholy i, j = 1,2, ..., m. Jsou váhy neexistujících hran stejné? nebo 0 v závislosti na úkolu. Hmotnostní matice je jednoduché zobecnění matice sousednosti.
1.2.4. Seznam hran grafu
Při popisu grafu seznamem jeho hran (nebo u digrafů seznamem oblouků) je každá hrana reprezentována dvojicí vrcholů, které k ní přiléhají. Tato reprezentace může být implementována se dvěma poli (nebo jedním dvourozměrným):
x =(X 0 , X 1 , ..., x m) A y = (y 0 , y 1 , ..., y m),
Kde m –– počet hran v grafu. Každý prvek v poli je štítek vrcholu a i-E okraj grafu opouští vrchol X i a vstupuje na vrchol y i. Velikost obsazené paměti je v tomto případě 2 m paměťové jednotky. Nevýhodou je velký počet kroků nutných k získání množiny vrcholů, do kterých vedou hrany z daného vrcholu.
1.2.5. Seznamy sousedních vrcholů grafu
Graf může být jednoznačně reprezentován strukturou sousedství jeho vrcholů. Struktura sousedství se skládá ze seznamů Adj [ X] vrcholy grafu sousedící s vrcholem X. Seznamy úprav [ X] jsou sestaveny pro každý vrchol grafu. Struktura sousedství je vhodně implementována polem n(počet vrcholů v grafu)
lineárně propojené seznamy (1.1, inzerát). Každý seznam obsahuje 
A d
| 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 |
|||
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
|
| 2 | 1 | 0 | 1 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
|
| 3 | 1 | 1 | 0 | 1 | 1 | 3 | 0 | 0 | 0 | 0 | 0 |
|
| 4 | 0 | 0 | 1 | 0 | 1 | 4 | 1 | 1 | 0 | 0 | 0 |
|
| 5 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 0 | 0 | 1 | 0 |
b E
| Ѕ | 1/3 | 1/5 | 2/3 | 3/4 | 3/5 | 4/5 | Ѕ | 1/3 | 4/1 | 4/2 | 5/4 |
|||
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | -1 | 0 | 0 |
|
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 2 | -1 | 0 | 0 | -1 | 0 |
|
| 3 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 3 | 0 | -1 | 0 | 0 | 0 |
|
| 4 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 4 | 0 | 0 | 1 | 1 | -1 |
|
| 5 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 5 | 0 | 0 | 0 | 0 | 1 |
PROTI a
G h
Rýže. 1.1
Vrcholy sousedící s vrcholem, pro který se seznam sestavuje. Seznam sousedních vrcholů v grafu poskytuje kompaktní reprezentaci pro řídké grafy – ty, jejichž sada hran je mnohem menší než sada vrcholů. Nevýhodou této reprezentace je, že pokud chceme vědět, zda má graf hranu ( X, y), musíte si prohlédnout celý Seznam úprav [ X] v hledání y. Množství požadované paměti je pro orientaci n+ m A n+2 m pro neorientované grafy paměťových jednotek, kde n je počet vrcholů grafu a m– počet hran (oblouků) grafu. Pokud je algoritmus pro řešení problému založen na operacích přidávání a odebírání vrcholů ze seznamů, pak je vhodné implementovat ukládání seznamů sousedství pomocí propojené reprezentace seznamů (1.1, d–h).
1.3. Procházení grafu
Procházení grafu je nějaké systematické procházení jeho vrcholů (a/nebo hran). Při procházení grafu se pohybujeme po hranách (obloucích) a procházíme všemi vrcholy. V tomto případě lze získat mnoho informací nezbytných pro další zpracování grafu, takže procházení grafu je základem mnoha algoritmů pro studium struktury grafu. Pokud se struktura grafu při návštěvě vrcholu nezmění, pak jsou nejužitečnější dvě hlavní metody procházení: procházení do hloubky a procházení do šířky.
1.3.1. Procházení do hloubky (nebo vyhledávání)
Nechť je dán graf a fixován počáteční vrchol s(původní graf může být neorientovaný nebo řízený). Strategie prohledávání nejprve do hloubky je začít od počátečního vrcholu, jít „do hloubky“ tak dlouho, jak je to možné (jsou zde nepřekonané odchozí hrany) a vrátit se a hledat jinou cestu, když žádné takové hrany nejsou. To se provádí, dokud nejsou nalezeny všechny vrcholy dosažitelné z původního. Pokud po tomto stále existují nedetekované vrcholy, vybere se jeden z nich (jako počáteční) a proces se opakuje. Dělejte to, dokud nenajdeme všechny vrcholy grafu.
Když při hledání poprvé najdeme vrchol proti, sousedící s vrcholem u, tato událost se musí oslavit. Algoritmus prohledávání do hloubky k tomu používá barvy (označení) vrcholů. Každý z vrcholů je zpočátku bílý (neprochází se). Jakmile je detekován, zešedne. Když byl vrchol kompletně zpracován (to znamená, když byl naskenován seznam sousedních vrcholů), zčerná. Během procesu hledání je tedy z grafu vybrána část – „strom hledání prvního do hloubky“ nebo několik stromů (les hledání prvního místa hloubky), pokud se hledání opakuje z několika vrcholů. Každý vrchol spadá přesně do jednoho vyhledávacího stromu v hloubce, takže se tyto stromy neprotínají. Kromě toho můžete na vrcholy stromu umístit další značky: značku, kdy byl vrchol objeven (zešedivěl), a značku, kdy bylo dokončeno zpracování seznamu sousedních uzlů. u vrcholy (a u zčernala).
Algoritmus níže používá znázornění grafu seznamy sousedních vrcholů Adj [ u]. Pro každý vrchol u
Sloupec navíc ukládá svou barvu Mark[ u] a jeho předchůdce Pr[ u]. Pokud neexistuje žádný předchůdce (např u =
s nebo u
dosud neobjeveno), pak Pr[ u] = nula. Navíc v d[ u] A
F[ u] jsou zaznamenány další u tagy: časová razítka. V d[ u] zaznamenává čas, kdy vrchol u byl detekován (a zešedl) a v f[ u] zaznamenává čas při zpracování seznamu sousedních u vrcholy (a u zčernala). V níže uvedeném algoritmu jsou časová razítka d[ u] A
F[ u] jsou celá čísla od 1 do 2| PROTI|; pro jakýkoli vrchol u platí následující nerovnost: d [ u]u]. Vrchol u bude bílá až do okamžiku d [ u], šedá mezi d [ u] af [ u] a černá po f [ u]. Algoritmus používá rekurzi, aby se podíval na všechny sousední
u vrcholy
Search_in_depth ( G)
2 pro (každý vrchol u PROTI[G])
4 Pr [ u] ?nula;
7 pro (každý vrchol s PROTI[G])
Vyhledávání ( u)
3d [ u] ?čas?čas+1;
4 za (každý proti Úprava [ u])
5 ( pokud (označte [ proti] = BÍLÁ)
6 ( Pr [ proti] ?u; Vyhledávání ( proti); }
9 f[ u]? čas?čas+1;
10 }
Algoritmus začíná tím, že nejprve (řádky 2–5) vybarví všechny vrcholy bílou barvou (označené jako neprošlé); v poli Pr je umístěno nula(pokud vrcholy nemají předchůdce). Poté (řádek 6) se nastaví počáteční (nulový) čas (časová proměnná je globální proměnná). Pro všechny vrcholy (řádky 7–8), které ještě nejsou projeté (bílé), se volá procedura Search. Tyto vrcholy se stávají kořeny hloubkových vyhledávacích stromů.
V době volání Vyhledávání ( u) horní u– bílá. V proceduře Hledat okamžitě zešedne (řádek 2). Čas jeho detekce (řádek 3) se zadává v d[ u] (počítadlo času se předtím zvýšilo o jedničku). Pak to vypadá (řádky 4–7) vedle sebe u topy; pro ty z nich, které se v době volání ukážou jako bílé, je vyvolána procedura Vyhledávání. Po zhlédnutí všech souvisejících u vrcholy úplně nahoře u udělejte to černé a napište to do f [ u] čas této události.
reklamy
Soutěž 1: Python (v libovolném úkolu)
nudná knihovna. Vektorizace výpočtů.
Důležité články o nudné dokumentaci:
Soutěž 2: Numpy (v libovolném úkolu)
Organizace kódu v Pythonu.
Funkce, moduly, třídy.
Soutěž 3: Třídy (v libovolném úkolu)
Metody metrické klasifikace.
Diskuse k prvnímu praktickému úkolu.
Úvod do zpracování obrazu.
Vizualizace v Pythonu.
Příprava textových zpráv. systém TeX.
Zpracování výjimek. Kontextové manažery. Testování.
Příprava krátkých projevů.
Iterátory a generátory.
Požadavky na zprávy o praktických úkolech
Zpráva musí být samostatný dokument ve formátu PDF připravený v systému LATEX. Studenti, kteří dobře zvládli minulé úkoly, mají možnost předkládat zprávy ve formátu HTML nebo PDF připravené pomocí notebooku Jupyter.
Zpráva by měla inspektorovi poskytnout odpovědi na následující otázky:
- Na jaký kurz se zadání vztahuje?
- Jaký úkol byl splněn?
- Kdo splnil úkol?
- Jaký byl úkol?
- co se udělalo? Co se neudělalo?
- Byly uvedeny správné odpovědi na všechny teoretické otázky v zadání?
- Byly provedeny všechny potřebné experimenty? Bylo dosaženo smysluplných ZÁVĚRŮ?
- Byla kreativní část úkolu dokončena?
- Získal student nějakou pomoc? Pokud ano, tak do jaké míry?
- Jakou literaturu student použil?
Některé prvky dobré zprávy:
- Objem zprávy: 5--20 stran;
- V textu zprávy se neopakuje úplná formulace zadání;
- Struktura zprávy odpovídá bodům zadání;
- Používají se vektorová písma;
- Plány jsou správně naformátovány;
- Měřítko pro grafy je zvoleno správně;
- V různých grafech jsou výsledky pro stejné metody zobrazeny stejnou barvou;
- Mezi umístěním grafů a místy, kde jsou v textu zmíněny (na stejné nebo sousední stránce), je poměrně malá vzdálenost;
- Na stránkách by nemělo být mnoho prázdného místa;
- Ve většině případů by grafy/tabulky/pseudokódy algoritmů neměly zabírat většinu jedné stránky zprávy;
- Všechna čísla v textu/tabulkách jsou označena požadovaným počtem platných číslic;
- Ve většině případů by v sestavě neměl být žádný kód;
- U všech experimentů je popsán zvolený experimentální design a ze získaných výsledků jsou vyvozeny závěry;
MINISTERSTVO ŠKOLSTVÍ RUSKÉ FEDERACE
BASHKIR STÁTNÍ UNIVERZITA
Workshop na počítači
Úlohy pro C++
Část 1
Zkompilovaný:
Rykov V.I. Workshop na počítači. Úkoly pro C++.. Část 1. /Publikace Baškirské univerzity. - Ufa 2006. - č. p.
Práce je věnována metodologii programování v C++.
Obsahuje počáteční informace o kódování, spouštění a ladění programů. Obsahuje texty problémů a případně návody na technologii jejich řešení.
Metodika programování a kódování programů pro každý typ úlohy je prezentována formou kompletních příkladů.
Práce se využívá při provádění laboratorních a praktických prací v oboru „Dílna na počítači“.
1 Úvod 5
1.1 První program 5
2 Nápověda C++5
2.1 Základní datové typy 5
3 Jednoduché datové typy 6
3.1 Modelový problém Vstupní a smyčkové operátory. Hnízdní konstrukce 6
3.2 Struktura pseudokódu 7
3.3 Implementace kontrolních struktur 7
3.4 Modelový problém Celá čísla. Operátory pro, while, if 8
4 pole 10
4.1 Úloha modelu Specifikace polí. Stroj nula 10
4.2 Modelový problém Vnořování řídicích struktur 18
5 Postupy a funkce 20
5.1 Modelová úloha Příklad funkce 20
5.2 Přetížení funkcí 21
5.3 Předání parametrů do funkce 21
5.4 Předání adresy pole funkci 22
6 Vektory a matice 24
6.1 Modelový problém vícerozměrná pole, vstup ze souboru 24
7 Zpracování symbolických informací 29
7.1 Řešení Najděte nejdelší symetrické slovo dané věty 31
8 Rekurze 33
8.1 Řešení: výpočet faktoriálu kladného celého čísla 33
8.2 Řešení Rekurzivní funkce. Práce se strunami. 36
8.3 Řešení Sestavte analyzátor pro koncept závorky. 38
9 Formulář laboratorní zprávy 41
10 Možnosti laboratorní práce 42
1. Úvod
Základní informace o programování jsou uvedeny v dokumentu „Prostředí Microsoft Visual C++ a ladění programů“.
1.1 První program
Program "2+3". V programu se po pozvánce zadávají dvě čísla. Chcete-li zadat každé číslo, musíte je napsat na klávesnici a stisknout klávesu Enter.
#include "iostream.h"
char* Rus(const char* text);
int main(int argc, char* argv)
// coutreturn 0;
char* Rus(konst char* text)
Počítačová dílna, Metody řešení lineárních systémů a hledání vlastních hodnot, Část 1, Bogachev K.Yu., 1998
Tato příručka obsahuje popisy algoritmů navržených pro implementaci na počítači pro studenty Fakulty mechaniky a matematiky Moskevské státní univerzity během výuky na počítači. U všech algoritmů je uvedeno potřebné teoretické zdůvodnění, odpovídající vypočítané vztahy a doporučení pro jejich praktickou implementaci na počítači (organizace procesu výpočtu, ukládání dat a výsledků do paměti počítače atd.).
METODY ŘEŠENÍ LINEÁRNÍCH SYSTÉMŮ ZALOŽENÝCH NA UNITÁRNÍCH MATICOVÝCH TRANSFORMACÍCH.
Každou z výše uvedených metod řešení lineárních soustav lze znázornit jako posloupnost elementárních maticových transformací (viz např. takové znázornění v §4 u Gaussovy metody). Každá z transformací je dána určitou maticí P, takže aplikace této transformace je ekvivalentní vynásobení (vlevo) původní matice A maticí P. Každý krok výše uvedených algoritmů je tedy přechodem z matice P. matice A na matici A = PA. O čísle podmínky této nové matice A=RA můžeme pouze konstatovat, že k(RA)< к(Р)к(А). Поэтому может случиться так. что в процессе проведения преобразований число обусловленности матрицы возрастает и на каждом шаге метод будет вносить все большую вычислительную погрешность. В результате может оказаться, что исходная матрица имела приемлемое число обусловленности, однако после нескольких шагов алгоритма она уже имеет слишком большое число обусловленности, так что последующие шаги алгоритма приведут к появлению очень большой вычислительной погрешности.
Vzniká nápad vybrat transformační matice P takto. aby se číslo podmínky matice během transformačního procesu nezvýšilo. Lemma 1.5 nám ukazuje příklad takových matic: je-li transformační matice P unitární (v reálném případě ortogonální), pak vzhledem ke spektrální normě k(PA) = k(A).
Metoda rotace a metoda odrazu uvedené níže jsou algoritmy pro výběr unitárních transformačních matic P tak, že v důsledku všech těchto transformací je původní matice A zmenšena do trojúhelníkového tvaru. Systém trojúhelníkové matice se pak řeší např. invertováním Gaussovy metody. I přes. že složitost těchto metod je větší než u Gaussovy metody (3, resp. 2krát), tyto metody se ve výpočetní praxi rozšířily díky odolnosti vůči hromadění výpočetních chyb.
Stáhněte si e-knihu zdarma ve vhodném formátu, sledujte a čtěte:
Stáhněte si knihu Workshop na počítači, Metody řešení lineárních systémů a hledání vlastních čísel, 1. část, Bogachev K.Yu., 1998 - fileskachat.com, rychlé a bezplatné stažení.
- Počítačová dílna, Metody řešení lineárních systémů a hledání vlastních hodnot, Část 2, Bogachev K.Yu., 1998
- Matematika a design, 1. stupeň, Učebnice pro všeobecně vzdělávací organizace, Volkova S.I., 2016
- Matematika, Ústní cvičení, 1. stupeň, Učebnice pro všeobecně vzdělávací organizace, Volkova S.I., 2016
Následující učebnice a knihy.
