Created for RTU in 2001 DISKRĒTĀS STRUKTŪRAS DATORZINĀTNES DISKRĒTĀS STRUKTŪRAS DATORZINĀTNĒS Lekciju kurss priekšmetā Profesors Jānis Grundspeņķis Rīgas Tehniskā Universitāte Datorzinātnes un informācijas tehnoloģijas fakultāte Sistēmu teorijas profesora grupa

MAIN MENU Diskrētās struktūras datorzinātnēs Kopu Teorija Kopu Teorija Attēlojumi, Grafi un Attieksmes Attēlojumi, Grafi un Attieksmes Grafu Algoritmi Grafu Algoritmi Koki Attieksmes un Datu Bāzes Attieksmes un Datu Bāzes

MAIN MENU Diskrētās struktūras datorzinātnēs Attēlojumi, Grafi un Attieksmes Attēlojumi, Grafi un Attieksmes Grafu Algorimti Grafu Algorimti Koki Attieksmes un Datu Bāzes Attieksmes un Datu Bāzes Kopu Teorija Kopu Teorija Kopu Teorijas Pamatjēdzieni Kopu Teorijas Pamatjēdzieni Operācijas Ar Kopām Operācijas Ar Kopām Kopu Veidi Kopu Veidi

Kopu Teorijas Pamatjēdzieni Kopas jēdziens nav stingri definēts, jo tas ir viens no matemātikas jēdzieniem, kurus nav iespējams izskaidrot ar citiem vēl vienkāršākiem jēdzieniem. Varam tikai aprakstīt kopas, uzrādot to īpašības un savstarpējas sakarības. Svarigi zināt vai elementi pieder kopai, vai nepieder. Viens un tas pats elements var piederēt pie dažādām kopām ar dažādām pakāpēm. Definīcija: Kopa – tas ir noteiktu un savā starpā atšķiramu elementu sakopojums, kuru var apskatīt kā vienotu veselu. Visas kopas apzīmē ar lieliem burtiem ( ar indeksiem ): A, B, X 1, X 2, bet elementus ar maziem: a,b,c...z. MAIN MENU PREVIOUS NEXT

Kopu teorija pēta abstraktu kopu vispārīgās īpašības, kuru noskaidrošanai nav vajadzīgas papīldzīmes ne par šo kopu elementiem, ne arī par speciālām struktūrām tajās. Kopu teorijas pamatā ir attieksme starp kopu un elementu; šo attieksmi sauc par piederību. Piemēram, skaitlis 3 pieder dabisko skaitļu kopai. Apzīmēsim kopu ar lielo burtu A, bet skaitlis – ar mazo burtu a. Tad izteiksmes elements a pieder kopai A raksta šādi: a A. Simbolu sauc par piederības zīmi, bet simbolu par nepiederības zīmi. Kopu Teorijas Pamatjēdzieni MAIN MENU PREVIOUS NEXT

Kopu Veidi Konkrētas kopas var uzdot ar vairākiem paņēmieniem. Galīgas kopas. Šo kopu veido galīgo elementu skaits. Galīgai kopai var uzdod kopas apjomu. Elementu skaits šajā kopā sauc par kopas apjomu: A ={1,2,3,4,5}; | A | = 5. Sanumurējamas kopas. Šajā kopā elementiem var pierakstīt indeksus no naturālo skaitļu kopas. Sanumurējamas kopas ir vienkāršākais galīgas kopas gadījums. Bezgalīgas kopas. Šai kopai ir bezgalīgi daudz elementu. Tukša kopa. Šajā kopā nav neviena elementa Definīcijas: Divas kopas A un B uzskata par vienādām tad un tikai tad, ja tās sastāv no vieniem un tiem pašiem elementiem; tad raksta A=B. Ja divas kopas A un B nav vienādas, tad tās atšķiras viena no otra vismaz ar vienu elementu. Tad raksta A B. MAIN MENU PREVIOUS NEXT

Definīcija: Kopu M sauc par kopas N apakškopu ja visas kopas M elementi ir arī kopas N elementi. Apakškopas var būt: īstas, kad N ietvēr M: M N neīstas, kad M ir neīsta N apakškopa: M N Definīcija: Ja katras kopas A elements u pieder arī otrai kopai B, tad saka kopa A ietilpst kopā B un raksta A B. Teorēma: Divas kopas ir veinādas tad un tikai tad, ja M N un N M. MAIN MENU PREVIOUS NEXT Kopu Veidi

Operācijas Ar Kopām Ar kopām var izpildīt dažādas operācijas ( darbības ), kuru rezultātā iegūst citas kopas. Šīs operācijas sauc par kopu operācijām. A B – apvienojums – kopa, kura sastāv no tiem elementiem, kuri pieder kopai A, vai kopai B, vai arī abām. A B : ={u | u A u B}. A B – šķēlums – kopa, kurā ir elementi, kuri pieder abām kopām vienlaicīgi. A B : ={ u | u A u B}. A \ B – starpība – kopa, kuru veido elementus, kuri pieder kopai A, bet nepieder kopai B. ( A \ B B \ A ). A\B : = { u A u B }. MAIN MENU PREVIOUS NEXT Definīcija: Par kopas A papildkopu sauc to elementu kopu A, kuri nepieder dotajai kopai, t.i., A := { u | u A }.

Kopas brīvu sadalījumu apakškopās sauc par kopas sadalījumu, ja izpildās: 1. A 1 A 2... A n = A ( apvienojot visas apakškopas, saņemsim doto kopu). 2. A i A 0, i j. Ja izpildās tikai 1. īpašība, tad tas ir pārklājums. Piemēram, sadalījums: { {1,2}, {3,4,5} } šķēlums = 0 pārklājums: { {1,2,3,}, {3,4,5} } šķēlums 0 Dotas kopas visu apakšsistēmu saimi sauc par kopu sistēmu. Definīcija: Dotas 2 kopas: A, B. Kopu A un B dekarta reizinājums A B ir kopa, kas sastāv no sakārtotiem pāriem ( kortežiem ), pie kam x obligāti ir ņemts no kopas A, bet y no kopas B. A B B A. MAIN MENU PREVIOUS NEXT Operācijas Ar Kopām

Viens no veidiem kā var uzdot dekarta reizinājumu ir uzdot pāru skaitļi. Pemēram, A B: A = { 1, 2 }; B = { a, b, c } A B = {,,,,, }. Var uzdot arī ar matricu palidzību: Var arī uzdot attēlojumu grafa veidā: 1 2 a b c MAIN MENU PREVIOUS NEXT Operācijas Ar Kopām

MAIN MENU Diskrētās struktūras datorzinātnēs Koki Attieksmes un Datu Bāzes Attieksmes un Datu Bāzes Kopu Teorija Kopu Teorija Attēlojumi, Grafi un Attieksmes Attēlojumi, Grafi un Attieksmes Attēlojuma Pamatjēdzieni Attēlojuma Pamatjēdzieni Attieksmju Pamatjēdzieni Attieksmju Pamatjēdzieni Attēlojumu Veidi Attēlojumu Veidi Attieksmju Īpašības Attieksmju Īpašības Attieksmju Speciālveidi Attieksmju Speciālveidi Elementu Salīdzināšana Sakārtotās Kopās Elementu Salīdzināšana Sakārtotās Kopās Attieksmes Un Grafi Attieksmes Un Grafi Grafu Algoritmi Grafu Algoritmi

Attēlojuma Pamatjēdzieni Attēls f(a) var saturēt jebkuru skaitu kopas B elementu un var būt arī tukšs. Kopas A dažādu elementu attēli kopā B var sakrist vai saturēt kopīgus elementus. Kopā B var atrasties elementi, kuri nepieder nevienam kopas A elementa attēlam. Likums: Katram vienam kopas elementam piekārto otras kopas apakškopu. b, a A 1,3,5,6 B a ={1,3,5} b ={3,6}. Definīcija: Par kopas A attēlojumu kopā B sauc atbilstības likumu f, ar kuru kopas A jebkuram elementam a var piekārtot zināmus kopas B elementus. Šie elementi veido kopas B apakškopu f (a), kuru sauc par elementa a attēlu attēlojumā f. MAIN MENU PREVIOUS NEXT

Definīcija: Par attēlojuma f : A B grafiku sauc kopu reizinājuma A×B apakškopu F A×B vai F : = { a,b | b f(a) } (a A, b B). Dekarta reizinājums – tas ir bināra attieksme starp 2 kopu elementiem ab Definīcija: Par kopas A elementa X attēlu sauc kopas B apakškopu X. Par kopas A patvalīgas kopas S attēlu (S ) sauc visus S elementu attēlu apreizinājumu. S =4 ; x S Attēlojuma Pamatjēdzieni MAIN MENU PREVIOUS NEXT

Definīcija: Par attēlojuma f : A B apvērsto (inverso) attēlojumu sauc attēlojumu f –1 : B A, kuru elementam b B piekārto tos un tikai tos kopas A elementus, kuru attēli satur elementu b. Šo elementu kopu apzīmē f –1 (b) un sauc par elementa b pirmtēlu. Tātad a f –1 (b) : b f (a) (a A, b B). MAIN MENU PREVIOUS NEXT Attēlojuma Pamatjēdzieni

Attēlojumu Veidi 1. Attēlojums kopāA B 2. Attēlojums uz kopuAB 3. DaļējsAB 4. Pilns A B Definīcija: Kopas A attēlojumu kopā B sauc par viennozīmīgu, ja katram kopas A elementam attēls satur tikai vienu kopas B elementu. Definīcija: Pārklajošs attēlojums ( sirjekcija ) – kopas A viennozīmīgs attēlojums uz kopu B. MAIN MENU PREVIOUS NEXT

