Sākums
n/a
Diskrētās struktūras datorzinātnē
 
Pasniedzējs: 
Lietotāja Jānis Grundspeņķis attēls
Jānis Grundspeņķis

DSD mācību materiāls

Uzdevumu risinājumu piemēri

Īsākā ceļa atrašana ar Deikstras algoritmu (.pps)

Minimālā karkasa atrašana ar Prima algoritmu (.pps)

Prima un Kraskāla algoritmu salīdzinājums (.pps)

Koku apiešana (pirmssakārtojums, pēcsakārtojums, iekšējais sakārtojums) (.pps)

Matemātiskas izteiksmes prefiksa, postfiksa un infiksa formu iegūšana un vērtību aprēķināšana (.pps)

Maksimālās plūsmas atrašana tīklā ar Forda-Falkersona algoritmu (.pps)

Eksāmena jautājumi

Eksāmens sastāv no teorētiskās un praktiskās daļas.

Tipiska teorētiskās daļas struktūra:

1. bloks - attieksmes:

Šī bloka jautājumi:

1.1. Kopu Dekarta reizinājums, bināras attieksmes un to īpašības (refleksivitāte, antirefleksivitāte, simetrija, asimetrija, antisimetrija, tranzitivitāte, antitranzitivitāte).

1.2. Ekvivalences attieksme, kopu sadalījums un pārklājums.

1.3. Sakārtojuma attieksme un tās veidi (pilns, daļējs, stingrs, nestingrs sakārtojums). Leksikografiskais princips.

1.4. Elementu salīdzināšana sakārtotās kopās (mažorante, minorante, maksimālais un minimālais elements, suprēms, infims).

2. bloks - attēlojumi, grafi un attieksmes.

 Šī bloka jautājumi:

2.1. Attēlojuma jēdziens, tā grafiks un piekārtojums. Attēlojumiem atbilstošie grafi.

2.2.Attēlojumu veidi (attēlojums kopā, uz kopu, pilns, daļējs, funkcionāls, sirjekcija, injekcija, bijekcija).  Attēlojumu kompozīcija.

3. bloks - grafu algoritmi.

Šī bloka jautājumi:

3.1. Informācijas par grafu uzdošanas statiskie un dinamiskie veidi.

3.2. Ceļu meklēšanas pamatprocedūras grafos (backtrack, pārmeklēšana dziļumā un plašumā).

3.3. Topoloģiskās šķirošanas, Deijkstras, Floida, Prima, Kraskala un Forda-Falkersona algoritmu būtība un pamatidejas. Forda-Falkersona teorēma. Plūsmas saglabāšanas vienādojums.

4. bloks - koki.

Šī bloka jautājumi:

4.1. Koki, karkasi un īsākie karkasi.

4.2. Koki kā problēmu risināšanas modeļi (lēmumu koki, spēles, šķirošana apvienojot, prefiksa kodu iegūšana).

4.3. Koku apiešana ( universālās adresu sistēmas, prefiksa, infiksa un postfiksa pieraksti to iegūšana un aprēķins).

5. bloks - attieksmes un datu bāzes.

Šī bloka jautājumi:

5.1. Attieksmju datu bāzu pamatjēdzieni.

5.2. Attieksmju algebras operācijas un tabulu izskaitļošanas procedūras.

5.3. Attieksmju rēķini un vaicājumu formēšana pseidokodā.

5.4. Strukturizēta vaicājumu valoda SQL (datu definēšana, datu pārvaldība - INSERT, DELETE, UPDATE, vaicājumu formulēšana - SELECT, UNION, subSELECT, aritmētiskie operātori sum, avg, max, min, COUNT, agregatizētie operātori - GROUP BY, HAVING, ORDER BY.

 

Papildjautājumi   (jāatbild vienīgi pretendējot uz atzīmi " 10" ):

1. Eilera, Hamiltona, plakani un divdaļīgi grafi.

2. Loku savienojumu un attālumu matricas un to iegūšana.

3. Forda algoritms īsāko ceļu atrašanai.

4. Izplūdušas attieksmes un grafi.

5. Semantiskie tīkli un konceptuālie grafi.

Literatūra papildjautājumu apgūšanai:

J. Grundspeņķis. Grafu teorijas pamati, Rīga, RPI, 1976.

J. Grundspeņķis. Ievads intelektuālās sistēmās, Rīga, RTU, 1993.

А. Кофман. Введение в теории нечетких множеств. М. Радио и связью 1982.

Н. Кристофидес. Теория графов. Алгоритмический подход. М. Мир. 1978.

Eksāmena teorētiskajā daļā studentam ir jāatbild uz 9 jautājumiem (pēc izvēles) no piedāvātajiem 15. Pretendējot uz atzīmi "8", "9" vai "10", obligāti ir jāievēro prasība, ka ir jāatbild vismaz pa vienam jautājumam no 1., 2. un 3. bloka un vismaz pa 2 jautājumiem no 4. un 5. bloka.

Katrā blokā tiek piedāvāti 3 jautājumi, kas atkarībā no to grūtības pakāpes tiek vērtēti ar 1, 2 vai 3 punktiem. Atzīme eksāmena teorētiskajā daļā tiek izlikta atkarībā no  summārā punktu skaita pēc šādas skalas:

Atzīme

Minimālā punktu summa

10

21

9

19

8

17

7

15

6

13

5

11

4

9

3

5

2

2

1

0

Eksāmena praktiskās daļas struktūra:

1. bloks - Deijkstras, Prima vai Forda-Falkersona algoritms.

2. bloks - attieksmes un datu bāzes.

2a) attieksmju algebras operācijas.

2b) vaicājumu formulēšana attieksmju rēķinos, lietojot pseidokodu.

2c) tabulu izskaitļošanas procedūras.

2d) SQL lietojumi.

Praktiskās daļas vērtēšanas pamatprincipi:

Katrs uzdevums tiek vērtēts šādi:

1. bloks - 4 punkti; 2. bloks - 6 punkti (2a - 2 p., 2b - 1p., 2c - 2 p., 2 d - 1 p.).

Kopējais praktiskās daļas vērtējums atbilst iegūtajai punktu summai.

Kopumā studenta zināšanas priekšmetā tiek vērtētas ar vidējo svērto atzīmi, ko veido:

1. Eksāmena teorētiskajā daļā iegūtā atzīme - 65%

2. Eksāmena praktiskajā daļā iegūtā atzīme  - 35%