Predgovor

Upustiti se u pisanje udžbenika sa naslovom “Diskretna matematika” bez ikakve sumnje predstavlja hrabru odluku, s obzirom na izuzetnu raznovrsnost problema kojima se diskretna matematika bavi. Interesantno je da i sam naziv “Diskretna matematika” u početku predstavlja veliku nepoznanicu studentima koji se sa ovom vrstom matematike prvi put susreću, s obzirom da je po tradiciji nastava matematike na tehničkim fakultetima bazirana pretežno na matematičkoj analizi, odnosno na kontinualnoj matematici. Međutim, sa intenzivnim razvojem računara, koji su po svojim fundamentalnim principima rada čisto diskretne naprave, interes za diskretnu matematiku rapidno raste, tako da diskretna matematika polako ali sigurno ulazi u nastavne programe većine fakulteta koji se bave tehničkim naukama. Doduše, neke oblasti diskretne matematike (uglavnom matematička logika i donekle teorija skupova) odavno se predaju na tehničkim fakultetima u okviru nekih drugih matematičkih kurseva, ali najčešće na površan i nedovoljno sistematičan način. Za razumijevanje pojava koje se proučavaju i modeliraju u savremenim računarskim naukama neophodan je sistematičan pristup matematskom aparatu diskretne matematike. Ovo je dosta problematično zbog činjenice da su oblasti kojima se bavi diskretna matematika prividno veoma nepovezane međusobno, tako da se njihova međusobna veza uočava tek nakon temeljitog proučavanja.

Kolika je raznovrsnost oblasti kojima se bavi diskretna matematika, najbolje se može demonstrirati činjenicom da u svijetu postoji dosta udžbenika hrabrog naziva “Diskretna matematika” (poput naziva ovog udžbenika) ili nešto tome slično, a čiji se sadržaji posve razlikuju. Kao drastičan primjer, autor može navesti primjere dva udžbenika veoma sličnog naziva, koji praktično nemaju niti jedne zajedničke teme koji obrađuju. Prvi je udžbenik pod nazivom “The Essence of Discrete Mathematics” autora N. Deana, koji obrađuje teme vezane za teoriju skupova, iskaznu i predikatsku logiku, te teme vezane za proučavanje relacija, funkcija i principa matematičkog modeliranja. Druga krajnost je udžbenik pod nazivom “Diskretna matematika” čiji su autori I. Milovanović i E. Milovanović, koji obrađuje teme vezane za teoriju diferentnih jednačina i konačnih suma, zatim za proučavanje specijalnih tipova matrica, te teme vezane za enumerativnu kombinatoriku, teoriju kombinatornih konfiguracija i teoriju grafova. Ovim autor ne želi reći da je i jedan od ova dva udžbenika loš (čak naprotiv), nego jednostavno da oni pokrivaju totalno drugačije aspekte diskretne matematike.

Prilikom pisanja ovog udžbenika, autor se našao pred teškom odlukom koje oblasti da obradi. Kao vodilja je poslužio nastavni plan i program za kurs pod nazivom “Diskretna matematika” koji autor ovog udžbenika posljednjih nekoliko godina (praktički od njegovog uvođenja) predaje na Elektrotehničkom fakulteta Univerziteta u Sarajevu. Ovaj kurs se sluša na II godini studija kao redovan kurs na Odsjeku za računarstvo i informatiku, te kao izborni kurs na Odsjeku za automatiku i elektroniku. Stoga je autor odlučio da obradi upravo one oblasti koje se nalaze u nastavnom planu i programu ovog kursa. Sve što se obrađuje na predavanjima iz ovog kursa, kao i brojni primjeri koji se obrađuju na auditornim vježbama ili kroz zadatke za samostalan rad, nalazi se u ovom udžbeniku. Međutim, s obzirom da je pomenuti nastavni plan i program izuzetno obiman, a fond časova za kurs veoma ograničen (60 časova u toku jednog semestra), mnoge interesantne teme na predavanjima ostaju samo dotaknute, a pominju se više sa ciljem da eventualno zainteresiraju studenta nego sa ciljem da budu detaljnije obrađene. Autor ovog udžbenika je odlučio da takve teme temeljitije obradi u udžbeniku. Stoga na mnogim mjestima sadržaj udžbenika daleko prevazilazi sadržaj koji se u okviru predavanja posvećuje istoj temi. Odjeljci čiji sadržaj za više od 30 % prelazi sadržaj koji se obrađuje na predavanjima označeni su znakom “+” iza rednog broja odjeljka, dok su sadržaji koji se uopće ne obrađuju na kursu (ili se eventualno obrađuju samo opcionalno za zainteresirane studente) označeni znakom “#”. Na taj način će studentu biti olakšano snalaženje u udžbeniku. Nakon svakog poglavlja nalaze se odabrani zadaci, koji između ostalog uključuju i sve zadatke koji su se do sada pojavljivali na ispitima, ili su bili davani kao zadaci za zadaću.

