O laboratoriju
Osebje
Objave
Raziskave
Pravila
Predmeti / vaje
Izpitni roki
Rezultati
Diplome
Informacije
Real-time Systems Laboratory

Diplomske naloge

(Algoritmi in) Podatkovne strukture

  1. Vizualizacija podatkovnih struktur
  2. Obnašanje dvojiških dreves
  3. Implementacija in primerjava sortirnih algoritmov

Mikroračunalniki

  1. Rutine za aritmetične operacije nad števili s plavajočo vejico
  2. Inteligentni periferni vmesnik za analogno/digitalno pretvorbo

Sistemi v realnem času

  1. Prikaz strategij razvrščanja opravil v realnem času
  2. Upravljanje konfiguracij programskih zbirk
  3. Načrtovalski vzorci za sisteme v realnem času
  4. Mobilne naprave in sistemi v realnem času

Podiplomski študij

Na podiplomskem študiju izvajamo v okviru laboratorija predmet Sistemi v realnem času. Ker narava predmeta to omogoča, se za vsakega študenta sestavi individualni program, ki se čim bolj prilagaja njegovi splošni usmeritvi. Iz predmeta je mogoce opravljati izpit in / ali seminarsko delo.

Pri podiplomskem študiju kot somentorji praviloma sodelujejo profesorji iz tujine, pri katerih je mogoce opravljati tudi izpite.

V Laboratoriju za sisteme v realnem času je pod mentorstvom dr. Matjaža Colnariča mogoče opravljati magistrska dela in doktorske disertacije. Do sedaj sta bili zaključeni dve magistrski in dve doktorski deli, trenutno pa v okviru laboratorija študirata še dva podiplomska študenta.

Sistemi v realnem času

  1. Simulator okolja vgrajenega sistema za delo v realnem času

Vsebine nalog

Na vrh

Vizualizacija podatkovnih struktur
(univerzitetni | visoki strokovni študij)

Izdelajte programski paket, ki bo omogočal demonstracijo delovanja podatkovnih struktur v okoju MSWindows in/ali XWindows. Izdelan naj bo v obliki, da ga je mogoče povezovati z drugimi paketi.

S paketom zelimo prikazovati podatkovne strukture, ki jih obravnava predmet Podatkovne strukture (in algoritmi): sklad, vrsta, seznam, razne oblike dreves in grafe. Omogočen naj bo eleganten grafični vnos, brisanje in izpis vozlišč in podatkov.

Posebej pri drevesih in grafih je potrebno avtomatsko razporediti vozlišča, tako, da bo oblika drevesa smiselna ter da manjkajoča vozlišča ne bodo zavzemala nepotrebnega prostora na ekranu (prilagoditev izpisa dejanski topologiji).

Možno naj bo ročno premikanje vozlišč strukture: ko se struktura avtomatsko generira, lahko z miško premaknemo neko vozišče na novi položaj. (V primeru drevesa se s tem premakne (in preuredi) poddrevo pod premaknjenim vozliščem)

Program naj omogoča prikaz, izpis na tiskalnik in izvoz slike v vsaj enem od standardnih grafičnih formatov (GIF, BMP, TIFF, JPEG, PS, EPS..) Podatkovno strukturo naj bo mogoče uvoziti in izvoziti tudi v obliki, ki jo je mogoče obdelovati z drugimi programi (dinamični seznami).

univerzitetni ali visoki strokovni program (pri slednjem bo posebej določen obseg nalog)

Kontaktna oseba: M.Colnarič


Na vrh

Vizualizacija in analiza iskalnih dreves
(univerzitetni študij)

Vizualizacija:

  • Izdelajte program za prikaz dvojiških dreves. Prikaz naj čim bolje izkoristi prostor na ekranu (oz. v oknu), kar pomeni, da statična razporeditev vozlišč ni primerna.
  • Možnost določanja zakasnitev, da se vidi, kaj se v drevesu dogaja (izvajanje po korakih?)
  • Podatki se vpisujejo ročno oz. jemljejo iz datoteke ali iz generatorja. Pripravite primerni način podajanja podatkov za iskanje, vstavljanje in odstranjevanje.
  • Paralelni prikaz različnih dreves pri vstavljanju istih podatkov v različnih oknih?

Analiza obnašanja:

Implementacija iskalnih dreves:

  • navadno iskalno drevo,
  • vstavljanje v koren,
  • lomljeno drevo,
  • uravnoteženo (AVL) drevo,
  • rdeče-črno drevo,
  • (simetrično) binarno Bayerjevo.

Izdelajte algoritme za vstavljanje, iskanje in odstranjevanje podatkov. V algoritme vgradite sonde, ki opazujejo višino dreves in merijo zahtevnost postopkov (število osnovnih operacij - premikov, rotacij, itd.. - bomo še definirali). Računanje pričakovane iskalne poti.

