Odabrana poglavlja iz diskretne matematike

Sadrzaj Predgovor . . . . . VII Iz predgovora prvom izdanju knjige 'Diskretna matematika' . . . . . VIII Iz predgovora drugom izdanju knjige 'Diskretna matematika' . . . . . . . . X Iz predgovora prvom izdanju knjige 'Diskretne matematicke strukture' . . . X 1. Teorija grafova . . . . . . 1 1.1 Pregled elementarnih pojmova . . . . . . 1 1.2 Hromatski broj grafa . . . . . . . 8 1.3 Broj unutrasnje i spoljasnje stabilnosti grafa . . . . . . 12 1.4 Eulerovi i Hamiltonovi putevi . . . . . . . 14 1.5 Povezanost grafova . . . . . 18 1.6 Grafovski algoritmi . . . . . . . . 19 1.6.1 Reprezentacije grafova . . . . . . 20 1.6.2 Pretrage grafova . . . . . 21 1.6.3 Neki osnovni grafovski algoritmi . . . . . . . . 28 1.7 Zadaci . . . . . . . . 33 2. Mreze . . . . . . . 41 2.1 Mreze kao relacijske strukture . . . . . . 41 2.2 Mreze kao algebarske strukture . . . . . . 47 2.3 Razni tipovi mreza . . . . . 49 2.4 Teorema o nepokretnoj tacki . . . . . . . 53 2.5 Zadaci . . . . . . . . 54 3. Metodi optimizacije . . . . . . 59 3.1 Linearno programiranje . . . . . . 59 3.1.1 Osnovni pojmovi . . . . . . . . 60 3.1.2 Simpleks metod . . . . . 65 3.1.3 Dualnost u linearnom programiranju . . . . . 74 3.1.4 Polinomijalni metodi za linearno programiranje . . . . . . . 76 3.2 Osnovi teorije igara . . . . . . . . 78 3.2.1 Matricne igre . . . . . . 79 3.2.2 Matricne igre sa sedlastom tackom . . . . . . 80 3.2.3 Mesovite strategije . . . . . . . 82 3.2.4 Svodjenje na zadatak linearnog programiranja . . . . . . . . 85 3.2.5 Igre na grafovima . . . . . . . . 86 3.3 Nelinearni problemi optimizacije . . . . . 87 3.4 Celobrojno programiranje . . . . . 89 3.5 Dinamicko programiranje . . . . . 92 3.6 Mrezno planiranje . . . . . 95 3.7 Zadaci . . . . . . . . 99 4. Kombinatorna optimizacija . . . . . . 111 4.1 Najkraca povezujuca mreza . . . . . . . . 112 4.2 Ekstremalni putevi u mrezi . . . . . . . . 114 4.3 Maksimalni protok u mrezi . . . . . . . . 118 4.4 Problem trgovackog putnika . . . . . . . . 125 4.5 Zadaci . . . . . . . . 127 5. Algebarske strukture sa vise operacija . . . . . . . 129 5.1 Prsten . . . . . . . . 129 5.2 Telo i polje. Konacno polje . . . . . . . . 133 5.3 Univerzalne algebre . . . . . . . . 137 5.4 Zadaci . . . . . . . . 139 6. Algoritmi i njihova kompleksnost . . . . . . 145 6.1 Rekurzivne i izracunljive funkcije . . . . . 145 6.2 Turingova masina . . . . . 148 6.3 Kompleksnost algoritama i problema . . . . . . . 150 6.4 Heuristike za NP-probleme . . . . . . . . 155 6.5 Zadaci . . . . . . . . 157 7. Formalne teorije i automatsko rezonovanje . . . . . . . . 159 7.1 Motivacija . . . . . 159 7.2 Denicija formalne teorije . . . . . 162 7.3 Iskazni racun i drugi primeri formalnih teorija . . . . . 163 7.4 Herbrandova teorema . . . . . . . 166 7.5 Princip rezolucije . . . . . . 170 7.6 Heuristike u izvodjenju . . . . . . 174 7.7 Lambda racun . . . . . . . 177 7.8 Zadaci . . . . . . . . 178 8. Teorija kodova . . . . . . 183 8.1 Osnovni pojmovi teorije kodova . . . . . 184 8.2 Linearni kodovi . . . . . . . 187 8.3 Savrseni kodovi . . . . . . . 194 8.4 Pregled vaznijih kodova . . . . . . 196 8.5 Shanonov problem . . . . . 197 8.6 Linearni rekurentni nizovi . . . . . 200 8.7 Zadaci . . . . . . . . 205 Literatura . . . . . 209