Graafid (0)

Sarnased õppematerjalid

22

docx

Algoritmid ICD0001 - kordamisküsimused

probleemorienteeritud liides. ADT - Abstract Data Type ● Lubatud väärtuste hulk (väärtusvaru) ● Lubatud operatsioonide hulk ● (Notatsioon - tähistused väärtuste ja operatsioonide jaoks) Andmestruktuurid võib jagada: ● staatilised: komponentide arv ja tüübid fikseeritud: näiteks kompleksarv ● dünaamilised: väärtuse komponentide arv on muutuv, komponendid ise tavaliselt üht tüüpi: näiteks magasin, järjekord, graaf, ... Ahelad Ahel on tee, milles servad ei kordu. Ei jõua tagasi samasse punkti. Tsükli saab ühe kaare lisamisega. Lihtahel on ahel, milles ka tipud ei kordu. Ahel koosneb muutuvast arvust elementidest, mis on omavahel seotud viitadega. Keeles Java ei ole viidatüüpi operatsioone ilmutatud kujul olemas - iga objektitüüpi väärtus on "tegelikult" viit. Lisamine ja kustutamine on lihtsalt kolm omistamist (viitade ümberlülitus) ja nihutamist ei olegi vaja

Algoritmid ja andmestruktuurid

16

pdf

Algoritmid

Postorder – läbida vasak alampuu, läbida parem alampuu, väljastada (töödelda) juur. Inorder – läbida vasak alampuu, väljastada (töödelda) juur, läbida parem alampuu. Puu realiseerimine arvutis – Eelistatud on dünaamiline realisatsioon, kuna see ei nõua esialgu suur mälumahtu & on loomulikum. Sõlmes on kaks viidavälja (rlink, llink) ja võtmeväli (key). Puu koosneb ühest viidast juurele (root). Tühja viida tähis (none). 9. Graaf. Suunatud ja suunamata graaf. Atsükliline graaf. Kaalutud graaf. Graafi realiseerimine arvutis. Topoloogiline sorteerimine. Sügavuti otsimine. Laiuti otsimine (+ lühim tee). Lühim tee kaalutud graafis (Dijkstra algoritm). Graaf – tippude ja servade hulk, servad ühendavad omavahel konkreetseid tippe. Suunatud graaf – iga kaare jaoks on määratud, millisest tipust algab ja millises lõpeb, tähistatakse noolega kaare otsas. Seosel on suund

Analüütiline geomeetria

80

pdf

Algoritmid ja andmestruktuurid eksamiks kordamine

raske tõestada. 2.2.2 Tugevad küljed: • Paljudel juhtudel on teda kergem koostada • Töötab kiiremini kui DP algoritm Optimiseerimise juures on vajalikud teatud tingimused: 1. Kandidaatide hulk (graafi tipud, teede pikkused, rahatähtede suurused...) 2. Valitute hulk, mis või kes on juba kasutatud (sobivaks tunnistatud, tagasi antud rahatähed, läbitud graafi tipud...) 3. Eeldatav lahendus, otsitav summa vms, mille järgi saab otsustada, kas välja valitud kandidaadid moodustavad lahendused (ei pruugi olla optimaalne) 4. Jätkamise näitaja, mille järgi saab otsustada, kas kandidaatide hulka saab suurendada, et lahendust leida. 5. Valikufunktsioon, mille abil valitakse uusi kandidaate väljavalitute hulka 6. Vastusefunktsioon, mis annab lõpliku väärtuse lahendusele 2.2.3 Näide kasutamisest:

Informaatika

21

docx

Graafid ja matemaatiline loogika eksamimaterjal