Definīcija: Iekļaujošs attēlojums ( injekcija ) – attēlojums kurā gan tiešas, gan apgrieztas attēlojumi ir vienādi. – apgriezti– tieši Definīcija: Attēlojumu, kas vienlaicīgi ir sirjekcija un injekcija, sauc par bijekciju. MAIN MENU PREVIOUS NEXT Attēlojumu Veidi Apgriezto attēlojumu var iegūt, apmainot grafikā korteža elementu vietām.

Attieksmju Pamatjēdzieni Bināras attieksmes – attieksmes starp 2 elementiem no 2 kopām. R – simbolisko attieksmju apzīmējums. Definīcija: Bināra attieksme R ir jebkura A B apakškopa. R A B Bināras attieksmes R definīcijas apgabals DR– ir kopa, kas satur tādus elementus x, ka noteikumiem y korteži pieder attieksmei R. DR = {x | R, noteiktiem y } Bināras attieksmes R vērtību apgabals VR – ir kopa, kas satur elementus y tādus, ka korteži R. VR = { y | R, noteiktiem x }. Ternāra attieksmes – attieksmes starp trim elementiem.Tā ir kopa, kura ir A B C kopu apakškopa. R A B C N-āra attieksme – attieksmes starp n elementiem MAIN MENU PREVIOUS NEXT

1. Refliksivitāte Attieksmi sauc par refleksīvu, ja tā ir spēkā katram elementam pašam ar sevi xRx R. Ja xRx neizpildās nevienam elementam no dotās kopas, tad šādu attieksmi sauc par antirefleksīvu vai irrefleksīvu 2. Simetrija Katrai attieksmei xRy eksistē apvērstā attieksme, kuru apzīmē yR ¹x. Attieksme ir simetriska, ja spēkā ir: R=R ¹. Attieksme ir simetriska, ja no tā ka pāris R vienmēr seko tas, ka R Ja no tā, ka vienlaicīgi izpildās attieksmes xRy un yRx, vienmēr seko tas, ka x = y, tad šādu attieksmi sauc par antisimetrisku. MAIN MENU PREVIOUS NEXT Attieksmju Īpašības

Pemēram: dota kopa A: A = {a, b}. Pieņemsim ka ir dota attieksme R A×A, R = {,, }. Attieksme: 1. nav refleksīva, jo nav 2. nav antirefleksīva, jo ir 3. ir simetriska, jo ir un 4. ir antisemetriska, jo ir aRa 5. nav asimetriska, jo ir un uzreiz 6. nav transitīva, jo ir un un nav MAIN MENU PREVIOUS NEXT Ja no tā, ka eksistē R vienmēr seko tas, ka R tad attieksmi sauc par asimetrisku. 3. Transitivitāte Ja no tā, ka ir spēkā xRy un yRz vienmēr seko tas, ka ir spēkā arī xRz, tad šādu attieksmi sauc par transitīvu.

Attieksmju Īpašības Attēlojot attieksmes galīgā kopās ar to incidences matricām, refleksīvas attieksmes matricai galvenajā diagonālē ir tikai vieninieki, bet antirefleksīvas attieksme matricai – tikai nulles. Simetriskas attieksmes matrica ir simetriska pret galvēno diagonāli MAIN MENU PREVIOUS NEXT Definīcijas: Universāla attieksme – attieksme, kura ir spēkā visiem elementiem no dotas kopas. Tukša attieksme – attieksme, kura neizpildās xUy nevienam elementam no dotas kpas. Katrai attieksmei eksistē šis attieksmes papildinājums: xRy, x y.

Attieksmju Specialveidi Ekvivalences attieksme – tas ir attieksme, kurai piemīt 3 īpašības: 1. Refleksivitāte 2. Simetrija 3. Transitivitāte. Ja dotājā kopā ir definēta ekvivalences attieksme, tad šī attieksme doto kopu sadala apakškopās, veidojot dotas kopas sadalījumu, un iegūtas apakškopas sauc par ekvivalences klasi. Ja mēs ņemsim no katras ekvivelences klases pa vienu pārstāvim, mēs iegūstam kopu, kuru sauc par pilnu pārstāvju sistēmu. Refleksīvu, antisimetrisku un transitīvu attieksmi sauc par pamatkopas sakārtojumu (daļēju sakārtojumu). MAIN MENU PREVIOUS NEXT

Ja sakārtojums ir arī aptverošs, jebkuri divi elementi ir savā starpā salīdzināmi, tad to sauc par lineāra sakārtojumu dotājā kopā. Sakārtojuma attieksme ļauj elementus sakārtot noteiktā secībā. Kopa A ir definēts sakārtojums (A,). Kopu sauc par sakārtojumu, ja tajā ir definēta sakārtojma attieksme. Ja sakārtojums ir definēts visiem dotas kopas elementiem, tad šādu sakārtojumu sauc par aptverošu / pilnu. MAIN MENU PREVIOUS NEXT Attieksmju Specialveidi Stingrs sakārtojums – attieksme, kas ir antirefleksīva, antisimetriska un transitīva, kas var arī nebūt aptveroša. Šo sakārtojumu apzīme ar <.

Refleksīvu un transitīvu attieksmi sauc par kvazisakārtojumu. Kvazisakārtojuma jēdziens ietver gan ekvivalences, gan arī nestingra sakārtojuma jēdzienus, vispārinot tos. Attieksme, kas ir refleksīva un simetriska, sauc par toleranci (pseidoekvivalenci). Ja tolerance ir arī transitīva, tad to sauc par ekvivalenci. MAIN MENU PREVIOUS NEXT Attieksmju Specialveidi

Elementu salīdzināšana sakārtotās kopās Patvaļīgas sakārtotas kopas katram elementam var aplūkot to elementu kopu, ar kuriem tas ir salīdzināms. Ja sakārtojums ir aptverošs, lineārs, tad katrs elements ir salīdzināms ar jebkuru citu kopas elementu (un arī ar sevi, ja sakārtojums nav stingrs). Arī vienības attieksmi (kura ir reizē simetriska un antisimetriska) var uzskatīt par sakārtojumu; tā ir triviāls ( vismazākais) daļējais sakārtojums, kurā katrs elements ir salīdzināms tikai ar sevi. Definīcija: Sakārtotas kopas (A,) elementu a sauc par maksimālu šajā kopā, ja u : a u u = a (u A), un atbilstoši elementu b – par minimālu šajā kopā, ja u : u b u = b (u A). MAIN MENU PREVIOUS NEXT

Elementu salīdzināšana sakārtotās kopās Piemēram, dots {a,b,c} šajā kopā definēts ka ir daudz netukšu kopu. Vai šajā kopā ir minimālais elements? {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}. {a} {a,b} {a,b,c} {a} {a,c} {a,b,c} {b} & {c} tad {a}, {b} un {c} – dotas kopas minimālie elementi. MAIN MENU PREVIOUS NEXT Definīcija: Elementu m kas pieder X, sauc par kopas A mažoranti (augšējo slieksni), ja visiem elementiem a A ir spēkā attieksme aRm [ m X, m A, m> a max ].

Pemēram, pieņemsim ka X ir veselu skaitļu kopa un A={-2, -1, 0, 1} Mažorante: m=2, m=3... Minorante: n <-2. Mažorantes vai minorantes var piederēt vai nepiederēt kopai A. MAIN MENU PREVIOUS NEXT Elementu salīdzināšana sakārtotās kopās Definīcija: Elementu n X sauc par kopas A minoranti (apakšējo slieksni), ja visiem a A ir spēkā attieksme nRa. [n X, n A, n< a min ]. Definīcijas: Ja mažorante pieder kopai A, tad to sauc par kopas A maksimumu, maxA. Ja minorante pieder kopai A, tad to sauc par kopas A minimumu, min A.

Definīcijas: Apakškopu, kurai eksistē augšēja robeža (suprēms), sauc par ierobežotu no augšas. Apakškopu, kurai eksistē apakšēja robeža (infims), sauc par ierobežotu no apakšas. Apakškopa, kura ir ierobežota no apakšas un augšas sāuc par ierobežoto. Definīcijas: Ja mažorantu kopai eksistē minimums, tad to sauc par kopas A augšējo robežu (suprēms) sup A. Ja minoranšu kopai eksistē maksimums, tad to sauc par kopas A apakšējo robežu (infimu) inf A. MAIN MENU PREVIOUS NEXT Elementu salīdzināšana sakārtotās kopās Piemēram, X ir veselu skaitļu kopa un A={-2, -1, 0,1}, tad sup A = 2 un inf A = -3.

Lineāri sakārtotu kopu sauc par pilnīgi sakārtotu, ja katrai tās netukšai kopai eksistē minimālais elements. Svarīgas apgalvojumi par kopām: Izvēles aksioma. Katrai kopai eksistē visur definēts funkcionāls attēlojums, kas piekārto katrai tās netukšai apakškopai vienu šīs apakškopas elementu. Cermelo teorēma. Katrā kopā eksistē pilnīgs sakārtojums. No daļēji skārtotajām kopām svarīgākās ir tās, kuru katrai galīgai netukšai apakškopai eksistē suprēms un infims. Šādas kopas sauc par režģiem. Katra lineāri sakārtota kopa ir režģis. MAIN MENU PREVIOUS NEXT Elementu salīdzināšana sakārtotās kopās

