p Flashcards

Question

Trieda NP

Answer 1

✅ Trieda NP (Nondeterministic Polynomial time) * problémy, ktorých riešenie možno overiť (verifikovať) deterministickým algoritmom v polynomiálnom čase. * Alternatívne: Riešenie sa dá nájsť pomocou nedeterministického Turingovho stroja * Prakticky zahŕňa mnohé dôležité problémy, pre ktoré nie sú známe efektívne algoritmy s polynomiálnym časom riešenia: * hľadanie Hamiltonovej cesty * problém obchodného cestujúceho * satisfiabilita (SAT) * plánovacie a optimalizačné úlohy

Answer 2

✅ NP-úplné problémy (NP-complete) • Najťažšie problémy v NP • Ak vyriešiš jeden NP-úplný problém v polynomiálnom čase → vyriešiš všetky NP problémy (Stephan Cook, 1970) • Príklad: SAT, 3-SAT, CLIQUE, Traveling Salesman, Hamiltonov cyklus Príklady NP-úplných problémov: * Existencia k-kliky v grafe - či v danom grafe existuje množina k vrcholov, medzi ktorými sú všetky dvojice priamo spojené hranou * Problém obchodného cestujúceho (TSP) – nájdenie najkratšej trasy prechádzajúcej všetkými vrcholmi a návrat do východzieho bodu. * Problém batohu – výber predmetov s maximálnou hodnotou, ktorý neprekračuje nosnosť. * Problém splniteľnosti logických (booleovských) formúl (SAT=satisfiability problem, 3-SAT) * zisťujeme, či existuje také pravdivostné ohodnotenie booleovských premenných, aby daná logická formula bola pravdivá; 3-SAT je jeho verzia, kde každá klauzula má presne tri literály. * Nezávislá množina v grafe (Independent set). * Problém zafarbiteľnosti grafu * Hra Sudoku a rôzne plánovacie či optimalizačné úlohy (rozvrhovanie procesorov, alokácia pamäte a pod.).

Answer 3

Algoritmicky neriešiteľné problémy * Problémy, ktoré žiadny algoritmus ani TS nemôže vyriešiť pre všetky vstupy * Tieto problémy patria do oblasti teórie vyčísliteľnosti a ich existenciu dokazuje tzv. Church-Turingova téza, ktorá hovorí, že každý algoritmus možno realizovať Turingovým strojom . Rekurzívne a rekurzívne vyčísliteľné jazyky * Rekurzívne jazyky sú také, ktoré možno rozpoznať Turingovým strojom, ktorý sa vždy zastaví. * Rekurzívne vyčísliteľné jazyky sú rozpoznateľné Turingovým strojom, ktorý sa môže pre niektoré vstupy nezastaviť (nedokáže vždy rozhodnúť negatívne prípady) . Príklady algoritmicky neriešiteľných problémov: * Problém zastavenia Turingovho stroja (Halting problem): otázka, či sa daný Turingov stroj na konkrétnom vstupe zastaví. Tento problém je nerozhodnuteľný – neexistuje TS, ktorý by ho vždy vedel rozhodnúť . * 🖥️🛑 Halting problem (problém zastavenia) Predstav si, že máš robota, ktorému dáš program a vstup a chceš vedieť: 👉 Zastaví sa niekedy, alebo sa bude vykonávať navždy? Halting problem sa pýta: Existuje univerzálny spôsob, ako zistiť, či ĽUBOVOĽNÝ program so svojím vstupom niekedy skončí, alebo bude bežať donekonečna? - Odpoveď Nie! * Problém akceptovania prázdneho slova ε pre Turingov stroj je tiež algoritmicky neriešiteľný, pretože sa redukuje na problém zastavenia .

Answer 4

Fázy: 1. Plánovanie * voľba produktu - štúdie, analýza trhu * predbežne skúmanie produktu - hlavné funkcie, uživateľske požiadavky * skúmanie realizovateľnosti - technicka realiz, odhad a ekon kalkulacie * vysledné fázy - hrubý katalog požiadaviek, plan 2. Definícia - zoskupenie diagramov * datovo a procesovo orientovane metody * yourdanova metóda - určuje “čo” je treba urobiť v urč. fáze * essential model - čo má systém robiť * enviromental (voči okoliu) - definicia účelu, diagram kontextu * behaviour (def správanie) - DFD, ER, stavové * výsledky analýzy - celkový katalog poziadaviek, opis funkc, slovník dát 3. Návrh * hierarchická štruktúra a správanie modulov * plán testov a nasadenia do prevádzky * logické a fyzická štruktúra údajov * odhad ľudsky a materiálnych zdrojov * 1. verzia príručky 4. Implementácia - transformácia návrhu do funkčného programu, dokumentácie, dopracovanie príručky 5. Odovzdanie a uvedenie do prevádzky - zaberá 20-30% času, 25% nákladov * do fázy patria: * testy funkcií a modulov * integračné testy * nezávislé testy * inštalačné testy * alfa a beta testy - bez živých dát * preberacie testovanie * dokumenty o vysledkoch akc. kriterií a testov, o zaškolovaní používateľov, preberací protokol 6. Údržba a starostlivosť o produkt - update, upgrade, oprava a rozširovanie požiadaviek

