Dopolnilno izobraževanje iz računalništva in informatike

Iz MaFiRaWiki

(Preusmerjeno iz DIRI)

Vsebina

Osnovni podatki

Seminarska naloga

Navodila

Pregled nad svojimi prispevki

Vse svoje prispevke lahko vidiš na strani Posebno:Contributions/UporabniskoIme (zamenjaj UporabniskoIme s tvojim uporabniškim imenom). Lahko tudi klikneš na povezavo Moji prispevki v skrajnem desnem zgornjem kotu spletne strani.

Gumb Prikaži predogled

Pred shranjevanjem strani uporabi gumb >>Prikaži predogled<<, ki bo prikazal stran tako, kot bo izgledala, ko jo boš shranil. Shrani pa jo šele tedaj, ko boš zadovoljen z njenim izgledom. (Tako prihraniš muke tistim, ki gledajo zgodovino sprememb na strani in na celotnem wikiju.)

Sodelovanje z ostalimi

Sodeluj z ostalimi na wikiju, tudi če niso tvoji sošolci. Razmisli, kako se tvoje prispevke najbolje vključi v wiki.

Svoje izdelke poveži s to stranjo (v ustreznih rubrikah spodaj), prav tako pa svoje članke dodaj v ustrezne kategorije. Svoj članek poveži z ostalimi članki na wikiju (povezave se naredi z dvojnim oglatim oklepajem), kjer je to smiselno.

Predvsem ne podvajaj že obstoječih člankov. Najprej preveri, ali članek že obstaja in če ga najdeš (ali če te kasneje kdo opozori nanj), ga izboljšaj in ne piši svoje ločene verzije: dodaj slike ali diagrame, prikaži izvorno kodo, dopiši zgodovino, dodatne obrazložitve, poišči zunanje povezave na isto gradivo in jih dodaj v članek, ipd.

Uporabi že narejene vzorce

Na začetku strani dodaj vzorec {{Student|tvoje uporabniško ime|predmet}} (beseda Student naj ostane, ostalo pa ustrezno spremeni), tako da bodo drugi vedeli, da si to stran napisal v okviru določenega predmeta in je zato ne bodo popravljali (uporabo vzorca lahko preizkusiš v peskovniku).

S klikom na tvoje uporabniško ime naj bi ostali prišli do tvoje osebne strani, s klikom na predmet pa do te strani, zato pazi na pravilnost vnosa teh podatkov.

Prikazovanje izvorne kode

Namesto ukazov <code> in <pre> lahko za lepši prikaz kode uporabljaš ukaze, ki ti kodo obarvajo, oštevilčijo vrstice itd. Če pišeš npr. v javi, uporabi kar ukaz <java> pred kodo in ukaz </java> za njo. Če ne želiš številčenja kode (npr. če je le ena vrstica), pa uporabi ukaza <java-simple> oz. </java-simple>. Več o ukazih za ostale programske jezike pa je na strani o pomoči.

Piši in beri pogovorne strani

Komentiraj ostale prispevke na pogovornih straneh. S tem sošolcem in ostalim pomagaš, saj jih opozarjaš na napake, in nejastnosti ter predlagaš izboljšave. Vedno bodi vljuden in spoštljiv, čeprav se ti morda zdi prispevek površen ali napačen.

Beri pogovorne strani svojih prispevkov. Ostali člani wikija bodo tvoj prispevek komentirali na pogovorni strani. Njihove pripombe vzemi v pozitivnem duhu (tudi če niso tako napisane), saj ti bo to pomagalo izboljšati prispevke.

Programski pojmi

V spodnji seznam vpisujte pojme iz področja programiranja. Pojmi naj bodo urejeni po abecednem vrstnem redu.

Izpitna vprašanja