Tõestame, et ( ( + ) = + ) ( + ) = + Implikatsiooni tõestamiseks eeldame ( + ) = + ja näitame, et siis on tõene ka ( + ) = + Teisendame võrduse vasakut poolt, kuni saame parema poole: ( + ) = ( + ) = ( + ) + = ( + )+ = + ( + )= + Teisendusteks kasutasime: liitmise aksioomi P4, korrutamise aksioomi P6, implikatsiooni vasakut poolt, liitmise assotsiatiivsust, aksioomi P6. Sellega on L 3.2 ja teoreem 3 tõestatud. GRAAFID  Graaf on paar G=(V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad Hulga V elemente nimetatakse graafi tippudeks Hulga E elemente nimetatakse graafi servadeks Multigraaf on graaf, mis võimaldab serva, mis ühendab tippu iseendaga, ning võimaldab mitut erinevat serva kahe antud tipu vahel Täisgraafiks nimetatakse n-tipulist graafi, kui selles graafis on olemas serv iga kahe tipupaari vahel

Algebra I

4

doc

Diskmatt terminid

Loogikafunktsioonide täielik süsteem: loogikafunktsioonide süsteem, mille abil on võimalik kujutada suvalise keerukusega loogikafunktsiooni Täielikkuse kriteerium: loogika funktsioonide süsteem on täielik, kui ta sisaldab vähemalt ühte igast järgnevast funktsioonist: 0 mittesäilitav, 1 mittesäilitav, mittepööratav, mittemonotoonne, mittelineaarne **** Graafid Graaf: objektidevaheliste seoste joonismudel, mis koosneb tippudest ja kaartest. Orienteerimata graaf: kõik kaared suunamata, neid tähistatakse harilike joontega Orienteeritud graaf: kõik kaared suunatud, neid tähistatakse nooltega Ahel: tee orienteerimata graafis Alamgraaf: graaf on mingi graafi alamgraaf, kui ta on selle graafi mingi taandatud graafi jääkgraaf Baas: selline minimaalne tippude osahulk, kus selle osahulga tippudest leidub tee selle graafi mistahes tippu (orienteeritud graafis) Elementaarahel: elementaartee orienteerimata graafis

Diskreetne matemaatika

13

docx

Diskreetse matemaatika elemendid, eksami konspekt

kahe arvu x ja y vahel parajasti siis, kui nende arvude sõnalises kujus ei leidu ühist tähte (,,sõltumatud arvud"). Lihtne on üle kontrollida kõik arvupaarid ja tulemuseks saame R = {(1, 4), (2, 4), (4, 1), (4, 2)} b. Boole'i maatriks: olgu R relatsioon hulkade X = {x1, x2, ..., xm} ja Y = {y1, y2, ..., yn} vahel. Seame relatsioonile R vastavusse m×n-maatriksi, kus maatriski element . Nt, jaguvusrelatsioon. c. Graaf: Relatsioone lõpliku hulga X elementide vahel saab kujutada suunatud graafi abil. Kujutame hulga X elemente graafi tippudena ja joonistame tipust x tippu y kaare, kui kehtib xRy. Nt, jaguvusrelatsioon d. Avaldis: algebralised avaldised, nt võrratused. 22) Hulgal X määratud relatsiooni R nimetatakse  a. refleksiivseks, kui iga x X korral (x, x) R. Nt samasusrelatsioon. Maatriksil on peadiagonaalis kõik ühed, graafis on iga tipu juures silmus.

Diskreetse matemaatika elemendid

92

docx

Diskreetse matemaatika elemendid

 o Relatsiooni hulkade X = {x1, x2, . . . , xm} ja Y = {y1, y2, . . . , yn} vahel saab ette anda ka maatriksiga, mille mõõtmed on m×n, kusjuures reas i ja veerus j asub väärtus 1, kui elemendipaar (xi, yj) kuulub relatsiooni, ning väärtus 0 vastasel korral. Juhul X = Y saame ruutmaatriksi. o Kui R on näiteks viimati vaadeldud jaguvusrelatsioon, siis tema maatriks on Graaf o Ühe võimalusena võib relatsiooni esitada suunatud graafi abil. Kujutame hulga X elemente ja hulga Y elemente punktidena joonisel ning tõmbame kaare elemendist x ∈ X elemendini y ∈ Y parajasti siis, kui paar (x, y) kuulub vaadeldavasse relatsiooni. Niimoodi saame graafi, milles kõik kaared viivad ainult hulgast X hulka Y ning kus pole ühtegi kaart kummagi hulga sees. o Näiteks olgu X tähtede hulk {a, b} ning Y kõigi kahetäheliste sõnade hulk, mida saab

Diskreetne matemaatika

12

docx

Diskreetne matemaatika eksami kordamise materjal

ühisosa, täiend.  Minimaalne Cantori normaalkuju on lihtsaim CNK.  Täielik CNK on normaalkuju, mille iga avaldise osa sisaldab kõiki hulki.  MCNKst saab TCNK kleepimisseaduse abil.  Ristkorrutis on kahe hulga elemendite paaride koostamine.  Järjestatud paare esitatakse loogsulgude vahel.  Otseruut on hulga ristkorrutis iseendaga.  Korteežid on järjestatud paarid, kolmikud, nelikud jne. Graafid:  Graaf on objektide vaheliste seoste mudel.  Graaf koosneb tippudest ja kaartest.  Orienteeritud graafis saab ühest tipust teise minna ainult noolega suunatud kaare mööda. Orienteerimata graafil saab liikuda mistahes suunas kaarel.  Tühi graaf on graaf, kus ühegi tipu vahel ei ole ühtegi kaart.  Täielik graaf on graaf, kus iga tipp on seotud iga teise tipuga.  Väljundaste on tipust väljuvad kaared.

Diskreetne matemaatika

Kommentaarid (0)