Přednáška je věnována numerickému řešení problémů dynamické elasticity a stlačitelného proudění. Uvažujeme lineární pružnost a nelineární St. Venantův-Kirchhoffův model. Prostorová diskretizace je realizována pomocí nespojité Galerkinovy metody. Pro časovou diskretizaci bylo navrženo a testováno několik technik. Jako nejpřesnější se ukazuje časoprostorová nespojitá Galerkinova metoda. Tato metoda byla rovněž aplikována na řešení problému stlačitelného proudění v časově závislých oblastech formulovaného pomocí tzv. ALE (arbitrary Lagrangian-Eulerian) metody.

Abstract

For the past 40 years computer scientists generally believed that NP-complete problems are intractable. In particular, Boolean satisfiability (SAT), as a paradigmatic NP-complete problem, has been considered to be intractable. Over the past 20 years, however, there has been a quiet, but dramatic, revolution, and very large SAT instances are now being solved routinely as part of software and hardware design.
In this talk I will review this amazing development and show that we can leverage SAT solving to accomplish other Boolean reasoning tasks. Counting the the number of satisfying truth assignments of a given Boolean formula or sampling such assignments uniformly at random are fundamental computational problems in computer science with numerous applications. While the theory of these problems has been thoroughly investigated in the 1980s, approximation algorithms developed by theoreticians do not scale up to industrial-sized instances. Algorithms used by the industry offer better scalability, but give up certain correctness guarantees to achieve scalability. We describe a novel approach, based on universal hashing and Satisfiability Modulo Theory, that scales to formulas with hundreds of thousands of variable without giving up correctness guarantees.

Náboj je mezinárodní matematická soutěž pro pětičlenné týmy středoškoláků, které reprezentují jednotlivé školy. Celá soutěž trvá 120 minut, během nichž se týmy snaží na jednom ze soutěžních míst vyřešit co nejvíce příkladů.

Abstract

This talk is about a curious phenomenon, which concerns the reliable estimation of principal components in the face of severe corruptions. Here, the scientist is given a data matrix which is the sum of an approximately low-rank matrix and a sparse matrix modeling corrupted entries. In addition, many entries may be missing. Hence, we have a blind de-mixing problem in which the goal is to recover the low-rank structure and find out which entries have been corrupted. We present a novel approach to this problem with very surprising performance guarantees as well as a few applications in computer vision and biomedical imaging, where this technique opens new perspectives.