Attieksmes un Grafi Katru virsotņu pāri q = {x,y} sauc par grafa G loku jeb šķautni un saka, ka loks q savieno virsotes x un y. Tātad virsotnes x un y ir loka q galapunkti ( robežpunkti ). Bez tam virsotnes, kas savienotas ar loku sauc par blakusstāvošām. Virsotne x un loks q ir incidenti, tāpat kā virsotne y un loks q, jo virsotnes ir loka galapunkti. Eksistē tādi jēdzieni kā orientēts grafs un neorientēts grafs. Orientētā grafā lokus attēlo ar bultām. Šajos grafos kopa Q sastāv no sakārtotiem pāriem ( kortežiem ) q =. Virsotni a sauc par orientētā loka q sākuma, bet virsotni b – par šī loka beigu virsotni. abab neorientēts grafsorientēts grafs Grafs G sastāv no netukšas kopas X, kas satur elementus x X jeb grafa virsotnes, un dotas kopas Q, kura satur kopa X dažādu virsotņu nesakārtotus pārus. MAIN MENU PREVIOUS NEXT

Virsotne ir incindenta lokam, ja virsotne ir loka galapunkts. Loku skaitu kas ir incindenti virsotnei, sauc par šīs virsotnes lokālo pakāpi V1V1 V2V2 V3V3 V4V4 V 2, V 3 – ar lokālo pakāpi 2. V 1, V 4 – ar lokālo pakāpi 3. Ja ir orientēts grafs, tad eksistē lokālas pakāpes ar ieejošiem un izejošiem lokiem. Lokālu pakāpi ar izejošiem lokiem apzīmē ar: d G +, ar ieejošiem lokiem apzīmē ar: d G -. Peimēram, dots orientēts grafs ar 4 virsotnēm: V 1, V 2, V 3, V 4 : V1V1 V2V2 V3V3 V4V4 Tad lokāla pakāpe virsotnei V 1 ir: d G + (V 1 ) = 2 d G - (V 1 ) = 1. MAIN MENU PREVIOUS NEXT Attieksmes un Grafi

Eksistē tāds jēdziens kā jaukts grafs. Šajā grafā ir gan orietēti, gan neorientēti loki. Šo grafu var pārveidot orientētā, apmainot neorientētus lokus uz orientētiem lokiem: jaukts garfspārveidots grafs Loku, kas savieno virsotni pašu ar sevi q = {x,x,}, pieņemts saukt par cilpu. Ja grafs satur cilpas, tad tas ir grafs ar cilpām. Ja starp vienu virsotnes pāri ir vairāki atšķirīgi loki, tad šādu grafu sauc par multigrafu. Ja multigrafs satur arī cilpas, tad šādu grafu sauc par pseidografu. multigrafspsiedografs MAIN MENU PREVIOUS NEXT Attieksmes un Grafi

Ja katrā virsotnē ir cilpa, tad grafs attēlo refleksīvu attieksmi. Ja nevienai virsotnei nav cilpas, tad grafs attēlo nerefleksīvu attieksmi. Attieksme ir simetriska, ja oirentētā grafā katram lokam ir pretējs: ab un ba. Cilpa neietekmē uz simetriju. Ja grafā ir kaut viens orientēts loks, kuram nav pretēja, tad grafs ir asimetrisks. Orientēts grafs ar cilpām attēlo antisimetrisko attieksmi. Transitivitātei jābūt 3 virsotnēm. (a,b) un (b,c) =>(a,c). Lai parbaudītu transitivitāti, jāmeklē celš ar garumu 2, kuriem jābūt nosledzošiem lokiem. Ceļš ar garumu n ir virsotņu V 0, V 1,..., V n secība tāda, ka katram i=1, n pāris (Vi- 1, Vi) Q. Pie tam, ja ir (a,b) un (b,c) =>(a,c). MAIN MENU PREVIOUS NEXT Attieksmes un Grafi

Ja mēs atradām ceļu ar sākumvirsotni V 0, visas virsotnes, kuras ietilpst šajā ceļā, tiek sauktas par virsotnes pēctēčiem. Г G + (V 0 ) => šis virsotnes pēctēču kopa. Pemēram: Г G + (a) = {b,c,d} Г G + (b) = {c,d} Г G + (d) = {-} Г G + (c) = {d} d c ba MAIN MENU PREVIOUS NEXT Attieksmes un Grafi Cikls, (ceļš ar garumu 3). Ceļu,kuram sākumvirsotne sakrīt ar beigumvirsotni, sauc par ciklu.

MAIN MENU Diskrētas struktūras datorzinātnēs Koki Attieksmes un Datu Bāzes Attieksmes un Datu Bāzes Kopu Teorija Kopu Teorija Attēlojumi, Grafi un Attieksmes Attēlojumi, Grafi un Attieksmes Grafu Algoritmi Grafu Algoritmi Informācija Par Grafu Uzdošanas Veidi Informācija Par Grafu Uzdošanas Veidi Īsāko Ceļu Meklēšana Īsāko Ceļu Meklēšana Ceļu Meklēšana Grafos Ceļu Meklēšana Grafos Deikstra Algoritms Deikstra Algoritms Floida Algoritms Floida Algoritms Tīkli Tīkli Transporta Tīkli Transporta Tīkli Forda-Falkersona Algoritms Forda-Falkersona Algoritms

Informācijas Par Grafu Uzdošanas Veidi Eksistē 2 klases: 1. statistiskie atspoguļojumi 2. dinamiskie atspoguļojumi A = Galvenāja diagonālē – 0, jo nav cilpu. => nevar būt refleksīva => simetriska pret galvēno doagonāli, kas nozīme, ka attieksme ir simetriska. Blakusvirsotņu matrica – tas ir kvardrātveida matrica. |V| |V| – matricas apjoms, matricas elementi ir 1 un 0. A (i,j) = 1, ja loks ( i, j ) Q 0, ja loks ( i, j ) Q MAIN MENU PREVIOUS NEXT

Orientētājā grafā ir loks, kurš iziet no i un ieiet j, tad matricā (i,j) vietā ir 1. Ja matrica ir bināra, tad uzdod matricu, jāpatērē atmiņas apjomu : O ( | V| 2 ) bitu. Ja mums ir orientēts grafs un mēs gribam pārbaudīt, vai 2 virsotnes ir saistītas, tad mēs patērētu O (1) laiku 1 operācijai. Ja mēs grībam pārbaudīt blakusvirsotņu matricu jāpatērē : O (n) vai O( |V| ). Bez blakusvirsotņu matricas lieto arī loku sarakstu. Loku sarakstu veido visu virsotņu pāri, kuri atbilst dota grafa lokiem. Mūsu gadījumā tas ir : { (1,2), (1,4), (1,5), (2,1), ( 2,3),... }. Atmiņas apjomu, kuru jāpatērē, lai atspoguļotu bināra matrica ir: O (2 |Q|) MAIN MENU PREVIOUS NEXT Informācijas Par Grafu Uzdošanas Veidi

Sasniedzamības matrica – ir kvadrātveida matrica ar izmēru n n R(i,j) = 1, ja grafa ceļš no i uz j 0, prētējā gadījumā Incidenču matrica – taisnstūra veida matrica ar izmēru n m, kur n ir rindas, kuras atbilst grafa virsotnēm, un m ir kolonas, kas atbilst grafa lokiem Neorentēta grafā B (i,j) = 1, ja virsotne V i incindenta lokam q j 0, ja prētējā gadījumā Orientēta grafā B (i,j) = +1, ja V i incidenta lokam q i un q j iziet no V i –1, ja V i incidenta lokam q i un q j ieiet V i 0, ja prētējā gadījumā MAIN MENU PREVIOUS NEXT Informācijas Par Grafu Uzdošanas Veidi Teorēma: Ja A ir blakusvirsotņu matrica tad elements (i,j) matricā A k ir vienādas dažādu ceļu skaitu no i uz j, pie nosacījuma, ka katrā ceļā ir navairāk pa k lokiem. => Mazāka pakāpe k, pie kuras elementi (i,j) 0, norāda attālumu starp virsotnēm i un j.

Visi dināmiskie atspoguļojumi balstās uz datu struktūras – blakus virsotņu saraksta (BVS). ADJ = BVS ADJ (V 1 ) : V 2 V 4 ADJ (V 2 ) : V 4 ADJ (V 3 ) : V 4 ADJ (V 4 ) : V 5 ADJ (V 5 ) : zero BVS organizēšana BVS var organizēt kā tā saucamo lineāro masīvu. V1V1 V2V2 V3V3 V4V4 V5V5 V2V2 V4V4 V3V3 Lineārs masīvs – tāda struktūra, kurā katrai virsotnei atbilst viens lineārs komponents. MAIN MENU PREVIOUS NEXT Informācijas Par Grafu Uzdošanas Veidi

Lineārs saraksts ar norādēm. Katrai virsotnei ir norādīta tai sekojoša virsotne, kura atspoguļo virsotņu secību. MAIN MENU PREVIOUS NEXT Informācijas Par Grafu Uzdošanas Veidi V1V1 V3V3 V3V3 V2V2 V2V2 V4V4 V4V4 V4V4 V5V5 V5V5

MAIN MENU PREVIOUS NEXT Informācijas Par Grafu Uzdošanas Veidi Nemainīgais saraksts – ir tikai 1 ieeja, kas ir speciāli norādīta, nav tiešas pieejas nekādiem datiem, izņemot to, kurai ir pieeja. V1V1 V2V2 V3V3 V2V2 V4V4 V3V3 V4V4 V4V4 V5V5 V5V5 V1V1 V2V2 V3V3 V4V4 V4V4