Obimnost ovog udžbenika ne treba nikoga da začudi, s obzirom na veoma kompleksan nastavni plan i program. Treba napomenuti da je veoma teško naći na jednom mjestu sve oblasti kojima se ovaj udžbenik bavi, pogotovo na jezicima naroda Bosne i Hercegovine (užbenici D. Cvetkovića, profesora na Elektrotehničkom fakultetu Univerziteta u Beogradu, donekle se približavaju ovom cilju, ali ni oni ne prate u potpunosti plan i program kursa diskretne matematike na ETF-u u Sarajevu). Stoga je cilj ovog udžbenika upravo da ublaži ovaj nedostatak. Poređenja radi, treba napomenuti da se dosada predviđena obavezna literatura za ovaj kurs na ETF-u u Sarajevu sastojala od 3 udžbenika na engleskom jeziku (“Discrete Mathematics and Its Applications” K. H. Rosena, “Discrete and Combinatorial Mathematics” R. P. Grimaldija te “Introduction to the Theory of Computation” M. Sipsera), koji zajedno imaju preko 2000 stranica, što je više nego trostruko duže od ovog udžbenika.

Činjenica da se u ovom udžbeniku obrađuje zaista veliki broj različitih tema na relativno skučenom prostoru ima i svoju cijenu. Na mnogim mjestima materija se izlaže čisto faktografski, bez ulaženja u dokaze pojedinih tvrdnji (u okviru predavanja dokazi se uglavnom u potpunosti izostavljaju). Dokazi su u udžbeniku navedeni samo u slučajevima gdje čitatelj odnosno čitateljka mogu doći do nekih bitnih saznanja proučavajući dokaz. Na taj način, s vremena na vrijeme udžbenik dobija donekle enciklopedijski karakter. Međutim, s obzirom da je udžbenik prvenstveno namijenjen studentima tehničkih nauka kojima je bitnije znati kako izvesti neki postupak nego zašto se on izvodi baš tako, ovo i nije veliki nedostatak. S druge strane, na pojedinim mjestima dosta se prostora posvećuje nekim donekle filozofskim raspravama sa ciljem da se pronikne u suštinu materije (ovo se posebno odnosi na teme iz oblasti matematičke logike i teorije skupova). Cilj ovoga je da popravi nivo opće matematičke kulture kod čitatelja odnosno čitateljki, koji je kod studenata tehničkih nauka danas nažalost uglavnom na dosta niskom nivou.