V drevesa se vstavljajo poljubne količine podatkov:

  • naključno zaporedje z enakomerno porazdelitvijo,
  • z normalno porazdelitvijo,
  • striktno naraščajoče in padajoče zaporedje,
  • zaporedje s tendenco naraščanja oz. upadanja.

Analiza rezultatov: primerjava kvalitete (višine dreves in povprečne iskalne poti) in zahtevnosti algoritmov. V Excelu?

Kontaktna oseba: M.Colnarič


Na vrh

Vizualizacija in analiza sortirnih algoritmov
(univerzitetni | visokošolski strokovni študij)

Vizualizacija:

  • Izdelajte program za prikaz poteka sortiranja podatkov.
  • Imeti mora možnost določanja zakasnitev, da se vidi, kaj se med postopkom dogaja (izvajanje po korakih?).
  • Podatki se vpisujejo ročno oz. jemljejo iz datoteke ali iz generatorja. Pripravite primerni način podajanja podatkov za iskanje, vstavljanje in odstranjevanje.
  • Paralelni prikaz vmesnega stanja pri urejanju istih podatkov po različnih postopkih ob istem številu operacij?

Analiza obnašanja:

Implementacija sortirnih postopkov:

navadno vstavljanje, navadno izbiranje, sortiranje s premenami (bubble-sort), sortiranje z naraščajočim prirastkom (Shellsort), drevesno sortiranje (Heapsort), Quicksort, Radixsort, Mergesort

Analiza rezultatov:

primerjava zahtevnosti algoritmov v MS Excelu?

Kontaktna oseba: M. Colnarič, R. Gumzej


Na vrh

Matematične rutine za operacije nad števili s plavajočo vejico
(univerzitetni | visokošolski strokovni študij)

Opis:

Izdelajte knjižnico rutin, ki bodo omogočale izvedbo operacij s plavajočo vejico na Motorolinem mikroprocesorju ColdFire. Za predstavitev števil s plavajočo vejico ter operacije nad njimi uporabite standard IEEE 754. Za vsako izmed rutin je potrebno določiti ali izmeriti maksimalne čase izvajanja.

Kontaktna oseba: D. Verber


Na vrh

Inteligentni periferni vmesnik za analogno/digitalno pretvorbo

Izdelajte inteligentni periferni vmesnik, ki bo preko serijskega vodila omogočal opazovanje analognih signalov. Omogoča naj dva načina delovanja, ki se nastavita ob inicializaciji:

  • pretvorba na zahtevo
  • ciklični način

Pri pretvorbi na zahtevo lahko gospodar preko serijskega vodila zahteva pretvorbo, katere rezultati bodo dosegljivi čez čas. Zahteva lahko tudi vzorčenje ob točno dolocenem času, rezultat pa bo prečital kasneje.

Pri cikličnem načinu vmesnik neprestano izvaja pretvorbo. Rezultate zadnjih N meritev shranjuje v krožni pomnilnik skupaj s časi, ko so bili dobljeni. Perioda je lahko konstantna ali pa se pretvorba sproži, čim je bila prejšnja gotova.

V primeru cikličnega načina je možno zahtevati najbolj sveži rezultat (pri čemer se lahko zahteva tudi čas, ko je bil dobljen), ali pa oceno trenutne vrednosti, kar se lahko dobi z ekstrapolacijo zadnjih vrednosti (linearno ali višjega reda).

V obeh načinih delovanja je možno zahtevati kontrolo delovanja: ob pretvorbi na zahtevo se lahko podajo gornja in spodnja meja pričakovanjega rezultata. Pri cikličnem delovanju se poleg tega lahko zahteva tudi kontrola dinamike ("filtriranje"): ob podani časovni konstanti se lahko predpostavi, kakšen je najvecji možni interval naslednjega odtipka. Če pride v katerem od primerov do odstopanja, pošlje opozorilo (alternativa, ki se jo da izbrati med inicializacijo: v primeru cikličnega delovanja lahko izračuna ekstrapolirano vrednost; če bo naslednji odtipek spet izven meja, javi napako. S tem sfiltiriramo enkratne pogreške).

Za vzdrževanje realne ure služi timer, ki ga na zacetku zbrišemo, nato pa ga inkrementiramo z urinimi impulzi, ki prihajajo od gospodarja. Ob inicializaciji lahko gospodar vmesniku pošlje tudi začetni absolutni čas, kot bo ob zagonu sistema, oz. ob trenutku, ko bo dobil prvi impulz. Absolutni čas bo torej izračunal tako, da bo začetnemu absolutnemu času prištel relativni, ki ga izračuna iz stanja števca.

Izdelajte protokol komunikacije med gospodarjem in vmesnikom posebej za inicializacijo in za vse načine delovanja, ki se ob inicializaciji izberejo.

