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ů.

  • Mocnění intervalových matic [zabráno]
  • Určit přesný rozsah hodnot druhé mocniny intervalové matice [A]2 je jednoduché, ale pro třetí mocninu je to už výpočetně složité - NP-těžké. Pro vyšší mocniny pak prakticky musíme rozsahy složek aproximovat. Cílem projektu je prozkoumat různé způsoby spočítání obálky hodnot k-té mocniny intervalové matice. Nabízí se standardní mocnění intervalovou aritmetikou nebo využití spektrálního rozkladu, případně další způsoby. Součástí řešení by mělo být odvození různých způsobů řešení, implementace matod a jejich numerické porovnání různých přístupů. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. H.S. Ahn, K.L. Moore and Y.Q. Chen. Iterative Learning Control. Robustness and Monotonic Convergence for Interval Systems. Springer, 2007.
    2. Z. Haiyan, A note about power-boundedness of interval matrices. J. Comput. Appl. Math. 31(2), 1990.
    3. 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.
    4. O. Kosheleva, V. Kreinovich, G. Mayer, and H.T. Nguyen. Computing the cube of an interval matrix is NP-Hard. In Proceedings of the 2005 ACM symposium on Applied computing (SAC '05), Lorie M. Liebrock (Ed.). ACM, New York, NY, USA.

  • 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.

  • Vyhodnocení polynomu s intervalovými koeficienty [zabráno]
  • Pro daný polynom s intervalovými koeficienty chceme najít co nejtěsnější obálku funkčních hodnot pro dané body. Kromě přímého použití intervalové aritmetiky (pomocí Hornerova schematu) existují i jiné metody, například pomocí tzv. Bernsteinových polynomů. Cílem práce je implementace zmíněných metod a jejich porovnání, případně vylepšení. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. J. Garloff and A. P. Smith. Preface. Special Issue on the Use of Bernstein Polynomials in Reliable Computing: A Centennial Anniversary. Reliable Computing 17, 2012.
    2. V. Stahl. Interval methods for bounding the range of polynomials and solving systems of nonlinear equations. Dissertation, Johannes Kepler University Linz, Austria, 1995.

  • Speciální soustavy s parametrickými závislostmi koeficientů při navrhování příhradových konstrukcí [zabráno]
  • 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.

  • Intervalová Mongeova matice v silném a slabém smyslu
  • Mongeova matice je definovaná jednoduchou podmínkou a hraje důležitou roli v několika problémech. Například v dopravních úlohách charakterizuje velice efektivně řešitelné případy. Cílem práce je zobecnit tyto matice na intervalové v silném smyslu (všechny jsou Mongeovy) a slabém smyslu (aspoň jedna je Mongeova). Bude nás zajímat charakterizace těchto vlastností, jejich složitost a postačující/nutné podmínky.

    Odkazy:

    1. R.E. Burkard, B. Klinz, R. Rudolf. Perspectives of Monge properties in optimization. Discrete Appl. Math., 70, 95-161, 1996.
    2. M. Fiedler. Remarks on Monge matrices. Mathematica Bohemica, 127(1), 27-32, 2002.
    3. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.



    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í [zabráno]
  • 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