Home  
  Teaching  
  Research  
  Misc  
Milan Hladík
Teaching

Ročníkové projekty a bakalářské práce

Projekty a práce tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. U projektů preferuji pokračování do bakalářské práce.

Některá témata jsou v SISu. Další navrhovaná témata jsou dole (můžete přijít i s vlastním tématem), jedná se zejména o problémy z intervalového počítání, proto jsem sepsal pár základních informací a odkazů o intervalovém počítání. Může se také hodit pár užitečných odkazů.

  • Utažení pivota pro parametrické lineární soustavy rovnic
  • Utažení pivota je způsob jak zefektivnit (z hlediska výsledné obálky množiny řešení) metody na řešení soustav intervalových lineárních rovnic, a to konkrétně Gaussovy eliminace pro obecnou soustavu a Choleského rozklad pro soustavu s positivně definitní maticí. Cílem projektu je rozšířit tento způsob na intervalové soustavy s lineárními závislostmi. Součástí by mělo být i numerické porovnání s jinými metodami řešení. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. J. Garloff. Pivot tightening for direct methods for solving symmetric positive definite systems of linear interval equations. Comput. 94(2-4):97-107, 2012.
    2. J. Garloff. Interval Gaussian elimination with pivot tightening. SIAM J. Matrix Anal. Appl. 30(4):1761-1772, 2009.
    3. M. Hladík. Enclosures for the solution set of parametric interval linear systems. Int. J. Appl. Math. Comput. Sci., 22(3):561–574, 2012.

  • Předpodmínění a regularita symetrických intervalových matic
  • Předpodmínění se často používá pro řešení intervalových (i neintervalových) soustav rovnic. Různá předpodmiňovací matice samozřejmě vede k různým výsledkům. Cílem projektu je prozkoumat různé způsoby předpodmínění symetrické intervalové matice pro účely testování regularity. Dále, použít výsledky pro těsné odhady vlastních čísel symetrických intervalových matic. Součástí by mělo být i numerické porovnání různých přístupů. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. M. Hladík, D. Daney, and E. P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput. 217(12):5236-5242, 2011.
    2. M. Hladík, D. Daney, and E. P. Tsigaridas. Bounds on Real Eigenvalues and Singular Values of Interval Matrices. SIAM J. Matrix Anal. Appl. 31(4):2116-2129, 2010.
    3. M. Hladík. Optimal Preconditioning for the Interval Parametric Gauss–Seidel Method. SCAN 2015, Wuerzburg, Germany.
    4. Arnold Neumaier. Interval methods for systems of equations. Cambridge University Press, 1990.

  • Obraz boxu při bilineárním a kvadratickém zobrazení
  • Obraz intervalového boxu při bilineárním a kvadratickém zobrazení se dá snadno odhadnout vyhodnocením intervalovou aritmetikou, ale výsledek může být značně nadhodnocen. Cílem této práce je vylepšit tyto základní odhady použitím algebraických maticových dekompozic, linearizací používaných v optimalizaci, heuristik a jiných technik. Součástí by měla být implementace a numerické porovnání metod. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. C. A. Floudas. Deterministic Global Optimization. Theory, Methods and Applications, Kluwer, 2000.
    2. Arnold Neumaier. Interval methods for systems of equations. Cambridge University Press, 1990.
    3. S. M. Rump. Verification methods: Rigorous results using floating-point arithmetic. Acta Numer., 19:287-­449, 2010.

  • Grafické znázornění komplexních vlastních čísel intervalové matice
  • Problém spočívá ve vykreslení množiny všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Tato množina není jednoduše popsatelná, a proto se musí aproximovat. Například metody založené na principu branch & bound aproximují množinu s libovolnou přesností. Cílem projektu je navrhnout a implementovat metodu, která vykreslí tyto množiny s předem danou přesností. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. E. Garajová: Intervalový solver nelineárních podmínek, 2014.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J. Rohn. Checking properties of interval matrices. Technical Report 686, Institute of Computer Science, Academy of Sciences of the Czech Republic, 1996.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Lokalizace vlastních čísel intervalových matic [zabráno]
  • Zde nás zajímá množina všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Cílem práce je zapouzdřit tuto množinu pomocí jednoduchých odhadů založených na Gerschgorinových discích, Cassiniho oválech a dalších pokročilých technik. Konkrétně, jedná se o adaptaci výše zmíněných metod na intervalové matice, porovnání metod a jejich implementace. Programovací část (jazyk Matlab/Octave + Intlab) zahrnuje i vizualizaci odhadů.

    Odkazy:

    1. H.-B. Li, T.-Z. Huang, and H. Li On some subclasses of P-matrices. Numer. Linear Algebra Appl., 14: 391–405, 2007.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J.M. Peña. On an alternative to Gerschgorin circles and ovals of Cassini. Numer. Math., 95(2): 337-­345 , 2003.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Pole hodnot intervalové matice [zabráno]
  • Pole hodnot matice je množina komplexních čísel, která zapouzdřuje vlastní čísla matice. Používá se jako odhad umístění vlastních čísel. Práce by se zabývala polem hodnot intervalové matice. Praktická část by se věnovala vykreslení (přesného či přibližného) pole hodnot jako množiny v komplexní rovině. Teoretická část by prozkoumala vlastnosti pole hodnot intervalové matice ve srovnání s vlastnosti reálné matice. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. R.A. Horn and C.R. Johnson. Topics in Matrix Analysis. Cambridge University, 1991.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584-5591, 2013.
    3. L. Vacek. Pole hodnot matice: Teorie a výpočet. bakalářská práce, KNM MFF UK, 2016.

  • AE řešitelnost intervalových soustav
  • Určité úlohy v robotice vedou na lineární systémy s intervalovými parametry, přičemž parametry jsou dvojího druhu. Cílem je otestovat, zda pro všechny hodnoty jednoho druhu existuje výběr hodnotu druhého druhu, aby systém byl přípustný. V řeči intervalového počítání: jde nám o to zjistit, zda je systém tzv. AE řešitelný. O AE řešitelnosti se neví mnoho. Cílem projetu je adaptovat a implementovat určité postačující/nutné podmínky na řešitelnost a případně je rozšířit na úlohy s lineárními závislostmi. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. M. Hladík. AE solutions and AE solvability to general interval linear systems. Linear Algebra Appl., 465(0):221-238, 2015.
    2. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    3. L. Jaulin et al. Applied Interval Analysis. With examples in parameter and state estimation, robust control and robotics. Springer, London, 2001.

  • Speciální soustavy s parametrickými závislostmi koeficientů při navrhování příhradových konstrukcí
  • Soustavy rovnic, které vznikají při navrhování příhradových konstrukcí, mají specifickou strukturu. Pokud máme zohlednit určitou míru nepřesnosti vstupních dat, vede to na problém řešení speciálních lineárních soustav rovnic s parametry. Jako řešení hledáme intervalové zapouzdření všech možných řešení soustavy pro všechny přípustné hodnoty parametrů. Cílem práce by bylo porovnat, a případně vylepšit, různé alternativní metody se základní metodou Neumaiera a Pownuka. Pokusíme se získat reálná data, aby porovnání bylo co nejvěrohodnější. Programovací jazyk: Matlab + Intlab.

    Odkazy:

    1. A. Neumaier and A. Pownuk. Linear Systems with Large Uncertainties, with Applications to Truss Structures. Reliable Computing 13:149-172, 2007.



    Ryze teoretické bakalářské práce

    Co to je teoretická bakalářka a mám se toho bát? Ne, rozhodně není třeba se bát. Pokud si student vybere téma, které ho baví a věnuje tomu přiměřené úsilí, pak je riziko neúspěchu minimální. Teoretická bakalářka je typicky zaměřená na speciální problém, který ještě nikdo neřešil, nebo na rozšíření známých výsledků na větší třídu úloh. Proto když student na začátku nastuduje problematiku, tak má připravenou půdu ke zdárnému výsledku. Zde samozřejmě závisí na invenci a píli studenta, a na kousku štěstí k jak velkým výsledkům se dostane. Historie ale ukazuje, že studenti naší katedry mají dobré výsledky, leckdy i publikovatelné v odborném tisku, a také bývají úspěšní v soutěžích typu SVOČ.

  • Geometrie intervalových lineárních soustav
  • Množina řešení čtvercové soustavy intervalových lineárních rovnic je tvořena polyedrem, který je obecně nekonvexní, ale je konvexní v každém ortantu. Pro tuto množinu jsou známy zajímavé geometrické vlastnosti a podmínky jak se dá vyjádřit její konvexní obal, nebo kdy je automaticky konvexní. Cílem práce prozkoumat zobecnění těchto výsledků na přeurčené intervalové soustavy rovnic a na soustavy nerovnic.

    Odkazy:

    1. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.
    2. J. Rohn. Systems of linear interval equations. Linear Algebra Appl., 126(C):39-78, 1989.
    3. J. Rohn. A manual of results on interval linear problems. Technical Report 1164, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.

  • Speciální třídy P-matic v intervalovém prostředí
  • P-matice jsou důležité matice s mnoha pěknými vlastnostmi, mj. zaručují, že úloha lineární komplementarity má jednoznačné řešení. Rozpoznávání, zda je daná matice P-maticí, je však NP-těžké. Proto byly navrženy různé speciální třídy P-matic, které jsou snadněji ověřitelné. Cílem práce je prozkoumat tyto speciální třídy pro případ intervalové matice, adaptovat podmínky na rozpoznávání jednotlivých typů matic a vyšetřit jejich vlastnosti.

    Odkazy:

    1. M. Hladík. An overview of polynomially computable characteristics of special interval matrices. preprint arXiv: 1711.08732, 2017.
    2. J.M. Pena. A class of P-matrices with applications to the localization of the eigenvalues of a real matrix. SIAM J. Matrix Anal. Appl., 22(4):1027-1037, 2001.
    3. M.J. Tsatsomeros. Generating and detecting matrices with positive principal minors. In L. Li, ed., Focus on Computational Neurobiology, Nova Science Publishers, pp. 115-132, 2004

  • Zobecněná Perron-Frobeniova teorie pro intervalové matice
  • Perron-Frobeniova teorie říká, že nezáporné matice mají z hlediska vlastních čísel a vlastních vektorů speciální vlastnosti. Nezápornost matice A znamená, že A leží v kuželi nezáporných směrů. Jedno z možných rozšíření uvažuje obecný kužel a zobecňuje některé výsledky pro tento případ. Cílem práce je prozkoumat tuto zobecněnou teorii, adaptovat výsledky na intervalové matice a vyjádřit podmínky na ověření předpokladů.

    Odkazy:

    1. M. Hladík. An overview of polynomially computable characteristics of special interval matrices. preprint arXiv: 1711.08732, 2017.
    2. L. Hogben. Handbook of Linear Algebra. CRC Press, Second Edition, 2014

  • Celočíselné lineární programování s intervalovými koeficienty
  • Lineární programování (LP) a celočíselné LP jsou základní úlohy optimalizace, používané k řešení mnoha praktických úloh. Reálná data ale jsou často odhadnuta či známa jen s určitou přesností. To vede na úlohy s intervalovými daty. Zatímco intervalové LP je předmětem zkoumání řadu let, o celočíselném se ví mnohem méně. Cílem práce je prozkoumat, které výsledky z intervalového LP platí pro celočíselný případ a které již nikoliv. U těch druhých se pokusit je adaptovat na celočíselné prostředí.

    Odkazy:

    1. M. Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming - New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
    2. J. Rohn. A manual of results on interval linear problems. Technical Report 1164, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.
    3. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.



    Diplomové práce

    Tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. Některá témata jsou v SISu. Další navrhovaná témata (můžete přijít i s vlastním tématem):

  • Verifikace v lineárním programování
  • Používání floating-point aritmetiky vede k zaokrouhlovacím chybám a v důsledku toho mohou solvery na lineární programování dávat chybné výsledky. Verifikační metody jsou postupy, které dokážou potvrdit optimalitu vypočítaného řešení (resp. optimální báze) vhledem k dané přesnosti. Cílem práce by bylo zmapovat verifikaci v lineárním programování, porovnat a případně navrhnout vylepšení. Předpokládá se i implementace ve vhodném prostředí - nejspíše v Matlabu s použitím Intlabu.

    Odkazy:

    1. Christian Jansson. Rigorous Lower and Upper Bounds in Linear Programming, SIAM J. Optim. 14(3): 914-935, 2004.
    2. Arnold Neumaier and Oleg Shcherbina. Safe bounds in linear and mixed-integer linear programming, Math. Program., Ser. A, 99(2):283-296, 2004.
    3. Siegfried M. Rump. Verification methods: Rigorous results using floating-point arithmetic, Acta Numerica 19: 287-449, 2010.
    4. Jiří Rohn. VERSOFT: Verification software in MATLAB / INTLAB, version 10, 2009.
    5. Christian Keil and Christian Jansson. Computational Experience with Rigorous Error Bounds for the Netlib Linear Programming Library , Reliab. Comput. 12(4): 303-321, 2006.
    6. Christian Keil. Lurupa - Rigorous Error Bounds in Linear Programming, Dagstuhl Seminar Proceedings 05391, 2006.

  • Intervalová maticová norma
  • Jsou známy různé způsoby jak rozšířit maticové normy na intervalové matice. Cílem této práce by bylo porovnat různé normy mezi sebou, jak moc je těsná ekvivalence mezi nimi, zjistit jejich vlasnosti (konsistence, výpočetní složitost atp.). Zajímavým rozšířením by bylo zobecnění norem tak, aby měly intervalovou hodnotou.

    Odkazy:

    1. R. Farhadsefat, J. Rohn and T. Lotfi. Norms of interval matrices. Technical Report No. 1122, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague 2011.
    2. Behnam Hashemi and Hanieh Tavakolipour. A non-induced interval matrix norm. Reliable Computing 18, 144-146, 2013.
    3. Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University, 1985.

  • Exponenciála s intervalovou maticí
  • Exponent s maticí je definován přirozeně pomocí Taylorovy řady jako matice eA=∑k=0Ak/k!. Cílem je určit co nejlepší dolní a horní odhady na prvky eA pokud prvky matice A perturbujeme v rámci předem daných intervalů. Motivace tohoto problému pochází v mikro-robotiky, vzniká při hledání robustního řešení v teorii řízení robota.

    Odkazy:

    1. Micky Rakotondrabe, homepage.
    2. Alexandre Goldsztejn. On the Exponentiation of Interval Matrices, arXiv, 2009.
    3. M. Althoff, O. Stursberg, and M. Buss. Reachability analysis of linear systems with uncertain parameters and inputs. In Proc. of the 46th IEEE Conference on Decision and Control, 726-732, 2007.
    4. E.P. Oppenheimer and A.N. Michel. Application of Interval Analysis Techniques to Linear Systems. II. The Interval Matrix Exponential Function. IEEE Trans. Circuits Syst., 35(10):1230-1242, 1988.

  • Porovnání metod intervalového lineárního programování
  • Úlohou intervalového lineárního programování rozumíme množinu úloh lineárního programování, v nichž parametry nabývají hodnot z daných intervalů. Jedním z cílů tohoto problému je najít extrémní meze, ve kterých se nabývají optimální hodnoty jednotlivých lineárních programů. To lze řešit různými metodami, např. dekompozicí na exponenciálně mnoho lineárních programů, metodami globální optimalizace či nehladké nekonvexní optimalizace. Cílem práce je implementace a porovnání základních metod s využitím vhodných dolních a horních odhadů na meze optimálních hodnot. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. E. Hansen and G.W. Walster. Global optimization using interval analysis. 2nd ed., Marcel Dekker, 2004.
    2. M. Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming - New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
    3. M. Hladík. On approximation of the best case optimal value in interval linear programming. Optim. Lett., 8(7):1985–1997, 2014.
    4. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156–4165, 2013.

  • Silné Nashovo ekvilibrium v intervalových maticových hrách
  • Nashovo ekvilibrium je takový rovnovážný výběr strategií, že žádnému hráči se nevyplatí jeho stretegii změnit, protože by si pohoršil. Silné Nashovo ekvilibrium je pak taková situace, že ani žádná koalice hráčů si nepolepší. Polepšením výplaty koalice myslíme, že by se mohli domluvit mezi sebou, změnit stretegii a každý ze členů koalice by měl větší výplatu. Zatímco Nashovo ekvilibrium existuje, silné již existovat nemusí. Cílem práce je prozkoumat silné Nashovo ekvilibrium pro hry s intervalovými maticemi, navrhnout postup jak určit, že existuje instance se silným ekvilibriem (resp., že všechny instance jej mají).

    Odkazy:

    1. R. Aumann. Acceptable points in general cooperative n-person games, Acceptable points in general cooperative n-person games, in "Contributions to the Theory of Games IV", Princeton Univ. Press, Princeton, N.J., 1959.
    2. M. Hladík. Interval valued bimatrix games. Kybernetika, 46(3):435-446, 2010.
    3. B. Kubica, A. Wozniak. Interval methods for computing strong Nash equilibria of continuous games. Decision Making in Manufacturing and Services, 9(1), 63-78, 2016.
    4. R. Nessah, G. Tian. On the existence of strong Nash equilibria. J. Math. Anal. Appl., 414(2), 871-885.



    Další užitečné odkazy