Interesantno je napomenuti da se u ovom udžbeniku obrađuju i neke teme koje se veoma rijetko susreću u udžbenicima diskretne matematike širom svijeta, (a koje su predviđene nastavnim planom i programom kursa diskretne matematike na ETF-u u Sarajevu). To se prvenstveno odnosi na teme iz oblasti teorije diskretnih sistema, koje mada po formi definitivno pripadaju grani diskretne matematike, traže ozbiljnije uplitanje matematskog aparata matematske analize, koja je tipični primjer kontinualne matematike. S druge strane, ograničenost na teme koje se u manjoj ili većoj mjeri obrađuju na kursu diskretne matematike na ETF-u u Sarajevu (u nastavku samo Kursu), te ograničenost prostora u ovom udžbeniku doveli su do toga da se pojedine interesantne oblasti diskretne matematike nije moglo naći mjesta u ovom udžbeniku. Tako se, na primjer, u ovom udžbeniku nije moglo naći mjesta za teoriju jezika i automata, teoriju sekvencijalnih struktura, teoriju kombinatornih struktura, teoriju kombinatorne optimizacije (sa izuzetkom problema raspoređivanja), teoriju diskretnih igara, računarsku geometriju, teoriju diskretnih stohastičkih procesa, teoriju kodiranja, teoriju kompleksnosti, teoriju algebarskih struktura, matrične metode u diskretnoj matematici i još neke druge interesantne oblasti koje spadaju u predmet proučavanja diskretne matematike u užem ili širem smislu. Ova činjenica se navodi ne da se istakne nedostatak udžbenika, nego više sa ciljem da ukaže na činjenicu koliko je zapravo širok predmet proučavanja diskretne matematike.

Mada je udžbenik prvenstveno namijenjen studentima Elektrotehničkog fakulteta u Sarajevu, on može bez ikakvih problema poslužiti svima koje ova materija zanima, kao i studentima drugih fakulteta na kojima se izučavaju srodne discipline. Tako, ovaj udžbenik bez sumnje može biti od koristi studentima svih tehničkih fakulteta, zatim studentima Prirodno matematičkog fakulteta (naročito studentima Odsjeka za matematiku), pa donekle i studentima ekonomskog fakulteta.

Materija u udžbeniku podijeljena je na 10 poglavlja, ne računajući uvodno poglavlje. Svrha uvodnog poglavlja (numeriranog kao Poglavlje 0) je da ukaže na motivaciju za uvođenje matematskog aparata diskretne matematike. U ovom poglavlju, nakon kratkog osvrta na predmet proučavanja diskretne matematike, ilustrira se razlika između kontinualnih i diskretnih veličina, te uspostavlja veza između ovih veličina. Na kraju uvodnog poglavlja, ilustrira se kako priroda binarnog kodiranja informacija u savremenim digitalnim računarima dovodi do potrebe proučavanja posve drugačijeg matematskog aparata u odnosu na onaj koji nudi konvencionalna kontinualna matematika.

Poglavlje 1 posvećeno je elementima logike iskaza i iskazne algebre. Ovo poglavlje uglavnom po sadržaju i obimu prati materiju koja se prelazi u okviru Kursa. Nakon upoznavanja sa osnovnim pojmovima logike iskaza, principima formiranja složenih iskaza i zakonima iskazne algebre, čitatelj odnosno čitateljka se informativno upoznaju sa aksiomatskom pristupu logici iskaza, više sa ciljem da shvate šta je uopće bit aksiomatskog pristupa u matematici. Posebna pažnja se posvećuje problemu ekvivalencije logičkih izraza. Dio posvećen tautologijama i matematičkom načinu zaključivanja bitno je proširen u odnosu na materiju koja se obrađuje na Kursu, prvenstveno zbog opisa dokazivanja zasnovanog na principu rezolucije, koji se na Kursu ne obrađuje. Također, u udžbeniku se u osnovnim crtama upoznaje i sa pristupom logici iskaza kao formalnoj teoriji, što se u Kursu ne obrađuje. Veliki dio poglavlja posvećen je transformaciji logičkih izraza na standardne oblike, kao i metodama za njihovu minimizaciju. Mada se ova tematika ne obrađuje često na kursevima diskretne matematike, na ovaj način se uspostavlja čvrsta poveznica sa kursom “Logički dizajn” koji studenti računarstva i informatike na ETF-u u Sarajevu također slušaju kao obavezni kurs. Na kraju poglavlja, obrađuju se univerzalne logičke funkcije, te baze iskazne algebre.