Answer 5

§ Štruktúrovaný prístup k modelovaniu * Dátovo orientovaný prístup - štrukúra údajov a ich vzájomné vzťahy * Funkčne orientovaný prístup - opis funkcie * Štrukturovaný prístup - grafická hierarchicka dekompozícia sys * abstrakcia postupne zjemňujúca pohľad až na detailnú úroveň, * Model správania sa systému * Diagram dátových tokov (DFD) - rozdeľuje požiadavky na procesy a zobrazuje v tvare siete, pospojané tokmi údajov - vytvára hierarchické väzby  * * ER diagramy, diagramy prechodu stavov, slovník dát a špecifikácie procesov

Answer 6

Diagram - je grafické znázornenie množiny prvkov. Zvyčajne ako graf s vrcholmi a hranami. § UML (unified modeling language) * štandardizovaný jazyk na vizuálne modelovanie softvérových systémov s použitím OOP prístupu * základné elementy: vzťahy, grafické symboly, text (vo vnutri elemtnov) * Používa sa na analýzu, návrh a dokumentáciu systémov a umožňuje grafické znázornenie ich štruktúry a správania * Využitie UML: režim nákresu, režim projektovania, režim programovacieho jazyka * Case prostriedky: automatizovaný vývoj SW, priamy - kreslenie diagramova, spätný - načítanie kódu a generovanie diagramov * * Poskytuje: * Štruktúrne diagramy * tried * vlastnosti * väzby * komponentov * objektov * Diagramy správania * aktivít - proc. a paralelná činnosť * Sekvenčný diagram – postupnosť správ, ktoré si vymieňajú objekty medzi sebou * prípadov použitia - spolupráca použivateľov so systémom * stavový - zmena objektu v čase na základe udalosti

Answer 7

* Obsahuje: cache buffery, redo log buffer, shared pool (lib cache, dic cache), large pool, java pool, streams pool

Answer 8

* Spoľahlivosť – systém funguje stabilne a predvídateľne * Celistvosť – transakcie sú buď úplne dokončené, alebo úplne zrušené * Nezávislosť – transakcie používateľov sa navzájom neovplyvňujú * Stabilita – po ukončení transakcie sa výsledky zachovajú * Rozšíriteľnosť – systém zvláda rast používateľov a dát * Bezpečnosť – ochrana dát pred neoprávneným prístupom * Flexibilita (3 vrstvy aplikácie): * Užívateľské rozhranie – zobrazovanie dát používateľovi * Aplikačná logika – spracovanie pravidiel a operácií * Riadenie dát – manipulácia a transakcie s databázou

Answer 9

Reprezentuje reálne objekty, vzťahy medzi nimi, ich sémantiku a integritné obmedzenia pomocou konceptuálnych nástrojov. Existujú dva základné druhy vzťahov: 1. Vzťahy atribútov (vzťahy medzi vlastnosťami údajov), 2. Vzťahy asociácií (vzťahy medzi entitami).

Answer 10

c) Relačný model * Dáta vo forme tabuliek (relácií), nezávislé od fyzickej štruktúry, má prirodezenú štruktúru * Podporuje normalizáciu, zabezpečuje vysokú dátovú nezávislosť a minimálnu redundanciu. Časti modelu: 1. Štrukturálna – tabuľky, záznamy (riadky), atribúty (stĺpce). 2. Riadiaca – manipulácia pomocou relačnej algebry a kalkulu. 3. Obmedzenia – integrita, kazdy zaznam primárny kľúč. Charakteristiky modelu: * Každá tabuľka má jedinečný názov, * Každý záznam má rovnakú štruktúru a je jednoznačne identifikovateľný pomocou primárneho kľúča, * Poradie stĺpcov ani riadkov nie je dôležité, * Hodnoty v stĺpci patria tomu istému atribútu, * Hodnoty v zázname musia úplne závisieť od primárneho kľúča. Výhody: jednoduchosť, striktný návrh, nezávislosť dát, jedna inform struktura - tabulka, minimalizacia redundacie dat Nevýhody: nie vždy možne zobraziť cez tabulky, neprehľadnosť pri veľa tabuľkách, vyššie pamäťové nároky.

p Flashcards

(34 cards)