-
Ekvivalences attieksme, Deikstras algoritms
Nr. | Chapter | Page. |
1. | UZDEVUMA NOSTĀDNE | 4 |
2. | TEORĒTISKAIS PAMATOJUMS | 5 |
2.1. | DEIKSTRAS ALGORITMS | 5 |
2.1.1. | Grafi | 5 |
2.1.2. | Blakus virsotņu matrica | 5 |
2.1.3. | Ceļš | 6 |
2.2. | ATTIEKSMES UN TO ĪPAŠĪBAS | 8 |
2.2.1. | Attieksmju pamatjēdzieni | 8 |
2.2.2. | Attieksmju īpašības | 8 |
2.2.3. | Ekvivalences attieksme | 9 |
3. | PASKAIDROJUMI PROGRAMMAS LIETOTĀJAM | 9 |
3.1. | EKVIVALENCES ATTIEKSME | 9 |
3.1.1. | Darba uzsākšana | 9 |
3.1.2. | Ievades datu forma | 9 |
3.1.3. | Izvades datu forma | 10 |
3.2. | DEJKSTRAS ALGORITMS | 11 |
3.2.1. | Darba uzsākšana | 11 |
3.2.2. | Ievades datu forma | 11 |
3.1.3. | Izvades datu forma | 12 |
4. | KONTROLPIEMĒRA ANALĪZE | 13 |
4.1. | EKVIVALENCES ATTIEKSME | 13 |
4.2. | DEIKSTRAS ALGORITMS | 14 |
SECINĀJUMI | 16 | |
PIELIKUMS | 17 | |
IZMANTOTĀ LITERATŪRA | 18 |
1. UZDEVUMA NOSTĀDNE
38. variants
Variants ietver 2 uzdevumus. Katra uzdevuma atrisināšanai jāizstrādā programma, kas veic datu ievadi prasītajā formā, atrisina uzdevumu un izvada rezultātu.
Uzdevumi:
1) Galīgā kopā A = {a,#,2,y,3} tiek uzdota attieksme R; to uzdot ar matricu. Pēc matricas ievades parādīt atbilstošo kortežu sarakstu.Noteikt vai dotā attieksme ir ekvivalence,( dot atbildi par visām 3.attieksmēm).
2) Deikstras algoritma realizācija – atrast īsāko ceļu grafā. Jābūt iespējai izvēlēties ceļu sākuma un beigu virsotnes. Grafu ievada ar blakus virsotņu matricu( 1 vietā ievada loka svarus), grafa virsotņu skaits n:9
2. TEORĒTISKAIS PAMATOJUMS
2.1. DEIKSTRAS ALGORITMS
2.1.1. Grafi
Grafs ir matemātisks objekts. Tā apzīmēšanai izmanto burtu G. Tas sastāv no divām kopām – V un Q. Kopa V ir grafa virsotņu kopa. Tajā iekļautas visas apskatāmā grafa virsotnes. Kopa Q ir grafa virsotņu pāru kopa jeb loku vai šķautņu kopa. Tātad grafa pilns apzīmējums ir G(V,Q).
Zīmējot grafu, virsotnes zīmē kā apļus, bet lokus zīmē kā līnijas vai bultas starp virsotņu, kuras tas savieno, apļiem.
Pastāv divi galvenie grafu veidi – neorientēts un orientēts.
Neorientētā grafā nav svarīgi, kura virsotne katram lokam ir pirmā un kura otrā – loku zīmē kā līniju un kopas Q elementi ir nesakārtoti virsotņu pāri.
Orientētā grafā ir svarīgi, kura virsotne katram lokam ir pirmā un kura otrā – loku zīmē kā bultu no pirmās virsotnes uz otro un kopas Q elementi ir sakārtoti virsotņu pāri.
…
Ekvivalences attieksme, Deikstras algoritms Šis studiju darbs ir studiju darbs mācību priekšmetā “Diskrētās struktūras datorzinātnēs”. Šajā darbā ir apskatītas divas tēmas: • attieksmes un to speciālie veidi (ekvivalence); • grafi, Deikstras algoritms. Šī darba izstrādes procesā sagatavotas divas MS DOS videi paredzētas programmas, ar kuru palīdzību tiek realizēta studiju darba praktiskā puse.