U Poglavlju 2 obrađuju se elementi teorije skupova, pri čemu se posebna pažnja posvećuje specijalnim skupovnim tvorevinama kao što su funkcije i relacije. Na početku se obrađuju osnovni pojmovi teorije skupova, modeli za opis skupova, osnovne operacije sa skupovima te zakoni algebre skupova. Zatim se uvodi pojam uređenih n-torki i Kartezijevog produkta, koji se koristi za definiranje binarnih i općenitije n-arnih relacija. Odjeljak o binarnim relacijama neznatno je proširen opisom Warshallovog algoritma za nalaženje tranzitivno-refleksivnog zatvorenja relacije, koji se na Kursu ne obrađuje. S druge strane, odjeljak o n-arnim relacijama bitno je proširen u odnosu na Kurs uspostavljanjem jasne veze sa teorijom relacionih baza i programskim jezikom SQL, čime se uspostavlja veza sa kursom “Osnove baza podataka” na Odsjeku za računarstvo i informatiku na ETF-u u Sarajevu (ovo proširenje se studentima koji pohađaju Kurs nudi kao neobavezni dodatak). Poglavlje se dalje nastavlja razmatranjem načina skupovnog modeliranja funkcija, te specijalnih vrsta relacija, kao što su relacije ekvivalencije i poretka. Završni dio poglavlja posvećen je nekim naprednijim konstrukcijama teorije skupova kao što su modeli prirodnih brojeva pomoću skupova i kardinalni brojevi, te kratkim osvrtom na protivrječnosti naivne teorije skupova i na aksiomatsku teoriju skupova. Mada se o ovim temama rijetko govori na kursevima diskretne matematike, okvirno upoznavanje sa njima, pored činjenice da povećava nivo matematičke kulture kod čitatelja odnosno čitateljki, neophodno je za kasnije razumijevanje teorije izračunljivosti.

Cilj Poglavlja 3 je da ukaže na bitnu vezu između tema koje su obrađene u prva dva poglavlja i da ukaže na alternativne načine posmatranja na iskaznu algebru, te na pravce u kojima se ona može znatno proširivati. Nakon što se uvede pojam Booleove algebre, pokazuje se da su i iskazna algebra i algebra skupova njeni specijalni slučajevi, te se razmatraju još neki interesantni primjeri Booleovih algebri. Posebna pažnja posvećuje se prekidačkoj algebri, prekidačkim funkcijama i njihovoj interpretaciji u tehnici, s obzirom da one čine osnovni matematički model za modeliranje savremenih digitalnih uređaja. Dio posvećen Žegalkinovoj algebri proširen je opisom logičkog diferenciranja koje se ne obrađuje na Kursu, sa ciljem da se ukaže na mogućnost njegove primjene u detekciji kvarova u digitalnim uređajima. Odjeljci o alternativnim logikama, kao što su ternarna logika i fuzzy logika osjetno su prošireni u odnosu na materiju koja se obrađuje na Kursu, s obzirom da ove logike dobijaju sve veći i veći značaj u modernom računarstvu. Konačno, poglavlje se završava uvodom u teoriju fuzzy relacija, fuzzy vezivanja i principima aproksimativnog rezonovanja. Ove teme, koje tek odnedavno stidljivo ulaze u predmet proučavanja diskretne matematike, inače se ne obrađuju na Kursu, ali se nude kao opcija zainteresiranim studentima. Na taj način ostvaruje se poveznica sa nizom kurseva na višim godinama iz oblasti vještačke inteligencije, na kojima se koristi upravo taj matematski aparat.