MAIN MENU PREVIOUS NEXT Ceļu Meklēšana Grafos Ceļu meklēšana grafos balstās uz Back Trak principu – meklēšana atkāpjoties. Tiek fiksēts ceļa sākumvirsotnes numurs un algoritms virzās uz priekšu formējot tā saucamo tekoša ceļa sarakstu, kurā iekļauj tikai tādas virsotnes, kurās numurs ir vairāk, nekā ceļa sākumvirsotnes numurs numurs nav sastopams tekošā ceļa sarakstā. Algoritms tiek virzīts uz priekšu tik ilgi kamēr var pievienot jaunas virsotnes numuru, kas apmierina nosacījumus un ja tas vairs neiespējams, notiek atkāpšanas uz priekšpēdējo virsotni tekošajā ceļā un algoritms mēģina turpināt ceļu no šīs priekšpēdējas virsotnes.

MAIN MENU PREVIOUS NEXT Ceļu Meklēšana Grafos Piemēram, dots orientēts grafs no 8 virsotnēm un jāatrod ceļu no virsotnes 1. (Back Trak procedūra atkāpjas uz vienu soļu) –2 – 3 – 5 – 7 – 8 1 –3 – 5 – 7 1 – 2 – 3 – 5 1 – – 2 – 4 – 5 – 7– 8 1 – 2 – 4 – 5 – 7 1 – 2 – 4 – – 2 – 4 – 6 – 7– 8 …….. Ja ceļā parādās, ka virsotne, kurai numurs ir tāds pats, kā sākumvirsotnes numurs, tad var atrast algoritmā arī ciklus. Ceļu meklēšanas algoritms domāts visu ceļu atrāšanai.

MAIN MENU PREVIOUS NEXT Īsāko Ceļu Meklēšana Grafos Grafa lokiem ir doti svari: W (i,j), kas norāda tās lokus, kuri nāk no virsotnes i uz virsotni j svaru. Svars ( W ), norāda attālumu starp i un j. Uzdevumi: 1.jāmeklē ceļu starp uzdoto ( fiksēto ) virsotņu pāri. 2.jāmeklē īsākie ceļi no fiksētas sākumvirsotnes uz visām pārējām virsotnēm. 3.jāmeklē īsākie ceļi starp visiem iespējamiem virsotņu pāriem. Svari var būt gan pozitīvie, gan negatīvie.

MAIN MENU PREVIOUS NEXT Deikstra algoritms balstās uz iezīmju piešķiršanas tehniku. Katrā iterācijā grafa virsotnēm piešķir iezīmes, kuras norāda īsāka ceļu garumu, ar norādījumu, ka ka īsākajā ceļā ietilpst nevis visi iespējami loki, bet fiksēta loku apakškopa. Sākumvirsotnei iezīmi piešķiram nozīmi = 0, bet pārējam virsotnēm iezīmes =. Algoritmā izpildes gaitā notiek iezīmju maiņa tā, ka ka katrā iterācijā tieši viena iezīme kļūst par konstanti (const) un šī iezīme norāda īsāka ceļa garumu no sakuma virsotnes uz doto virsotni. Const iezīme ir tāda iezīme tādai virsotnei kurai iezīme dotajā iterācijā ir minimāla. Deikstra Algoritms Deikstra algoritma pierakstīšana pseidokodā Procedūra Deikstra { jābūt dotam svērtam grafam, kuram doti svāri ir pozitīvi } { virsotnes ir sanumurētas a = v 0, v 1, v 2,..., v n = z } { ja loks neeksistē tad W = }.

MAIN MENU PREVIOUS NEXT For i:=1 to n l (a) := 0 l (v 1 ) := S = 0 { virsotņu kopa, kur ir virsotnes const iezīmēm } While z S { z – beigu virsotne } Begin p :=v * { v * – virsotne, kas nav iekļauta kopā S un kurai iezīme l (p) ir minimāla } S := S {p} { S pievienojam virsotne p } For... { visam virsotnēm V, kas nav kopā S } If l (p) + W (p, v) < l (v) Then l (v) = l (p) + W (p, v) End; Deikstra Algoritms

MAIN MENU PREVIOUS NEXT Deikstra Algoritms Algoritms sastāv no 4 soļiem 1). l (a) := 0 l (v i ) := a vivi p = a {ievadam} 2). v i Г (p) { Г – attēls } ar maināmām iezīmēm mainām iezīme saskaņa ar šādam nosacījumiem l (v i ) = min [ l (v i ), l (p) + W (p, v i ) ] 3). Starp visam virsotnēm ar maināmām iezīmēm atrast tādu kurai l (v * ) = min ( l (v i ) ) 4). Uzskatīt iezīmi l (v * ) par const, ņemt p = v * un pāriet uz otro soli, ja ir vēl virsotnes ar maināmām iezīmēm. Pretējā gadījumā algoritma beigas.

MAIN MENU PREVIOUS NEXT Deikstra Algoritms Piemēram, dots grafs no 6 virsotnēm un jāatrod ceļu no a uz f a ce d f b l (a) := 0 l (v i ) := vi vi { b, c, d, e, f } a b c d e f S 0 = {a} const ( Jāatrod virsotni ar minimālo iezīmi. Šī iezīme kļūst const ) 0*0* p = a Г (a) = {b,c} l (v i ) = min { l (v i ), l (p) + W (p, v i ) } l (b) = min {, } = 4 l (c) = min {, } = 2 ( Starp visām iezīmēm, kuras vēl nav konstantes, jāatrod minimālo ) a b c d e f 0*0* 42*2*

MAIN MENU PREVIOUS NEXT Deikstra Algoritms S 1 = { a, c } ( atradām īsāko ceļu no a uz c, kurš ir vienāds ar divi ) p = c Г (c) = { b, d, e } l (b) = min { 4, }= 3 l (d) = min {, }= 10 l (e) = min {, 2+10 }= }= 12 a b c d e f 0*0* 3*3* 2*2* 1012 S2 S2 = { a, c, b } p = b Г (b) = { d } l (d) = min { 10, }= 8 a b c d e f 0*0* 3*3* 2*2* 8*8* 12 S3 S3 = { a, b, c, d } p = d Г (d) = { e, f } l (e) = min { 12, }= 10 l (f) = min { 10, } = 14 a b c d e f 0*0* 3*3* 2*2* 8*8* 10 * 14 S4 S4 = { a, c, b, d, e } p = e Г (e) = { f } l (f) = min { 10, }= 13 a b c d e f 0*0* 3*3* 2*2* 8*8* 10 * 13 * S5 S5 = { a, c, b, d, e, f }

MAIN MENU PREVIOUS NEXT Īsāko ceļu pārbaude: l (v i ) + W (v i, v i ) = l (v i ) [ v i – virsotnes v i priekštecis ] no a uz f ? l (f) = l (e) + W (e,f ) l (f) = l (d) + W (d,f ) ? – e – f l (e) =... kamēr netiksim līdz a Deikstra Algoritms Ja virsotņu skaits ir n, tad iterāciju skaits ir n-1. Sliktākajā gadījumā, vienā iterācijā lai atrastu min, jāizpilda 2(n-1) operācijas. Deikstra algoritma īsāko ceļu starp fiksēto virsotni un citam veicot nevairāk kā n 2 operācijas –– O(n 2 ). Deikstra algoritms strādā tikai tad, kad svari ir pozitīvi.

MAIN MENU PREVIOUS NEXT Floida Algoritms 1). k := 0 2). k := k +1 3). i k W ik j k W kj W ij = min [W ij, W ik + W kj ] Floida algoritms – efektīvākais algoritms, īsāko ceļu atrašanai starp jebkuru virsotņu pāri jebkurā grafā izpildot nevairāk ka n 3 operācijas un ir visvienkāršākais šim uzdevumam. Algoritms balstās uz svaru matricu pārveidošanu.

MAIN MENU PREVIOUS NEXT Floida Algoritms 1). ja W ii < 0 (W ii – svars uz galvenās diagonāles), tad grafā ir cikls ar negatīvo summāro garumu, un algoritms darbu beidz, jo uzdevumam nav atrisinājuma. 2). ja W ii 0; k = n, tad algoritms darbu beidz, jo īsākie ceļi ir atrasti. 3). ja W ii 0; k < n, tad algoritms atgriežas uz 2. soli palielina k vērtību. Algoritma beigu pārbaude

MAIN MENU PREVIOUS NEXT Tīkli Topoloģisku šķirošanu var realizēt, ja tīklā nav ne 1 cikla. Ja virsotne V, |V| = n, tad kopas V topologiska šķirošana ir bijekcija t, kura realizē šādu attēlojumu: t : {0,..., n-1} V Pie tam, ja loks ( t(i), t(j) ) U => i katra virsotne ir tāds loks, ka tam sākumvērtība ir < par loka beigu vērtību. Topoliģiska šķirošana rezultātā saņem sakārtotas virsotnes. Tīklos ir > n+1 loks, tīklos var būt arī cikli. Parasti nav lietojamas cilpas. Praktiski katram tīklam ir tikai viena sākumvirsotne x s ( tīkla ieeja) un tāda virsotne, kurā neieiet ne viens loks Г – (x s ) = 0, x t = Г – (x t ) = 0.

MAIN MENU PREVIOUS NEXT Algoritms: i = 0 W:=V - dota tīkla virsotņu kopa WHILE W0 DO BEGIN w W d – (w) = 0 // ņemam tādu virsotni kurā neieiet neviens loks t(i) = w w :=W –{w} virsotne, kura ieguva savu numuru i:=i+1 a c e d f b it (i) W adbcefadbcef {a, b, c, d, e, f} {b, c, d, e, f} {b, c, e, f} {c, e, f} {e, f} {f} Tīkli