V spodnji seznam, ki je urejen po zaporednih številkah, dodaj svoj odgovor. Naslov tvojega odgovora naj bo oblike Izpitno vprašanje DIRI2005 #številka, članek pa naj ima enako obliko kot že pripravljen odgovor Izpitno vprašanje DIRI2005 6500. Potem v seznamu vprašanj za DIRI 05/06 (glej spodaj) poišči ustrezno vprašanje in mu dodaj referenco na tvoj (kot je pri vpr. 5900 <==> vpr. 18)

Zaželeno je, da skopiraš že narejeni odgovor in ga prirediš.

Izpitna vprašanja 05/06

Vprašanjem dodaj ustrezno referenco na SPLOŠNO izpitno vprašanje (glej npr. Vprašanje 18!)

  1. Ugotovi in primerjaj časovno in prostorsko zahtevnost dveh algoritmov za izračun potence števila: z zaporednim množenjem in z razpolavljanjem.
  2. Zapiši algoritem za metodo, ki sprejme kot parameter seznam nizov in vrne črko, ki se v teh nizih največkrat pojavi.
    a. Kaj v tem primeru predstavlja velikost problema?
    b. Zapiši algoritem v Javi.
    c. Oceni njegovo prostorsko in časovno zahtevnost.
    d. Denimo, da na voljo nima več dodatnega spomina kot za pet spremenljivk tipa int. Ali znaš popraviti algoritem tako, da bo to upošteval? Kakšni sta časovna in prostorska zahtevnost novega algoritma?
  3. Razloži vsaj dva algoritma za izračun maksimalne vsote podzaporedja v zaporedju celih števil.
  4. Razloži, kako bi poiskal VSA podzaporedja z maksimalno vsoto.
  5. Primerjaj časovni zahtevnosti algoritma za iskanje v neurejenem zaporedju in z bisekcijo v urejenem zaporedju. Pokaži najboljši in najslabši primer.
  6. Izpitno vprašanje DIRI2005 3700 Dana sta dva algoritma. Prvi je časovne zahtevnosti O(n), drugi pa O(n2). Kaj lahko poveš o času izvajanja algoritmov na istem računalniku in na istih problemih.
  7. Kaj pomeni časovna in kaj prostorska zahtevnost algortma? Kaj nam ta informacija sploh pove?
  8. Naštej nekaj podatkovnih struktur in na kratko opiši njihove osnovne značilnosti.
  9. Izpitno vprašanje DIRI2005 4200 Formalno opiši podatkovno strukturo sklad.
  10. Izpitno vprašanje DIRI2005 4400 Imamo dva sklada, v katerih so elementi urejeni naraščajoče (prvi element v skladu je najmanjši). Sestavi algoritem, ki s pomočjo osnovnih operacij nad skladom sestavi nov sklad, kjer so elementi (iz prvih dveh skladov) urejeni prav tako naraščajoče.
  11. Opiši, kako bi sklad predstavil v Javi.
  12. Izpitno vprašanje DIRI2005 4600 Predstavitev sklada s pomočjo tabele.
  13. Predstavitev sklada z linearnim seznamom.
  14. Izpitno vprašanje DIRI2005 5200 S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani n-ti element.
  15. Izpitno vprašanje DIRI2005 5300 S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani najmanjši element. Če jih je več, odstrani tistega, ki je v skladu najdlje.
  16. Problem postajenačelnika.
  17. Zlivanje s pomočjo sklada.
  18. Izpitno vprašanje DIRI2005 5900 S pomočjo osnovnih operacij nad skladom iz danega sklada števil odstrani vsa soda števila.
  19. Dana sta dva nepadajoče urejena sklada. Sestavi metodo, ki vrne nepadajoče urejen sklad iz elementov, ki so v obeh skladih.
  20. Izpitno vprašanje DIRI2005 6100 Dan je nepadajoče urejen sklad. S pomočjo osnovnih operacij izbriši vse podvojene elemente.
  21. Preveri, če so v danem izrazu oklepaji postavljeni pravilno. V izrazu lahko nastopajo ( in [ oklepaji. Vsak predklepaj mora imeti zaklepaj, prav tako pa morajo biti oklepaji pravilno gnezdeni. Izraz je dan kot niz, na voljo pa je sklad, v katerem lahko hranimo znake. Tako v [a(b(]b]bb fbf] oklepaji niso, v [a(b()b)b[b f]bf] pa so postavljeni pravilno.
  22. Iz danega sklada naredi dva sklada. V prvem naj bodo liha v drugem pa soda števila iz prvega sklada.
  23. Sestavi algoritem, ki zlije dve urejeni zaporedji predstavljeni v linearnem seznamu. Pri tem ne prestavljaj elementov.
  24. Sestavi algoritem, ki vstavi nov element na začetek dvojno povezanega seznama, podanega s kazalcema na začetek in konec.
  25. Sestavi algoritem, ki na ustrezno mesto vstavi nov element v urejeni linearni seznam.
  26. Sestavi algoritem, ki iz linearnega seznama, v katerem hranimo cela števila, naredi dva seznama. V prvem so liha števila in v drugem soda števila. Pri tem ne smeš narediti prelagati elementov!
  27. Sestavi algoritem, ki izračuna povprečno dolžino besed, ki jih hranimo v enojno povezanem linearnem seznamu.
  28. Sestavi algoritem, ki vrne kazalec na element linearnega seznama v katerem je najdaljša beseda.
  29. Sestavi algoritem, ki določi, katera sta zadnja preostala elementa krožnega seznama, če izločamo vsak tretji element.
  30. Odstrani podatek iz enojno povezanega linearnega seznama.
  31. Predstavitev enojno povezanega linearnega seznama v Javi.
  32. Izpitno vprašanje DIRI2005 7500 Formalno opiši podatkovno strukturo vrsta.
  33. S pomočjo osnovnih operacij nad vrsto in skladom obrni vrstni red elementov v skladu.
  34. Izpitno vprašanje DIRI2005 7900 S pomočjo osnovnih operacij nad vrsto iz vrste odstrani n-ti element.
  35. Razloži, kako bi lahko vrsto predstavil s pomočjo tabele in opiši osnovne algoritme.
  36. Izpitno vprašanje DIRI2005 8000 Sestavi algoritem, ki z osnovnimi operacijami nad vrsto pove, kateri je n-ti element vrste (če obstaja).
  37. Imamo dve vrsti, v katerih so elementi urejeni naraščajoče. Sestavi algoritem, ki s pomočjo osnovnih operacij nad vrsto sestavi novo vrsto, kjer so elementi (iz prvih dveh vrst) urejeni prav tako naraščajoče.
  38. Imamo dva sklada, v katerih so elementi urejeni naraščajoče (oziroma pravilneje - nepadajoče). Sestavi algoritem, ki s pomočjo osnovnih operacij nad vrsto in skladom sestavi novo vrsto, kjer so elementi (iz prvih dveh skladov) urejeni prav tako naraščajoče.
  39. Imamo dva sklada, v katerih so elementi urejeni naraščajoče (prvi element v skladu je najmanjši). Sestavi algoritem, ki s pomočjo osnovnih operacij nad skladom sestavi nov sklad, kjer so elementi (iz prvih dveh skladov) urejeni prav tako naraščajoče.
  40. Algoritem, ki izpiše podatke iz enojno povezanega linearnega seznama.
  41. Algoritem, ki odstrani vsak drugi element iz dvono povezanega linearnega seznama.
  42. Formalno opiši podatkovno strukturo dvojiško drevo.
  43. Pregledi dvojiškega drevesa. Opiši in na praktičnem primeru izvedi.
  44. Sestavi algoritem, s katerim iz premega in vmesnega vrstnega reda rekonstruiraš drevo.
  45. Sestavi algoritem, s katerim iz obratnega in vmesnega vrstnega reda rekonstruiraš drevo.
  46. Sestavi algoritem, s katerim ugotoviš višino dvojiškega drevesa. Uporabi le osnovne operacije nad drevesom.
  47. V dvojiškem drevesu hranimo cela števila. Sestavi algoritem, s katerim izračunaš povprečno vrednost elementov v drevesu.
  48. V dvojiškem drevesu hranimo cela števila. Naj bo vsota poti do lista enaka vsoti elementov, ki jih prehodimo od korena do lista. Sestavi algoritem, ki ugotovi, če v danem drevesu obstaja list, ki ima vsoto poti enako vrednosti v tem listu.
  49. Predstavitev dvojiškega drevesa s tabelo.
  50. Predstavitve dvojiških dreves v Javi.
  51. Z osnovnimi operacijami sestavi zrcalno kopijo dvojiškega drevesa.
  52. Dano je dvojiško iskalno drevo. Izpiši elemente urejeno od najmanjšega do največjega.
  53. Dano je dvojiško iskalno drevo. Izpiši elemente urejeno od največjega do najmanjšega.
  54. Sestavi algoritem, ki iz sklada zgradi iskalno dvojiško drevo.
  55. Sestavi algoritem, ki s pomočjo osnovnih operacij nad dv. drevesom, dano dvojiško drevo prezrcali (t.j. zamenja vlogo levega in desnega poddrevesa vsakega vozlišča).
  56. Sestavi algoritem, ki s pomočjo osnovnih operacij nad dv. drevesom, ugotovi, če sta dve drevesi identični (imata enako strukturo in hranita enake vrednosti)
  57. Izpitno vprašanje DIRI2005 10500 Sestavi algoritem, ki v iskalnem dvojiškem drevesu poišče minimalni in maksimalni element.
  58. Sestavi algoritem, ki s pomočjo osnovnih operacij nad dv. drevesom, v dvojiškem drevesu poišče minimalni in maksimalni element.
  59. Iskalno drevo.
  60. Dano je dvojiško iskalno drevo. Poišči največji in najmanjši podatek.
  61. Vstavljanje v iskalno drevo.
  62. Razloži, kaj je to kopica in sestavi algoritem, ki vstavi nov podatek v kopico.
  63. Sestavi kopico, če vse elemente poznaš vnaprej.
  64. Elementi so shranjeni v kopici. Sestavi algoritem s katerim jih preložiš v tabelo tako, da so v tabeli urejeni.
  65. Izpitno vprašanje DIRI2005 11200 Naj tabela

    40

    18

    15

    9

    x

    11

    15

    y

    1

    6

    3

    11

    5

    predstavlja max kopico celih števil (x in y seveda nista tiskarski napaki, ampak ustrezni celi števili). Katere (celoštevilske) vrednosti lahko zavzameta x in y?
  66. Sestavi algoritem, s katerim odstraniš vrhnji podatek iz kopice.
  67. Sestavi algoritem, ki poišče najbolj desni element v kopici, iskalnem drevesu in običajnem dv. drevesu. Ima element kakšne posebne značilnosti?
  68. Izpitno vprašanje DIRI2005 11600 Iz podatkov 3, 7, 934, 323, 436, 56, 68, 45, 563, 57, 56, 511, 9879, 234, 355, 53, 35, 34, 111, 22 sestavi dve kopici. Prva naj bo taka, da je oče večji in druga taka, da je oče manjši od sinov. Pri prvi kopici uporabi algoritem, ki predvideva, da podatke dobivaš sproti in pri drugi takega, kjer podatke poznamo vnaprej!
  69. Sestavi algoritem, s katerim odstraniš poljubni podatek iz kopice.
  70. Idejo podatkovne strukture dvojiška kopica lahko naravno razširimo na pojem trojiške kopice. Namesto dveh ima sedaj vsako vozlišče največ 3 sinove. Tudi tu je drevo levo poravnano. Denimo, da trojiško kopico predstavimo v tabeli (v razredu Trojiska_Kopica imamo komponento tabela z n elementi, kjer je n število elementov v kopici) (v tabeli element z indeksom 0 NE izpustimo!) . Opiši način predtsavitve trojiške kopice, relacije med očetom in sinovi, ...
  71. Sestavi algoritem, s katerim v kopici poiščeš najmanjši in največji element!
  72. Sestavi algoritem, s katerim poiščeš element v dvojiškem iskalnem drevesu.
  73. Sestavi algoritem, ki poišče najbolj desni element v kopici, iskalnem drevesu in običajnem dvojiškem drevesu. Ima element kakšne posebne značilnosti?
  74. Dana je tabela celih števil. Uredi jo tako, da so na začetku števila, katerih absolutna vrednost pri deljenju s 3 dajo ostanek 0, nato števila, ki dajo pri deljenju njihove aboslutne vrednosti s 3 ostanek 1 in nato še preostala števila. Analiziraj stabilnost tvojega algoritma – torej ali enaki podatki ohranijo isti relativni vrstni red v preurejeni tabeli.
  75. Sestavi algoritem, s katerim vstaviš nov element v dvojiško iskalno drevo.
  76. Graf je predstavljen z matriko sosednosti. Sestavi algoritem, ki za vsako vozlišče ugotovi njegovo stopnjo.
  77. Razloži in s primerom pokaži, zakaj je dobro uporabljati stabilno metodo urejanja. Pokaži primer vsaj dveh nestabilnih in dveh stabilnih metod urejanja.
  78. Opiši hitro urejanje: algoritem, časovna zahtevnost, ...
  79. Primerjaj vstavljanje, izbiranje in urejanje z mehurčki.
  80. Razloži algoritem za urejanje z vstavljanjem.
  81. Dana je tabela neničelnih celih števil. Uredi jo tako, da bodo najprej soda negativna števila, nato soda pozitivna, nato liha negativna števila in še liha pozitivna števila. Analiziraj časovno zahtevnost svojega algoritma!
  82. Razloži algoritem za urejanje z izbiranjem.
  83. Razloži algoritem za urejanje z mehurčki.
  84. Na praktičnem primeru pokaži, kako deluje hitro urejanje in urejanje z zlivanjem.
  85. Urejanje z zlivanjem.
  86. Urejanje s kopico.
  87. Napiši algoritem za urejanje z vstavljanjem in analiziraj njegovo časovno zahtevnost.
  88. Napiši algoritem za urejanje z izbiranjem in analiziraj njegovo časovno zahtevnost.
  89. Napiši algoritem za urejanje z mehurčki in analiziraj njegovo časovno zahtevnost.
  90. Opiši metodo deli in vladaj.
  91. Opiši, kako bi z metodo deli in vladaj poiskal k-ti največji element v tabeli števil.
  92. Strasenovo množenje matrik.
  93. Razloži, kako z bisekcijo poiščeš element v urejeni tabeli števil. Analiziraj časovno zahtevnost metode.
  94. Naštej nekatere probleme, ki jih lahko rešiš s pomočjo metode deli in vladaj in opiši algoritem za enega od teh.
  95. Analiziraj časovno zahtevnost iskanja minimalnega elementa z direktnim iskanjem (zaporedno primerjanje) in z metodo deli in vladaj.
  96. Izpitno_vprašanje_DIRI2005_1800 S pomočjo metode deli in vladaj sestavi algoritem, ki poišče dve točki v ravnini, ki sta med sabo najmanj oddaljeni.
  97. Razporejanje programskih enot na trak - dokaz pravilnosti postopka.
  98. Požrešna metoda - opiši pojem dopustna rešitev in optimalna rešitev. Prikaži nekaj primerov.
  99. Problem enostavnega nahrbtnika.
  100. Dokaži pravilnost rešitve za problem enostavnega nahrbtnika.
  101. Razporejanje programskih enot na trak.
  102. Izpitno_vprašanje_DIRI2005_16100 Kaj je minimalno vpeto drevo in uporaba slednjega.
  103. Na praktičnem primeru razloži, kako deluje Primov in  Kruskalov postopek.
  104. Meta ima šest prijateljic: Aljo, Jano, Tejo, Sašo, Kajo in Uro. Vse so navdušene uporabnice mobilnih telefonov. Ker mora vsako novico vsaka takoj sporočiti ostalim šestim, so njihovi telefonski računi zelo visoki. Ko so nekaj mesecev spremljale stroške povprečnega pogovora, so prišle do matrike stroškov posameznega klica. Zanima nas, kako naj se novica najceneje prenese med poljubnima dvema prijateljicama. Če se torej Meta pogovarja neposredno z Aljo, so stroški klica 50 SIT. A novica od Mete do Alje lahko pride tudi tako, da Meta pokliče Jano (kar stane 21 SIT), Jana pa potem prenese novico Alji (kar stane 16 SIT) - torej skupno 37 SIT (ceneje)! Za poljubni dve prijateljici ugotovi, koliko ju stane, da si izmenjata novico.
  105. Meta ima šest prijateljic: Aljo, Jano, Tejo, Sao, Kajo in Uro. Vse so navdušene uporabnice mobilnih telefonov. Ker mora vsako novico vsaka takoj sporočiti ostalim šestim, so njihovi telefonski računi zelo visoki. Ko so nekaj mesecev spremljale stroške povprečnega pogovora, so prišle do matrike stroškov posameznega klica. Kako naj se kličejo med seboj, da se bo novica med njimi kar najhitreje raznesla?
  106. Razlike med Primovim in Kruskalovim postopkom, kdaj bi lahko uporabili ta postopek?
  107. Opiši postopek reševanja problema postavitve n-kraljic na šahovsko desko.
  108. Sestavi algoritem, ki v labirintu poišče pot do izhoda.
  109. Na praktičnem primeru demonstriraj način reševanja problema iskanja optimalnega zaporedja množenj matrik - tako določitve števila množenj kot načina množenja. Če je optimalnih načinov množenja več, moraš prikazati vse!
  110. Kako optimalno zmnožimo verigo matrik? Opiši algoritem!
  111. Razloži, zakaj uporaba rekurzije ni primerna za neposreden zapis Bellmanove enačbe pri množenju matrik.
  112. Problem 0/1 nahrbtnika.
  113. Črno/belo barvanje grafa

  114. Drevo stanj za problem trgovskega potnika potnika - pomen vozlišč in pomen ocen ..
  115. S strojem izdelujemo različne izdelke. Čas, potreben za pripravo stroja, je odvisen od tega, kaj želimo delati in kaj smo delali prej. Ta čas smo izmerili. Sedaj moramo izdelati n različnih izdelkov. V kakšnem vrstnem redu naj jih izdelamo, da bomo porabili za to najmanj časa?
  116. Za omrežje dano z matriko 4 x 4 skiciraj drevo stanj, kjer v vozliščih drevesa vpišeš točne vrednosti za minimalno dolžino pripadajočih ciklov.
  117. Navedi vse krožne poti vozlišč označenih od 1 do 7, ki vsebujejo
    a. Povezavo med vozlišči 1 in 3 ter 5 in 1.
    b. Pot 1 - 2 - 6 - 4 - 3
    c. Pot 2 - 6 - 4 - 3
    d. Povezave 1 - 2, 3 - 5, 7 - 4
    Kako bi predstavil ustrezno matriko omrežja, ki bi predstavljala zgoraj navedena stanja?
  118. Vrtalni stroj mora izvrtati n lukenj. V kakšnem vrstnem redu naj vrta, da bo vrtalna glava prepotovala najkrajšo pot?
  119. Na praktičnem primeru razloži, kako poteka reševanje problema trgovskega potnika z metodo razveji in omeji.
  120. Razloži pomen vozlišč in vrednosti v drevesu stanj pri reševanju problema trgovskega potnika z metodo z razveji in omeji.

Osebna orodja