Poglavlje 4 posvećeno je predikatskoj logici, čije je ispravno razumijevanje obično bolna tačka kod velikog broja studenata, što dovodi do čestih pogrešnih rezonovanja. S druge strane, temeljito poznavanje ove oblasti neophodno je za razumijevanje principa i metoda vještačke inteligencije. Na početku se izlažu osnovni pojmovi predikatske logike te načini modeliranja rečenica govornog jezika jezikom predikatske logike prvog reda. Sadržaj u ovom dijelu uglavnom prati sadržaj Kursa, samo što je obogaćen primjerima. Posebna pažnja posvećuje se valjanim izrazima predikatske logike i logičkim posljedicama. Ovaj odjeljak je u odnosu na sadržaj Kursa proširen nekim metodama za dokazivanje odnosno opovrgavanje valjanosti nekih izraza predikatske logike (poput metoda ekspanzije domena). Nakon upoznavanja sa najvažnijim primjerima valjanih izraza i preneks normalnom formom izraza predikatske logike, opisuje se mehanički postupak za dokazivanje valjanosti svih valjanih izraza predikatske logike. Na kraju ovog poglavlja, čitatelji odnosno čitateljke se informativno upoznaju sa ograničenjima predikatske logike prvog reda, te predikatskim logikama višeg reda.

U Poglavlju 5 obrađuju se odabrane teme iz elementarne teorije brojeva. Ovo poglavlje je na mnogim mjestima osjetno prošireno u odnosu na sadržaj Kursa, s obzirom da studenti ETF-a o ovoj materiji nemaju priliku ništa čuti ni na kojem drugom mjestu tokom studija, a radi se o materiji koja privlači sve više pažnje u modernim računarskim naukama, posebno na polju problematike sigurnosti u savremenim komunikacijama. Na početku ovog poglavlja, prvo se uvode osnovni pojmovi elementarne teorije brojeva, poput djeljivosti, prostih brojeva, najvećeg zajedničkog djelioca, itd. Ovaj dio poglavlja uglavnom posve prati sadržaj Kursa, osim što je dio o prostim brojevima proširen opisom Lucas Lehmerovog testa za testiranje prostosti Mersenneovih prostih brojeva. Nakon razmatranja Euklidovog algoritma, dolazi odjeljak o Fibonaccijevim brojevima, koji je donekle proširen u odnosu na sadržaj Kursa opisom nekih interesantnih svojstava ovih brojevima, koje je korisno znati. Odjeljak o linearnim Diofantovim jednačinama, osim što je obogaćen primjerima, proširen je opisom alternativnih metoda za rješavanje te vrste jednačina koje se ne oslanjaju na Euklidov algoritam, kao i upućivanjem na problematiku prebrojavanja rješenja takvih jednačina u prisustvu dopunskih ograničenja. U odjeljku posvećenom kongruencijama i modularnoj aritmetici postoje također neka sitnija proširenja u odnosu na sadržaj Kursa. Međutim, naredni odjeljak, posvećen testovima prostosti zasnovanim na kongruencijama, ne obrađuje se na Kursu, a uvršten je radi značaja ove tematike u primjenama. Odjeljak o linearnim kongruencijama proširen je razmatranjem linearnih kongruencija sa više nepoznatih koje se na Kursu ne obrađuju, kao i opisom nekih alternativnih metoda za njihovo rješavanje, dok je odjeljak o sistemima linearnih kongruencija drastično proširen u odnosu na sadržaj Kursa (na Kursu se obrađuju samo sistemi sa jednom nepoznatom koji se mogu riješiti putem Kineske teoreme o ostacima). Odjeljak o kvadratnim kongruencijama razmatra i postupke za njihovo rješavanje, dok se na Kursu samo dotiče problematika njihove rješivosti, a odjeljak o kongruencijama višeg reda izlazi izvan domena razmatranja Kursa. Konačno, posljednji odjeljak posvećen nekim primjenama elementarne teorije brojeva u kriptografiji, uglavnom prati sadržaj Kursa.