MAIN MENU PREVIOUS NEXT Transporta Tīkli Par transporta tīklu sauc galīgu grafu bez cilpām. Kur katram u ir dots vesels skaitlis q(u) 0, ko sauc par šī loka caurlaides spēju. Transporta tīkla raksturojumi: – visi ieejoši virsotnē x loki – visi izejošie loki 1). Šim grafam eksistē tikai viena ieeja un tikai viena izeja 2). Šādam tīklam ir definēta tā saucama plūsma. 2). 3). (u) q (u) // neviena loka plūsma nevar būt vairāk par šī loka caurlaides spēju 4). Plūsma ir funkcija, kurai ir spēkā šādas īpašības: 1). (u) 0 (u U)

MAIN MENU PREVIOUS NEXT Transporta Tīkli Tās 4 īpašības var pierakstīt arī ar plūsmas saglabāšanas vienādojumu: Transporttīklā raksturīgais uzdevums: noteikt maksimālo iespējamo plūsmas vērtību – max V. Transporttīkla loku, kurā plūsma vienāda caurlaides spējai, sauc par piesātinātu loku. Forda-Falkersona teorēma: Maksimālais plūsmas lielums no tīkla ieejas xs xs uz tīkla izeju xt xt ir vienāds ar minimālu griezuma caurlaides spēju, pie tam jāņem tāds griezums, kas atdala tīkla ieeju no tīkla izejas.

MAIN MENU PREVIOUS NEXT Transporta Tīkli Eksistē 2 griezumi: 1) Loku griezums 2) Virsotņu griezums Loku griezums – tāda loku kopa, kuru izslēgšana no grafa rada vismaz 2 nesaistītus apakšgrafus. Virsotņu griezums – tāda virsotņu kopa, kuras izslēgšana rada vismaz 2 nesaistītus apakšgrafus. Transporttīklos meklē tādus griezumus, kuri transporttīkla virsotnes sadala 2 kopās

MAIN MENU PREVIOUS NEXT Saskaņa ar Forda-Falkersona teorēmu, jāatrod min griezums – tāds griezums, kurā summārā caurlaides spēja ir minimāla. Transporta Tīkli 4 10 xsxs xtxt Griezumi

MAIN MENU PREVIOUS NEXT Forda-Falkersona Algoritms Katra virsotne var atrasties viena no trim stāvoklim: 1. virsotne var būt iezīmēta un caurskatīta ( ir apstrādātas visas ar doto virsotni saistītas virsotnes) 2. virsotne ir iezīmēta, bet nav caurskatīta 3. virsotne nav iezīmēta. x i – iezīme, kura sastāv no divām daļām, kuras var būt 2 tipu: 1. (+x j, ) 2. (–x j, ), – ir tāds lielums par kuru šajā lokā plūsmu var palielināt (+) vai pamazināt (–). x1x1 x2x2 x3x3 x4x4 x5x5 x6x A daļa: Iezīmju piešķiršana 1s. x s – tīkla sākumvirsotne, kurai piešķiram iezīmi: (+ x s, (s) = ) = (+ x s, ), nevienai citai virsotnei iezīmju nepiešķiram.

MAIN MENU PREVIOUS NEXT Forda-Falkersona Algoritms 2s. Ņemam kādu iezīmētu bet necaurskatītu virsotni: (± x k, ( x i )) a) katrai neiezīmētai virsotnei, kura pieder Г( x i )x j Г( x i ), kurai izpildās sakarība: ij < q ij ( ij – plūsmas lielums, q ij – loku caurlaides spēja) (+x i, ( x j )) ( x j ) = min [ ( x i ), q ij – ij ] x 1 : ( + x 1, ) x j Г( x 1 ) : { x 2, x 3 } x 2 : ( + x 1, 9 ) x 3 : ( + x 1, 8 ) Г( x 2 ) = { x 4 } x 4 : ( + x 2, 4) min [9, 4-0] Г( x 3 ) = { x 5 } x 5 : ( + x 3, 7) min [8, 7-0] Г( x 4 ) = { x 5, x 6 } x 6 : ( + x 4, 1) min [4, 1-0]

MAIN MENU PREVIOUS NEXT Forda-Falkersona Algoritms b) x j Г –1 ( x i ), kurai ji > 0 (– x i, ( x j )) ( x j ) = min [ ( x i, ) ji ] 3s. Atkārto 2 soli tik ilgi kamēr ir iezīmēta tīkla beigu virsotne x t. Ja tīklu beigu virsotne nav iezīmēta, un nevar piešķirt iezīmēs arī kādām citām virsotnēm tīklā: algoritms darbu beidz, maksimāla plūsmas vērtība ir atrasta. B daļa : plūsmas palielināšana 4s. x = x t 5s. a) Ja virsotnes x iezīme ir ( + z, ( x )), tad lokā (z, x) jāmaina plūsma: z, x (x t ) b) (-z, ( x t ) x, z – ( x t ) 6s. Ja z = x s, tad jādzēš visas iezīmes un jāatgriežas uz 1 soli. Ja z x s, tad x:= z un atgriežas uz 5 soli.

MAIN MENU Diskrētas struktūras datorzinātnēs Kopu Teorija Kopu Teorija Grafu Algoritmi Grafu Algoritmi Attēlojumi, Grafi un Attieksmes Attēlojumi, Grafi un Attieksmes un Datu Bāzes Attieksmes un Datu Bāzes Koki Koku Pamatjēdzieni Koku Pamatjēdzieni Kraskala Algoritms Kraskala Algoritms Prima Algoritms Prima Algoritms Lemumu Koka Konstruēšana Lemumu Koka Konstruēšana Prefiksa Koda Izmantošana Prefiksa Koda Izmantošana Koku Apiešana, Universāla Adrešu Sistēma Koku Apiešana, Universāla Adrešu Sistēma Apiešanas Algoritmi Apiešanas Algoritmi Prefiksa, Infiksa, Postfiksa Pieraksti Prefiksa, Infiksa, Postfiksa Pieraksti

MAIN MENU PREVIOUS NEXT Koku Pamatjēdzieni Definīcija: Par koku sauc saistītu neorientētu grafu, kas nesatur ciklus. Šajā grafā, starp jebkuru virsotņu pāri eksistē 1 vienīgais ceļš. Komponenšu skaits 1 Cikliskais rangs 0 Loku skaits m = n – 1 Kokam raksturīgie lielumi ir šādi: Jebkuras divas virsotnes savieno vienīgā vienkāršā ķēde. Kokam ir šādas īpašības: Jebkura loka izslēgšana pārvērš koku nesaistītā grafā, Pievienojot loku starp jebkurām virsotnēm, kas nav blakusstāvošas, parādās vienkāršs cikls, Jebkuram kokam ir vismaz 2 virsotnes, kam (x) = 1, un vismaz viens loks, kura galapunkti ir šīs virsotnes.

MAIN MENU PREVIOUS NEXT Koku Pamatjēdzieni Grafu, kam nav ciklu un kas satur komponentes, sauc par mežu, sastāvošu no kokiem Ja nepieciešams kokā izvēlēties kādu virsotni, tad šo virsotni sauc par koka sakni. Orientētā grafā visas orientācijas iziet no 1 virsotnes, kuru sauc par sakni. Izejošā kokā visi ceļi ienāk saknē. Ja kokā izdala kādu noteiktu ķēdi, tad to nosauc par koka stumbru. Katru koka virsotni x, kas nepieder stumbram, ar tuvāko stumbra virsotni saista viena vienīga ķēde, ko sauc par zaru. Koka diametrs ir garākās ķēdes garums. Ja koka diametrs d (G) ir pāra skaitlis, tad kokam ir viens centrs x, bet rādiuss vienāds ar ½ d (G). Ja d (G) ir nepāra skaitlis, tad kokam ir 2 centri un rādiusa garums ir ½ [d (G) + 1]. Par koka virsotnes x svaru sauc vislielāko loku skaitu, kas pieder kādam no zariem ar galapunktu virsotnē x. Koku skaits, kur var konstruēt izmantojot n dotas virsotnes, ir n n – 2.

MAIN MENU PREVIOUS NEXT Koku Pamatjēdzieni Koka sakne atrodas nulles līmenī. Sekojošā attēlā parādīts binārs koks. 0. līmenis 1. līmenis 2. līmenis Apakšgrafs, kas satur visas grafa virsotnes un ir koks tiek saukts par karkasu ( skeletu ). Grafa bez cilpām dažādu karkasu skaits ir vienāds ar jebkura galvenās diagonāles elementa minoru kvadrātveida matricā B·B T, ( B – incidenču matrica ). Pilna grafa dažādu karkasu skaits ir n 2, kur n – virsotņu skaits. Eksistē 2 paņiemieni karkasu noteikšanai: 1. doto grafu pakāpeniski samazināt tik ilgi, kamēr iegūstam karkasu ( izslēgt nevajadzīgus lokus). 2. sistemātiski palielināt grafu tik ilgi, kamēr iegūstam karkasu.

MAIN MENU PREVIOUS NEXT Samazināšana Piemēram, ir dots grafs ar 9 virsotnes un 12 lokiem. Koku Pamatjēdzieni abc d g e h f i Lai doto grafu pārveidot karkasā jāindeficē visus ciklus un jāizslēdz tādus lokus kuri veido šos ciklus. Ja izdosies izslēgt visus ciklus, tad grafu var uzskatīt par koku. Un izmantojot Back Trak principu var iegūt karkasu: e – f – i – h – g – d – a – b – c.

MAIN MENU PREVIOUS NEXT abcj d e f g hi Palielināšana: Dotajā grafā pievienosim vienu virsotni un izmantosim pārmeklēšanu plašumā. Izvēlētai sākumvirsotnei ( e ) pievienosim visas incidentas virsotnes tā, lai nebūtu ciklus. a b c j d e f g h i Īsākais karkass – ir karkass, kurā loku summārais garums ir minimāls. Koku Pamatjēdzieni

MAIN MENU PREVIOUS NEXT Prima Algoritms Vispirms jāatrod incidenču lokus dotai virsotnei un starp šiem lokiem jāizvēlas loku ar minimālo garumu. Pēc tam šim lokam jāpievieno nākošo loku ar minimālo garumu, saglabājot nepārtrauktības principu. Piemēram, dotajam grafam jāatrod īsāko karkasu. 3 fe d hg b i c j a ). e – b 2). b – a 3). e – f 4). e – h 5). h – g 6). f – i 7). g – d 8). f – c 9). c – j īsākais karkass = 16