Kontaktna oseba: M. Colnarič, D. Verber


Na vrh

Preučevanje in vizualizacija postopkov razvrščanja opravil v realnem času
(visokošolski strokovni študij)

Namen diplomske naloge je preu;iti delovanje razvrščanja opravil, ki delujejo v realnem času in izdelati študijski pripomoček. Vsako opravilo je doloceno s časom prihoda, trajanjem obdelave in skrajnim rokom za dokončanje. Ti podatki se vnašajo ročno (na začetku ali med delovanjem simulacije), lahko se generirajo avtomatsko z različnimi statističnimi lastnostmi ali prečitajo iz datoteke. Izdelati je treba simulacijo in grafični prikaz nekaj osnovnih algoritmov za razvrščanje opravil na eno- in večprocesorskih sistemih. Simulacija naj poteka v realnem času (dogajanje v sistemu je sproti vidno na ekranu). Opazovati je potrebno preobremenitve, ko sistem ni zmožen postreči vseh zahtev.

Kontaktna oseba: M. Colnarič


Na vrh

Upravljanje konfiguracij programskih zbirk kot nad-nivo operacijskega sistema
(univerzitetni študij)

Upravljanje konfiguracij izhaja iz namenskih vgrajenih računalniških sistemov, kjer je bilo mogoče strogo ločevati faze delovanja – ter sprogramirati ustrezne scenarije zanje (npr. proizvodne linije, nadzor letenja ipd.). Za ta namen je bila večinoma v uporabi statična rekonfiguracija. Kasneje se je pojavila potreba po dinamični rekonfiguraciji, kjer so meje med fazami delovanja manj strogo določene in je pogosto treba spremeniti le del scenarija, vendar se mora to zgoditi predvidljivo in varno.

Upravljanje konfiguracij programskih paketov z njihovimi povezavami se ne more vedno zanašati le na operacijski sistem. Zlasti v distribuiranem okolju, kjer mora več procesnih enot med sabo sodelovati pri obdelavi iste aplikacije, je zaradi konsistentnosti scenarijev včasih ugodno, da to nalogo prevzame upravljavec konfiguracij (Configuration Manager - CM), ki kot upravljavec programskih zbirk pri vsakem procesnem vozlišču (node) poskrbi za varnost preklopov med predvidenimi scenariji delovanja (različnimi paketi in njihovimi medsebojnimi povezavami).

V okviru naloge je potrebno s pomočjo RT-UML metodologije definirati CM kot bazno kapsulo - aktivni objekt programskih zbirk (paketov), ki znotraj nje skrbi za aktivacije ustreznih aktivnih objektov glede na aktualni scenarij. Navzven je ta bazna kapsula zadolžena za vzdrževanje in rekonfiguracije povezav z drugimi programskimi zbirkami, ki so lahko fizično tudi naložene na drugih procesnih enotah (node). Scenarij definiramo s pomočjo diagrama prehajanja stanj te bazne kapsule.

Kontaktna oseba: M. Colnarič, R. Gumzej


Na vrh

Načrtovalski vzorci za sisteme v realnem času
(univerzitetni študij)

Pri sistemih v realnem času se pojavljajo določeni vzorci delovanja, ki omogočajo načrtovanje varnih in robustnih aplikacij in so zanje karakteristični (npr.: watchdog, monitor-actuator, modeli upravljanja s pomnilnikom, ...), arhitekturni vzorci, ki so sicer lastni distribuiranim sistemom in veljajo tudi tu (npr.: Master-Slave, Layered Arcitecture, Proxy, Broker,…), vzorci za mehanistično načrtovanje (Observer, Rendezvous,…).

V okviru naloge je treba raziskati področje, identificirati še ostale (specifične) vzorce za sisteme v realnem času, jih klasificirati in zasnovati v RT-UML metodologiji.

Kontaktna oseba: M. Colnarič, R. Gumzej


Na vrh

Mobilne naprave in sistemi v realnem času
(univerzitetni študij)

Mobilne računalniške naprave se uveljavljajo predvsem na telekomunikacijskem področju (mobilni telefoni), pa tudi kot mediji za satelitsko navigacijo in lokalne obdelave (PDA terminali).

V okviru naloge je treba raziskati področje mobilnih terminalov (PDA), ki delujejo na Windows CE platformi in njihovo zmožnost delovanja v realnem času v odvisnosti od mobilnih komunikacij. Predvidena testna aplikacija je daljinski nadzor in krmiljenje določene naprave, ki je prav tako priključena na mobilno omrežje preko v omrežje povezanega (Host) sistema ali WLan konfiguracije.

Kontaktna oseba: M. Colnarič, R. Gumzej

Na vrh | Prva stran | O laboratoriju | Osebje | Inštitut za informatiko | E-pošta

 

RTSUMInštitut za informatikoFERIFERI