Poglavlje 6, posvećeno elementima enumerativne kombinatorike, najviše po obimu odstupa od sadržaja Kursa. Naime, mada enumerativna kombinatorika spada u jednu od najširih oblasti diskretne matematike, njoj je u nastavnom planu i programu Kursa posvećeno premalo prostora, pretežno zbog želje da se obradi što veći broj različitih oblasti. Tako se Kurs uglavnom ograničava samo na proučavanje elementarnih kombinatornih pojmova, kao što su permutacije, kombinacije i varijacije (sa i bez ponavljanja), te na probleme izbora uzoraka, uz kratak osvrt na permutacije totalnog nereda, particije i kompozicije. Mada se neki složeniji primjeri na Kursu obrađuju kroz auditorne vježbe i zadatke za samostalan rad, u pristupu tim problemima nedosteje sistematičnosti. Ovaj udžbenik u velikoj mjeri ispravlja ovaj nedostatak, pogotovo zbog činjenice da se studenti ETF-a u Sarajevu sa ovom materijom ne susreću niti na jednom drugom kursu. Tako se u udžbeniku našlo mjesta i za sistematičan pristup varijacijama i kombinacijama sa ponavljanjem u prisustvu dopunskih ograničenja (ovdje su dijelom iskorišteni neki originalni rezultati do kojih je došao autor ovog udžbenika¹), te naprednijim ali izuzetno važnim temama enumerativne kombinatorike kao što su funkcije izvodnice, rekurzivni postupci u kombinatorici i Stirlingovi brojevi. Odjeljci o permutacijama totalnog nereda te particijama i kompozicijama znatno su prošireni u odnosu na sadržaj Kursa (pogotovo ovaj posljednji), dok se poglavlje završava opisom pokušaja sistematičnog pristupa raznorodnim kombinatornim problemima koje je pod nazivom “twelvefold way” uveo G. C. Rota.

Poglavlje 7 uglavnom u potpunosti prati sadržaj Kursa. Zbog ograničenosti prostora (kako na Kursu, tako i u udžbeniku), u ovom poglavlju obrađuju se samo osnovni elementi diskretne teorije vjerovatnoće. Nakon izlaganja osnovnih pojmova o algebri događaja i samom pojmu vjerovatnoće (uz ilustrativne primjere), posebna pažnja se posvećuje problemu računanja vjerovatnoće pri izboru uzoraka. Slijede teme vezane za uvjetnu (relativnu) vjerovatnoću i Bayesovu teoremu. Poglavlje završava prikazom jedne od mogućih interpretacija značenja vjerovatnoće, čime se uspostavlja prirodna veza teorije vjerovatnoće sa metodama statističke analize.

Poglavlje 8 posvećeno je elementima teorije grafova. Mada je ovo jedno od dva najduža poglavlja u čitavom udžbeniku (što nije čudno s obzirom na značaj koju teorija grafova zauzima u diskretnoj matematici), ono uglavnom tačno prati sadržaj Kursa (uz izuzetke koji će biti spomenuti). S obzirom na publiku kojoj je udžbenik namijenjen, veća težina se daje algoritamskim nego općim aspektima teorije grafova. Nakon izlaganja osnovnih pojmova teorije grafova, razmatra se problematika reprezentacije grafova u računarima, izomorfizma grafova, osnovne operacije sa grafovima, problematika planarnosti, Eulerovih i Hamiltonovih puteva, te bojenja čvorova i grana grafa. Nakon toga se razmatraju stabla i kosturi grafa, te problematika sistematičnog obilaska čvorova grafa i njene primjene. Slijedi razmatranje problema pronalaženja minimalnog povezujućeg stabla i mreže najkraćih puteva u grafu na razne načine, pri čemu je odjeljak o nalaženju minimalnog pozezujućeg stabla u odnosu na sadržaj Kursa proširen nekim detaljima koji omogućuju efikasniju implementaciju odgovarajućih algoritama na računaru. Potom slijedi razmatranje transportnih mreža i pronalaženja optimalnog protoka kroz transportne mreže. Odjeljak o problematici uparivanja u grafovima proširen je u odnosu na sadržaj Kursa, dok se materija obrađena u odjeljku o problemu optimalnog raspoređivanja ne obrađuje na Kursu, ali se obrađuje na nekim drugim kursevima na višim godinama studija na ETF-u u Sarajevu, kao što je recimo kurs “Operaciona istraživanja”. Na kraju, poglavlje završava kratkim osvrtom na stabla sa korijenom i binarna stabla.