MAIN MENU PREVIOUS NEXT Prima algoritms sastāv no 4 soļiem: Prima Algoritms T s ={ x s } x s - sākumvirsotne T s – konstruējamais koks Q s = 0 Q s - loku kopa xj xj Ts Ts ; j Ts Ts ; W( j, xj xj ) = min [ W ( x i, xj xj )] = j ; xi xi TsTs xj xj := [ j, j ] Ja Г(x j ) Ts Ts = 0, tad xj xj := [ 0, ] izvēlās tādu virsotni kurai x j *, kuros ir minimāla. j * = min [ j ], x j TsTs T s = { x j * } (tiek palielināts konstruētais koks ) Qs Qs = Qs Qs { j *, j * } (pievieno lokus) Ja | Ts Ts | = n, algoritms beidzas un kopa Qs Qs satur tos lokus, kuri pieder īsākajām karkasam. Ja | Ts Ts | n, pārejam uz 4. soli:

MAIN MENU PREVIOUS NEXT Prima Algoritms Visam xj xj, kas nepieder T s – kuras vēl nav kokā, un tādam, kuram x j Г(x j * ) Ja j > W ( x j *, x j ), tad visiem virsotnēm jāatjauno iezīmes => j = W ( x j *, x j ); j = x j * ; atpakaļ uz 3. soli Ja j W ( x j *, x j ) => uz 3. soli.

MAIN MENU PREVIOUS NEXT Kraskala Algoritms Visā grafa kopumā jāatrod loku ar minimālu garumu, tad jāpārbauda vai ir grafā loki ar tādu pašu garumu un tad tos pievieno pirmajam, sekojot principu, ka nevar būt ciklus. Tad meklējam lokus kura garuma ir par vienu lielāks, tos pievieno lai neizveidotu ciklu. abc d g e h f i j LokiLoka garums a – b1 b – e1 g – h1 c – j1 e – h2 e – f2 f – i2 b – c3 a – d3 Īsākais karkass =16 Piemēram:

MAIN MENU PREVIOUS NEXT Lēmumu Koka Konstruēšana Risinot problēmu, katras risināšanas gaitā, pieņemto lēmumu jāattēlo kā koka virsotni. Turpinājot līdz lēmumu atrisināšanai. Grafu sauc par izkrāsotu, ja piekārtojot tā virsotnēm noteiktas krāsas, katras divas kaimiņu virsotnes ir dažādās krāsās. Četru krāsu hipotēze: Jebkurā grafā virsotnes var izkrāsot ne vairāk kā 4 krāsām. a : b a : cb : c b < a < cc > b > aa : c a > b > c a > ba < b a > ca < cb < cb > c a > c > b b > cb < c b > a > c a > c b > c > a a < c Šķirošanas procedūra Savā starpā salīdzināt 3 elementus: a, b, c.

MAIN MENU PREVIOUS NEXT Šķirošana Saplūstot Piemēram, jāsašķiro skaitļu virkni kura atrodas masīvā [1-10] izmantojot koku. Faktiski algoritms sastāv no 2 daļām: 1. daļā visus skaitļus dalām 2 daļās. Katru virsotni dalam uz 2 virsotnēm un t.t. Nākošajā attēlā paradīts kā tika sadalīta nesašķirota skaitļu virkne. Lēmumu Koka Konstruēšana

MAIN MENU PREVIOUS NEXT Lēmumu Koka Konstruēšana 2. daļa – saplūšana. 1. saraksts2.sarakstsSaplūdušais saraksts Salīdzinošais saraksts –1 < < < < 5 5 6–12344 –– Uzkonstruesim koku atpakaļ

MAIN MENU PREVIOUS NEXT Prefiksa Koda Izmantošana Ir iespēja konstruēt koku speciālā veidā, šim kokam lietot bitu kodus apzīmējumus 0 un 1 un to koku izmantot lai kodētu elementus. Neveiksmīga kodēšanas situācija: e – 0; a – 1; t – 01. Ja ir 0101, tad tos var atšifrēt tā: eat, tea, eaea. Prefiksa kods ļauj no šīs situācijas izbēgt. Prefiksa kods – binārs kods, kuru atspoguļo grafā veidā lokus pa kreisi apzīmē ar 0, labajā pusē – 1. e 1 1 s 1 1 a t n Rezultātā ir vārds sane

MAIN MENU PREVIOUS NEXT Koku Apiešana, Universāla Adrešu Sistēma Izmantojot koku apiešanu ir iespēja kompaktā veidā pierakstīt sarežģītas izteiksmes, veidot datu struktūras, noteikt izteiksmju vērtības. Universāla adrešu sistēma Veidošana ir saistīta ar procedūrām kā iziet cauri visiem koka virsotnēm, lai iegūtu pilnu sakārtojumu. Viens no veidiem – leksigrafiskais princips Ja virsotnei ir iezīme x 1... x n, tad šī virsotne ir mazāka par citu virsotni ar iezīmi y 1... y m, ja kāds i = kurā visi šīs komponentes ir vienādas x 1 = y 1, x 2 = y 2,..., x i-1 = y i-1, bet x i y i vai n < m, x i = y i, i = Saknes virsotne vienmēr ir apzīmēta ar iezīmi 0, tad ņemti virsotnes pēcteči ir: Ja vajag pievienot loku, tad pārēju virsotņu numuri nemainās.

MAIN MENU PREVIOUS NEXT Apiešanas Algoritmi Apiešanas algoritmi ļauj sistemātiski apmeklēt visas virsotnes sakārtotā kokā sākot ar sakni ( kurš attēlo universālo adrešu sistēmu ). Eksistē 3 apiešanas algoritmi: 1). tiek sameklēta koka sakne 2). tiek sameklēti visi apakškoki no kreisās puses Pirms sakārtojums TnTn r T1T1 T2T solis 2. solis3. solisn+1. solis To sauc arī par pārmeklēšanu plašumā. 1. Pirmssakārtojums 2. Iekšējs sakārtojums 3. Pēcsakārtojums

MAIN MENU PREVIOUS NEXT Apiešanas Algoritmi Piemēram, ir dots sekojošs koks: b a d e h c f gi j Vispirms jāapmeklē koka sākumvirsotni, šajā gadījumā virsotni a, pēc tam no kreisas puses jāapmeklē visus apakškokus. ab j f cd hgi 1. solis abe j fcdhgi 2. solis ab ejfcdhgi Rezultāts e

MAIN MENU PREVIOUS NEXT Apiešanas Algoritmi Iekšējs sakārtojums 1). apmeklē apakškoku, kura ir pa kreisi 2). apmeklē sakni 3). apmeklē otru apakškoku, no kreisās uz labo pusi un t.t. TnTn r T1T1 T2T solis 2. solis 3. solisn+1. solis b a d e h c f gi j ab e j f cd hg i 1. solis 2. solis Rezultāts: e j bacihgfd j ebachgifd

MAIN MENU PREVIOUS NEXT Apiešanas Algoritmi Pēcsakārtojuma apiešana 1). apmeklē visas apakškokas 2). apmeklē sakni. TnTn r T1T1 T2T solis2. solisn. solis n+1. solis b a d e h c f gi j 1. solis ab ef cd hgi j ef j bchgiad j efbchgiad 2. solis Rezultāts :

MAIN MENU PREVIOUS NEXT Apiešanas Algoritmi 2. veids kā realizēt šos algoritmus. Jāzina kā virsotnes ir ievietotas kokā b a dg i ef khj c 2). Lai iegūtu pirmssakārtojumu visas virsotnes tiek ievietotas sarakstā tikai tad, kad līkne iet gar šo virsotni pirmo reizi: a b d h e i j c f g k. 3). Lai iegūtu iekšējo sakārtojumu, strupceļa virsotnes tiek ievietotas sarakstā tad, kad līkne iet gar to virsotni pirmo reizi, bet visas iekšējas virsotnes tad, kad līkne gar tām iet otro reizi: h d b i e j a f c k g. 4). Lai iegūtu pēcsakārtojumu ievieto virsotnes saraksta tad, kad līkne gar to iet pēdējo reizi: h d i j e b f k g c a. 1). atlikām nepārtraukto linīju apkārt visām koka virsotnēm.

MAIN MENU PREVIOUS NEXT Prefiksa, Infiksa, Postfiksa Pieraksti Kā sarežģīto izteiksmi pierakstīt kā koku? Piemēram, mums ir izteiksme: lai to varētu izmantot to jāpieraksta tādā veidā: ( (x+y) 2 ) + ( (x-4) / 3) ). Tagad var konstruēt koku, bet jāievēro tas, ka strupceļa virsotnes vienmēr attēlo operandus un pārējas virsotnes – darbības. + / + 3 y 2 – 4 x x Prefiksa pierakstu iegūst lietojot šī koka pirmssakārtojuma apiešanas algoritmu: + + x y 2 / - x 4 3 Prefiksos pierakstā, operandi seko aiz operācijas zīmes – poļu pieraksts. Pretēja gadījumā nevar izskaitīt rezultātu.

