| Title: | Primeri uporabe pregleda grafov v globino : na študijskem programu 2. stopnje Matematika |
|---|
| Authors: | ID Galun, Maša (Author)
ID Taranenko, Andrej (Mentor) More about this mentor...  |
|---|
| Files: |  MAG_Galun_Masa_2025.pdf (512,75 KB)
MD5: BE2456D079BA8A71C54BAC5BC5A44186
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Master's thesis/paper |
|---|
| Typology: | 2.09 - Master's Thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | V magistrski nalogi predstavimo različne algoritme, ki temeljijo na pregledu grafov v globino (DFS). Delovanje DFS algoritma prikažemo na problemih iz teorije grafov in teorije iger. Predstavimo osnovne pojme teorije grafov in analiziramo delovanje ter časovno zahtevnost DFS algoritma.Definiramo pojem krepke povezanosti in krepko povezanih komponent. Obravnavamo dva algoritma za iskanje krepko povezanih komponent v usmerjenih grafih (Kosaraju-Sharirjev in Tarjanov algoritem), ki ju implementiramo v programskem jeziku Python. V zadnjem poglavju preučujemo uporabo DFS algoritma v teoriji iger. Predstavimo minimax algoritem, ki se uporablja za določanje optimalne poteze v igrah z dvema igralcema in ga optimiziramo z alfa-beta obrezovanjem. Predstavljeno implementiramo v programskem jeziku Python, kjer analiziramo delovanje algoritmov na primeru igre križci in krožci. |
|---|
| Keywords: | DFS, krepka povezanost, Tarjanov algoritem, Kosaraju-Sharirjev algoritem, minimax, alfa-beta obrezovanje, teorija iger, Python. |
|---|
| Place of publishing: | Maribor |
|---|
| Place of performance: | Maribor |
|---|
| Publisher: | [M. Galun] |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | VIII, 51 f. |
|---|
| PID: | 20.500.12556/DKUM-93223 |
|---|
| UDC: | 519.17(043.2) |
|---|
| COBISS.SI-ID: | 242077187 |
|---|
| Publication date in DKUM: | 10.07.2025 |
|---|
| Views: | 213 |
|---|
| Downloads: | 112 |
|---|
| Metadata: |    |
|---|
| Categories: | FNM
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