Poglavlje 9 predstavlja uvod u problematiku vezanu za teoriju diskretnih sistema i njene primjene. Ovo poglavlje obrađuje teme koje se, izuzev tematike vezane za rekurzivne relacije i diferentne jednačine, rijetko obrađuju u okviru kurseva diskretne matematike, nego se ta problematika uglavnom ostavlja za specijalističke kurseve posvećene teoriji signala i sistema. S druge strane, ovoj problematici na Kursu se posvećuje posebna pažnja, s obzirom da studenti Odsjeka za računarstvo i informatiku na ETF-u u Sarajevu o ovoj problematici nemaju priliku čuti niti u jednom drugom kursu tokom studija, a njeno poznavanje je poželjno za praćenje nekih kurseva na višim godinama studija. Također, studenti Odsjeka za automatiku i elektroniku na istom fakultetu kroz ovaj kurs mogu sagledati ovu problematiku iz drugačijeg ugla nego što se to posmatra na nekim drugim kursevima na ovom smjeru. Upravo iz tog razloga, sadržaj ovog poglavlja je u većini odjeljaka u izvjesnoj mjeri proširen u odnosu na sadržaj Kursa, a neki odjeljci se uopće ne obrađuju u Kursu. Tako je već uvodni odsjeljak o diskretnim signalima proširen važnim zapažanjima vezanim za prirodu periodičnih diskretnih sekvenci, čime se uspostavlja veza sa razmatranjima vezanim za diskretne Fourierove redove i diskretnu Fourierovu transformaciju, sa kojima se studenti mogu susresti na drugim kursevima. Nakon općih razmatranja o pojmu diskretnog sistema, posebna pažnja se posvećuje linearnim i stacionarnim sistemima, pri čemu se problematika nestacionarnosti razmatra detaljnije nego na Kursu. Slijedi razmatranje diskretne konvolucije i funkcije sistema, pri čemu je sadržaj odjeljka o funkciji sistema proširen razmatranjima za frekventno selektivno djelovanje diskretnih sistema. U nastavku slijedi upoznavanje sa z-transformacijom i inverznom z-transformacijom, koji su prošireni nekim nekonvencionalnim razmatranjima vezanim za proširenje područja primjene z-transformacije i nekim alternativnim tehnikama koje često olakšavaju nalaženje inverzne z-transformacije. Veći dio poglavlja posvećen je primjenama tehnika zasnovanih na z-transformaciji, pri čemu se na Kursu razmatraju primjene vezane za nalaženje odziva diskretnih sistema, rješavanje linearnih diferentnih jednačina sa konstantnim koeficijentima (i sistema takvih jednačina), te za sumiranje nekih tipova redova (posljednja problematika se ovdje razmatra detaljnije nego na kursu). Na kraju poglavlja nalaze se dvije teme koje se na Kursu ne obrađuju. Prva tema odnosi se na mogućnosti primjene razmotrenih tehnika u kombinatorici, čime se uspostavlja interesantna i neočekivana veza između nekih problema kombinatorike i teorije diskretnih sistema. Druga tema odnosi se na mogućnosti primjene razmotrenih tehnika na rješavanje nekih vrsta linearnih diferentnih jednačina sa promjenljivim koeficijentima. Pristup ovoj problematici koji je ovdje opisan je vrlo nekonvencionalan i jednim dijelom je baziran na rezultatima autorovog samostalnog istraživanja u ovoj oblasti.