MAIN MENU PREVIOUS NEXT Prefiksa, Infiksa, Postfiksa Pieraksti Piemērām, ir uzrakstīta izteiksme prefiksa pierakstā: + – * / 8 4, šo izteiksmi varam atrisināt tā: + – * / – * – – rezultāts Postfiksa pierakstu iegūst lietojot šī koka pēcsakārtojuma apiešanas algoritmu : x y + 2 x 4 – 3 / +. Piemēram, jāatrisina izteiksmi kura ir uzrakstīta postfiksa pierakstā: * – / – / / / – rezultāts Infiksa pierakstu iegūst izmantojot iekšējo apiešanu.

MAIN MENU Diskrētas struktūras datorzinātnēs Kopu Teorija Kopu Teorija Grafu Algoritmi Grafu Algoritmi Attēlojumi, Grafi un Attieksmes Attēlojumi, Grafi un Attieksmes Attieksmju datu bāzu pamatjēdzieni Attieksmju datu bāzu pamatjēdzieni Attieksmju Algebras Operācijas Attieksmju Algebras Operācijas Attieksmju Rēķini Attieksmju Rēķini Struktūrizēta Vaicājumu Valoda SQL Struktūrizēta Vaicājumu Valoda SQL Koki Attieksmes un Datu Bāzes Attieksmes un Datu Bāzes

MAIN MENU PREVIOUS NEXT Attieksmju Datu Bāzu Pamatjēzieni Datu bāze – ir datu glabātuve. Datu Bāzes Vadības Sistēmas ( DBVS) – ir speciāla programmatūra, kura nodrošina darbības ar datiem. Datu modeli: hierarhiskais, tīklveida, attieksmju (relāciju)). 70-os gados Kods ( Coad ) ieveicināja attieksmju datu modeli. Pamatā ir kāda kopa { D i1,..., D in }, pie tam apakškopa D i atbilst kādam objekta īpašībām = { D i | i i 1...i n }, kur – attieksme, kura raksturo kādu noteiktu objektu, – dekarta reizinājums. Jebkura datu bāžu sistēma sastāv no divām kopām: I – atribūtu kopa, D – domenu kopa; S ( I, D ). Katram atribūtam atbilst savs domēns. Jebkuru tabulu apraksta kortežu trijnieks: m, H ), kur m – nosaukums H – atribūtu saraksts – attieksme sh( ) = (i 1...i n ) – ir tabulas shēma, kura sastāv no atribūtiem.

MAIN MENU PREVIOUS NEXT Attieksmju Datu Bāzu Pamatjēzieni Attieksmes veido ieraksti ( tabulas rindas), laukiem ir vērtības. Jebkurš ieraksts ir kortežs. Ja vajag atrast ierakstu, tad ir jādomā par primāro atslēgu. Primāra atslēga – tāds atribūts, kurš ļauj viennozīmīgi identificēt ierakstus attiecīgajā tabulā. Nedrīkst būt vienādas atribūta vērtības. Par primāro atslēgu jāizvēlas tādu atribūtu, lai nevarētu atrast visa tabulā vienādus. Pamatgrūtība: primāra atslēga paliek arī tad primārā, ja tabulas dati mainās laikā. Var arī veidot saliktas primāras atslēgas kuri sastāv no jebkuras atribūtu kombinācijām. Vislabāk ņemt 1 atribūtu, citā gadījumā jācenšas ņemt minimālo atribūtu skaitu.

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras Attieksmju algebra definē operācijas, kuras var veikt ar tabulām. Ir 8 pamatoperācijas, pie tam 4 atbilst kopu teorijas operācijām ( jēdzieniem): apvienojums – apvieno tabulas šķēlums – šķelt tabulas starpība – vienu tabulu atņemt no otras dekarta reizinājums projekcija selekcija savienošana dalīšana Lai realizētu jebkuras darbības ar tabulām vajag 5 pilnīgi nepieciešamas operācijas: 1.apvienojums 2.starpība 3.dekarta reizinājums 4.selekcija 5.projekcija

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras Definīcija: Lai realizētu un 3. operācijas, tabulām ir jābūt saderīgam jeb savietojamām. Ir 2 tabulas, kas definē 2 attieksmes un. un ir saderīgas, ja tā ir viena un tā pati dekarta reizinājuma apakškopas. Abu tabulu virsrakstiem jābūt vienādiem un sakārtotiem vienā tai pašā secībā. m, H ) m, H ) Attieksmi attēlo tabula: ( m m, H, ) {,, \}.

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras DNODisciplīnas nosaukumsStundu skaits nedēļāAuditorija 110Ievads programmēšana4A Programmēšana14A Datoru arhitektūra3A Algoritmi un datu struktūras3A Diskrētā matemātika4A Operētājsistēmas3A7-307 Datu Bāze Disciplīnas Pasniedzēja vārdsDNOKabinets Bērziņš110A Bērziņš240A Kociņš210A7-333 Bērziņš310A Krūmiņš440A9-212 Zariņš310A9-403 Pasniedzēji DNOStudenta vārdsStudenta numursAtzīme 110Jānis Ābele Daina Sīmane Kristīne Liepa Jānis Ābele Juris Kalns Kārlis Bērzs Dace Egle Pēteris Putniņš Edgars Liepiņš54488 Atzīmes

MAIN MENU PREVIOUS NEXT DNOStudenta vārdsStudenta numursAtzīme 110Jānis Ābele Dita Karkliņa Kristīne Liepa Jānis Ābele Dita Karkliņa Andris Bērziņš Andris Bērziņš Kristīne Liepa Andris Bērziņš53386 Atzīmes 1 DNODisciplīnas nosaukumsStundu skaits nedēļāAuditorija 112Pprogrammēšanas valodas3A Programmēšana 14A Programmēšana 24A Algoritmi un datu struktūras3A Pprogrammēšanas valodas MI3A Disciplīnas 1 Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras Disciplīnas Disciplīnas1 Rezultāts: tabula (Disciplīnas Disciplīnas1), Virsraksts: DNO, Disciplīnas nosaukums, Stundu skaits nedēļā, Auditorija Ierakstu skaits: 9 (visi-kopīgie ieraksti : 11-2=9). 2). Šķēlums Disciplīnas Disciplīnas1 Rezultāts: tabula (Disciplīnas Disciplīnas1), Virsraksts: DNO, Disciplīnas nosaukums, Stundu skaits nedēļā, Auditorija Ierakstu skaits: 2 – kopīgie ieraksti. 3). Starpība Disciplīnas \ Disciplīnas1 Virsraksts: DNO, Disciplīnas nosaukums, Stundu skaits nedēļā, Auditorija Ierakstu skaits: 4 (Disciplīnas – kopīgie ieraksti: 6–2=4). 1). Apvienojums

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras 4). Dekarta reizinājums Ja ir 2 tabulas, kas definē un, tad par sauc tabulu, kuru iegūst, ņemot visus doto tabulu atribūtus, kuri veido dekarta reizinājuma virsrakstus un ierakstus šajā tabulā iegūst pēc dekarta reizinājuma definīcijas. Disciplīnas Disciplīnas1 Virsrakstu skaits: 8 Ierakstu skaits: 30 ( 6 5=30 ) DNO……… ……… 110Ievads Programmēšanā 4A Programmēša nas valodas 3A9-208 Disciplīnas Disciplīnas 1 Dekarta reizinājuma tabula satur pirmās un otrās tabulas atribūtus.

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras 5). Projekcija Projekcija ( P ) attēlo n-vietīgu kortežu uz m-vietīgu. P i1, P i2,…P im, (a 1, …,a n ) (a i1,…,a im ), kur m n Ar projekciju varam izslēgt ārā nevajadzīgus atribūtus. P DNO, Dt.sk. ned. (Disciplīnas) P 1, 3 (Disciplīnas) Rezultātā ir tabula ar 2 atribūtiem un 6 ierakstiem P 3, 4, 1, 2 (Disciplīnas) Piemēram: 6). Selekcija Ja dota, tad Sel F ( ). Galveno lomu spēle formula, kura saka, pēc kādiem principiem tas jādara.

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras 2). Formulu veido aritmētiskas salīdzināšanas operācijas: =,,,,. Sel St. sk. ned. > 3 (Disciplīnas) 1). Sel Stud.vārds=Ābele (Atzīmes) { Kolonas nosaukuma vietā var lietot kolonas numuru.} Selekciju var uzdot trijos veidos : 3). Formulu var veidot loģiskas operācijas: UN, VAI, NE. Sel Pasn. vārds=Berziņš OR Pasn. vārds=Kalniņš (Pasniedzēji). Rezultātā, tabulā paliek tikai interesējošie ieraksti. 7). Savienošana Jp (R,S) kur pm, pn, p – atribūtu skaits, m,n – pakāpes. Ir attieksme ar pakāpi m+n–p (t.i. atribūtu skaits), kas sastāv no visiem ierakstiem ( a 1, a 2,..., a m–p, c 1, c 2,..., c p,..., b 1,...b n–p ) S R Lai varētu savienot tabulas atribūti jāizvieto tā, lai tie atrodas beigās.

MAIN MENU PREVIOUS NEXT Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras Disciplīnas Pasniedzēji. Šajās tabulās ir kopīgs atribūts – DNO J 1 (Disciplīnas, Pasniedzēji) Ir jāuztaisa projekcija, lai DNO iegūtu tabulas beigās. Jāprojicē abas tabulas. P 2,3,4,1 (Disciplīnas) P 2,1,3 (Pasniedzēji) Disciplīnas nosaukums Stundu skaits nedēļā AuditorijaDNOPasniedzēja vārds Kabinets Ievads programmēšanā 4A11–410110BērziņšA11–401 Programmēšana14A7–310210KociņšA7–333