Poglavlje 10 je posljednje poglavlje ovog udžbenika, i posvećeno je elementima teorije izračunljivosti. Ovo poglavlje većinom u potpunosti prati sadržaj Kursa, osim posljednjeg odjeljka, posvećenog Churchovom l-računu, koje je prošireno u odnosu na sadržaj Kursa. Nakon kraćeg uvoda u predmet proučavanja teorije izračunljivosti i upoznavanja sa strogim zasnivanjem pojma algoritma, diskutira se egzistencija algoritamski nerješivih problema i navode važniji primjeri takvih problema. Potom se razmatraju konceptualno različiti ali suštinski ekvivalentni modeli računskih načina kojima se na strog način modelira proces izračunavanja, kao što su Turingova mašina, univerzalne registarske mašine, beskonačni abakus i razni minimalistički programski jezici (kao što je BF). Na kraju poglavlja, razmatraju se alternativni modeli izračunljivosti koji se ne oslanjaju ni na kakav koncept računske mašine, kao što su Kleeneov koncept rekurzivnih funkcija, Postovi sistemi zamjene, Markovljevi normalni algoritmi te, na kraju, Churchov l-račun.

Na kraju udžbenika nalaze se i četiri dodatka. Dodatak A ubačen je na insistiranje pojedinih zainteresiranih studenata, a posvećen je Veitchovim dijagramima, vrlo korisnoj grafoanalitičkoj varijanti Quineovog algoritma, koji se obrađuje u Poglavlju 1, a koji je posebno praktičan za slučaj malog broja promjenljivih. Dodatak B daje spisak bibliografskih referenci razvrstan po poglavljima, Dodatak C sadrži indeks korištenih pojmova, dok Dodatak D sadrži indeks osoba koje se spominju u udžbeniku.

Ovaj udžbenik prati i odgovarajuća web podrška, koja se nalazi na adresi dm.etf.unsa.ba. Ova podrška je još uvijek u razvoju, ali ono što je sigurno je da će se na njoj nalaziti rješenja odabranih a u dogledno vrijeme možda i svih zadataka koji su postavljeni u udžbeniku kao zadaci za samostalan rad (na kraju svakog od poglavlja). Pored toga, na istom mjestu moći će se naći korekcije eventualnih naknadno uočenih grešaka, razne dopune materijala, interesantni problemi za rješavanje, odgovori na često postavljana pitanja, i druge slične stvari.

Pored autora, mnogi drugi ljudi su također zaslužni što se ovaj udžbenik pojavio u ovakvoj formi. Na prvom mjestu, autor se duboko zahvaljuje recenzentima akademiku dr. Branislavi Peruničić, profesoru emeritusu na Elektrotehničkom fakultetu Univerziteta u Sarajevu, dr. Senadi Kalabušić, vanrednom profesoru na Prirodno-matematičkom fakultetu Univerziteta u Sarajevu i dr. Aleksandri Kostić, docentu na Mašinskom fakultetu Univerziteta u Sarajevu, što su se prihvatili mukotrpnog posla recenzije ovog udžbenika i na pozitivnim recenzijama. Dalje, autor veliku zahvalnost duguje Harunu Šiljku, inžinjeru elektrotehnike i (u vrijeme pisanja ovog udžbenika) studentu master studija na Elektrotehničkom fakultetu u Sarajevu, za mnogobrojne sugestije i ukazivanje na uočene greške u materijalu, kao i za prikupljanje osnovnih biografskih podataka o ličnostima citiranim u udžbeniku. Također, brojni studenti Elektrotehničkog fakulteta u Sarajevu koji su spremali ispit iz predmeta “Diskretna matematika” prema skriptama koje su u osnovi odabrani fragmenti iz ovog udžbenika, ukazali su autoru na izvjesne greške i nedostatke u udžbeniku, što je uzeto u obzir. Među njima posebno se istakla Maida Arnautović, u vrijeme pisanja ovog udžbenika studentica II godine Odsjeka za računarstvo i informatiku Elektrotehničkog fakulteta u Sarajevu. Na kraju, autor duguje veliku zahvalnost supruzi Maji, sinu Adrianu i kćerki Nini na nesebičnoj podršci i pokazanom razumijevanju za izgubljeno vrijeme utrošeno za pisanje ovog udžbenika.

Autor:

Dr. Željko Jurić