MAIN MENU PREVIOUS NEXT Pieņemsim, ka dalāmais (tabula, kuru grib dalīt) ir divvietīga attieksme, bet dalītājs ir vienvietīga attieksme. atribūti ir i 1 un i 2, atribūts ir j, pie tam, tas ir definēts šajā pašā domēnā, kurā ir atribūts i 2. Rezultāts \ ir vērtību kopa, pie tam atbilstoša atribūta i 2 vērtības sakrīt ar visām j vērtībām. 8) Dalīšana i1i1 i2i2 i1i1 i1i1 RSR \ S Attieksmju Algebras Operācijas Un Tabulu Izskaitļošnas Procedūras

MAIN MENU PREVIOUS NEXT Attieksmju Rēķini Un Vaicājumu Formēšana Pseidokodā Vaicājumu valoda pamatojas uz: attieksmju algebra attieksmju rēķini. 1. Attieksmju algebra 1s. Noteikt kurās tabulās ir vajadzīga informācija 2s. Dekarta reizinājums 3s. Selekcija1. selekcija 2. selekcija projekcija Šo procedūru sauc par tabulas izskaitļošanu.

MAIN MENU PREVIOUS NEXT Piemēram, jāatrod pasniedzēja vārdu, kurš pasniedz studentiem disciplīnu 4 stundas nedēļā. T1:= Disciplīnas Pasniedzēji Atzīmes T2:= Sel D. DNO=P. DNO= A. DNO (T1) T3:= Sel St. sk. ned.=4 & St. vārds=Ābele (T2) T4:= P Pasn.vārds (T3) Disciplīnas, Pasniedzēji, Atzīmes T1:= Disciplīnas DNO=DNO Pasniedzēji DNO=DNO Atzīmes T2:= Sel St. sk. ned.=4 & St. vārds=Ābele (T1) T3:= P Pasn.vārds (T2). Attieksmju Rēķini Un Vaicājumu Formēšana Pseidokodā

MAIN MENU PREVIOUS NEXT Piemērs 2, jāatrod pasniedzēju pāri, kuri pasniedz vienu un to pašu disciplīnu. Lai to izdarītu ir vajadzīga tikai 1 tabula ( Pasniedzēji ) un 2 atribūti. T2:= P P. vārds, DNO (Pasniedzēji) T2:= T 1 ( lai strādāt ar 2 tabulām) T3:= T 1 T 2 T4:= Sel T1.DNO=T2.DNO (T3) T5:= P T1 Pasn.vārds, T2 Pasn. vārds (T4) T6:= Sel T1 Pasn.vārds = T2 Pasn. vārds (T5). Attieksmju Rēķini Un Vaicājumu Formēšana Pseidokodā

MAIN MENU PREVIOUS NEXT 2. Attieksmju rēķini Attieksmju rēķini pamatojas uz predikātu rēķiniem. Ļauj konstruēt valodas manipulēšanai ar datiem, līdzīgi kā attieksmju algebrā, bet lietotājam ir ērtāk strādāt ar valodām uz predikātu pamatā, jo lietotājam nav jārūpējas par to kādā kārtība un kādā veidā sistēma apstrādās tabulas, lai iegūt vajadzīgo rezultātu. Ir 2 tipu valodas: 1.mainīgie korteži 2.mainīgie domenes. Attieksmju rēķini valodās kas izmanto mainīgus kortežus tiek konstruētas formulas, kas sastāv no termiem un aritmētiskām kā arī loģiskām operācijām. Saīsināti šādas formulas var pierakstīt šādi: {t | F (t)}, kur t – kortežu kopa, F(t) – formula, kuras vērtības ir patiesas. Attieksmju Rēķini Un Vaicājumu Formēšana Pseidokodā

MAIN MENU PREVIOUS NEXT Termi var būt 3 tipi: 1. R (t) t R 2. s.i u.j, kur s – mainīgie, u – korteži, i,j – vai nu atribūtu numuri, vai nu atribūtu nosaukumi, – aritmētiskā salīdzināšanas operators (, >=...) 3. s.i a, kur a – konstante. divi pieraksta veidi, kur t – korteži, R – attieksme. Pareizi konstruētas formulas Ja G 1 un G 2 ir pareizi konstruētas formulas, tad G 1 &G 2, G 1 G 2, G 1, G 2 arī ir pareizi konstruētas formulas. Ja G 1 ir pareizi konstruēta formula, tad s(G 1 ) un (G 1 ) arī ir pareizi konstruētas formulas. Attieksmju rēķini ar domēnu mainīgiem izmantošanas gadījumā tiek veidotas izteiksmes, kas izskatās šādi: {V| F(V)}, kur V – ir domēnes {i 1,...,i n | F( i 1,...,i n )}. Ir daudz reālo valodu, kas izmanto šīs teorijas, piemēram, valoda QBE (Query By Example), izmanto vairākas datu bāzes veidošanas sistēmās; Attieksmju Rēķini Un Vaicājumu Formēšana Pseidokodā

MAIN MENU PREVIOUS NEXT Pseidokods. 1. IEGŪT R( ): L, kur R – attieksme, L –izteiksme. 2. x R, kur x – kortežs. Piemēram, mūs interesē disciplīnas kodi, kuri notiek 419 auditorijā un kurām stundu skaits nedēļa ir lielāks par 3. IEGŪ R ( Disciplīnas. DNO): Disciplīnas. Auditorija = A11– 419 & Disciplīnas. Stundu skaits nedēļā >3. Vispirms sistēma atrod tabulu Disciplīnas, pēc tam veic selekciju un projicē, rezultātā būs tabula ar 1 virsrakstu ( DNO) un 3 ierakstiem. Piemērs, jāatrod disciplīnas nosaukumus, kurus lasa Bērziņš. IEGŪT DN (Disciplīnas. Disciplīnas nosaukums): x (x Pasniedzēji & x.Pasniedzēja vārds = Bērziņš & x. DNO = Disciplīnas. DNO). Attieksmju Rēķini Un Vaicājumu Formēšana Pseidokodā

MAIN MENU PREVIOUS NEXT Piemērs, atrast atzīmes, priekšmetā, kam ir 4 stundas nedēļā un kuru pasniedz Bērziņš. IEGŪT ATZ ( Atzīmes. Atzīme): x (x Disciplīnas & x. Stundu skaits nedēļā = 4 & x.DNO = Disciplīnas DNO) & y (y Pasniedzēji & y. DNO = x. DNO & y. Pasniedzēja vārds = Bērziņš. Attieksmju Rēķini Un Vaicājumu Formēšana Pseidokodā

MAIN MENU PREVIOUS NEXT Strukturizēta Vaicājumu Valoda SQL 1. Datu definēšana operatori ļauj definēt gan datus, gan tabulas, gan pašu datu bāzi 2. Datu pārvaldība ( datu menedžments) ļauj organizēt datu ievadu, koriģēšanu, datu atjaunošanu un izslēgšanu 3. Vaicājumi specificē konkrēti, ko mēs gribam datu bāzē atrast. CREATE DataBase ( DB vārds) CREATE TABLE ( Attieksmes vārds ) ( Atribūtu vārdi ) ( Datu tipi: ) Datu tipi var būt skaitliski ( integer, number), simboliski ( character, char). 1. Datu definēšana

MAIN MENU PREVIOUS NEXT Strukturizēta Vaicājumu Valoda SQL Piemērs: CREATE TABLE Pasniedzēji ( Pasniedzēja vārds, char(40) DNO, integer (4) Kabinets, char (7)) 2. Datu pārvaldība datu ievade INSERT INTO m (i 1,..., i n ), VALUES ( v 1,..., v n ) kur m – ir tabulas vārds, i 1,..., i n – atribūti INSERT INTO Pasniedzēji (Pasniedzēja vārds, DNO, Kabinets) VALUES (Bērziņš, 110, A11–401)..... Piemērs:

MAIN MENU PREVIOUS NEXT Strukturizēta Vaicājumu Valoda SQL datu izslēgšana DELETE FROM m WHERE c c – nosacījums. UPDATE m i 1 =l 1, i 2 =l 2,..., i n =l n. i – veca vērtība l – jauna vērtība atjaunošana 3. Vaicājumu formēšana SELECT [ distinct / unique ] (atribūtu skaits) FROM T WHERE C T– tabulas C – nosacījums UNION apvieno 2 vaicājumus. GROUP BY grupē tabulu ORDER BY sakārto datus. jāraksta tikai pēc WHERE Izmantojamas Funkcijas: sum – summa; max – maksimālais elements; min – minimālais elements; count – ierakstu skaits.

MAIN MENU PREVIOUS NEXT Strukturizēta Vaicājumu Valoda SQL Piemērs: SELECT DNO FROM Disciplīnas WHERE Stundu skaits nedēļā = 4 UNION SELECT DNO FROM Pasniedzēji WHERE Pasniedzēja vārds = Zariņš. Sistēma izdos rezultātu ar DNO kuram ir 4 stundas nedēļā, kuras pasniedz Zariņš. SELECT Studenta vārds FROM Atzīmes WHERE Atzīme > 4 GROUP BY Studenta vārds. Sistēma sagrupēs tabulu Atzīmes pēc studenta vārdiem. Piemērs:

MAIN MENU PREVIOUS NEXT Strukturizēta Vaicājumu Valoda SQL Piemērs: SELECT * FROM Atzīmes WHERE DNO = 210 ORDER BY Atzīmes. Ieraksti tiks sakārtoti secībā pēc atzīmēm