Matematický ústav Slovenskej akadémie vied, detašované pracovisko v Košiciach SK  EN 
O nás
Aktivity
Výskum
Vzdelávanie

Seminár detašovaného pracoviska Matematického ústavu SAV v Košiciach

2010   •   2011   •   2012   •   2013   •   2014   •   2015   •   2016   ···
 
24. 1. 2013 Edita Pelantová (FJFI ČVUT, Praha) – Paralelné sčítanie v neštandardných číselných sústavách
Abstrakt: Je známe, že sčítanie v klasickej decimálnej alebo binárnej sústave má lineárnu časovú náročnosť v závislosti na dĺžke sčítaných reťazcov. To bráni návrhu efektívnej aritmetickej jednotky.
V roku 1961, Avizienis popísal paralelný algoritmus na sčítanie v číselnej sústave s bázou $10$ a množinou cifier $\{-6, -5, ..., 5, 6\}$. Pri jeho algoritme je prenos cifry obmedzený, a to umožňuje pri dostatočnom počte procesorov sčítať dve čísla v konštantnom čase nezávislom na dĺžke reťazcov. Tento Avizienisov nápad sa dnes používa na urýchlenie algoritmov pre násobenie a delenie.
V prednáške uvažujeme číselné sústavy dané základom $b$, kde $b$ je algebraické číslo, $|b| > 1$. Ukážeme, že ak žiadny z ďalších koreňov minimálneho polynómu $f(x)$ čísla $b$ nie je v absolútnej hodnote rovný $1$, je možné nájsť konečnú abecedu (množinu cifier), pri ktorej sa dá paralelne sčítať.
Vo všeobecnosti je získaná abeceda zbytočne veľká. Odvodíme dolný odhad na kardinalitu abecedy, ktorá umožňuje paralelné sčítanie. Tento odhad je $|f(1)|$ a v prípade kladnej bázy ho možno ešte vylepšiť na $|f(1)|+2$. Na niekoľkých používaných sústavách ukazujeme, že táto medza sa nadobúda:
a ďalšie. Budeme diskutovať zatiaľ nevyriešenú otázku existencie ideálnej sústavy, v ktorej by bolo možné paralelné sčítanie v abecede $\{0,1\}$.
4. 2. 2013 Ján Borsík – O vlastnostiach topologických priestorov súvisiacich s kvázispojitosťou reálnych funkcií
Abstrakt: Topologický priestor $X$ má vlastnosť CP ak pre každú uzavretú riedku množinu $F\subseteq X$ existuje spojité zobrazenie $f:X\setminus F\to [0,1]$, ktorého oscilácia v bodoch množiny $F$ je $1$. Podobne, priestor $X$ má vlastnosť QP ak ak pre každú uzavretú riedku množinu $F\subseteq X$ existuje kvázispojité zobrazenie $g:X\setminus F\to [0,1]$, ktorého oscilácia v bodoch množiny $F$ je $1$. Ukážeme, že Niemyckého rovina má vlastnosť QP, ale nemá vlastnosť CP.
25. 2. 2013 Peter Eliaš – Dva problémy súvisiace s ohraničenosťou trigonometrických radov
Abstrakt: Uvažujme kružnicu $\mathbb{T}\simeq\mathbb{R}/\mathbb{Z}\simeq\{z\in\mathbb{C}:|z|=1\}$ ako kompaktnú poľskú grupu s metrikou $\varrho(x,y)=\|x-y\|$, kde $\|x\|$ zodpovedá vzdialenosti reálneho čísla $x$ od najbližšieho celého čísla. V práci [P. Eliaš, A hierarchy of thin sets related to the boundedness of trigonometric series, Proceedings of the AMS 128 (2000), 3341–3347] boli formulované dva problémy.
Zatiaľ čo odpoveď na prvú otázku je negatívna, druhý problém ostáva otvorený.
12. 3. 2013 Roman Frič – Poznámky o rozširovaní pravdepodobnostnej miery
Abstrakt: Cieľom referátu je informovať o zameraní a doterajších výsledkoch mojej doktorandky Jany Havlíčkovej, ktorej téma dizertačnej práce je „Topologické metódy v pravde­podobnosti“. Motivačným príkladom je rozširovanie pravde­podobnostných mier z poľa množín na generované $\sigma$-pole a jeho topologická podobnosť s Čechovou-Stoneovou kompaktifikáciou. Ukazuje sa možnosť popísať (metódami teórie kategórií) konštrukciu rozšírenia pravde­podobnostných mier na najväčší možný systém, ktorým sú tzv. absolútne merateľné množiny (merateľné voči všetkým pravde­podobnostným mieram na danom poli množín).
Nech $\mathbf{A}$ je pole podmnožín $X$ a nech $p:\mathbf{A}\rightarrow I$ je pravde­podobnostná miera. Pre $B\subseteq X$ definujeme $p^*(B)=\inf\big\{\sum_{i=1}^\infty p(A_i);\,B\subseteq \bigcup_{i=1}^\infty A_i,\,A_i\in \mathbf{A}\big\},$ výsledné zobrazenie $p^*:\mathbf{P}(X)\rightarrow I$ sa nazýva indukovaná vonkajšia miera. Množina $M\subseteq X$ sa nazýva $p$-merateľná, ak pre každú množinu $B\subseteq X$ platí $p^*(B)=p^*(B\cap M)+p^*(B\cap M^c)$, kde $M^c=X\setminus M$. Označme $\mathbf{M}_p$ množinu všetkých $p$-merateľných podmnožín $X$. Platia nasledujúce dôležité tvrdenia.
Veta. Nech $\mathbf{A}$ je pole podmnožín $X$ a nech $p$ je pravde­podobnostná miera na $\mathbf{A}$.
Označme $\mathbf{M}_{\mathbf{A}}=\bigcap_{p\in \mathcal{P}(\mathbf{A})}\mathbf{M}_p.$ Zrejme, $M\subseteq X$ patrí do $\mathbf{M}_\mathbf{A}$ práve ak je $p$-merateľná pre všetky $p\in \mathcal{P}(\mathbf{A})$, $\sigma(\mathbf{A})\subseteq\mathbf{M}_{\mathbf{A}}$ a $\mathbf{M}_\mathbf{A}$ je $\sigma$-pole podmnožín $X$.
Definícia. Nech $\mathbf{A}$ je pole podmnožín $X$. Prvky množiny $\mathbf{M}_\mathbf{A}$ nazývame absolútne $\mathbf{A}$-merateľné množiny.
Vo všeobecnosti platí $\mathbf{M}_\mathbf{A}\setminus\sigma(\mathbf{A})\neq\emptyset$.
Definícia. Nech $\mathbf{A}$ je pole podmnožín množiny $X$ a nech $p$ je pravde­podobnostná miera na $\mathbf{A}$. Nech $\mathbf{B}$ je pole podmnožín množiny $X$ také, že $\mathbf{A}\subseteq \mathbf{B}$ a nech $q$ je pravde­podobnostná miera na $\mathbf{B}$ taká, že $p(A) = q(A)$ pre všetky $A\in \mathbf{A}$. Ak pre všetky $B\in\mathbf{B}$ platí $q(B) = \inf\big\{\sum_{i=1}^\infty p(A_i);\,B\subseteq \bigcup_{i=1}^\infty A_i,\,A_i\in \mathbf{A}\big\}$, tak $q$ sa nazýva merateľným rozšírením $p$.
Zhrnutie. Nech $\mathbf{A}$ je pole podmnožín množiny $X$. Potom $\mathbf{M}_\mathbf{A}$ je najväčšie $\sigma$-pole podmnožín $X$ také, že obsahuje $\sigma(\mathbf{A})$ a ku každej pravde­podobnostnej miere $p\in \mathcal{P}(\mathbf{A})$ existuje jediná pravde­podobnostná miera $p_\mathbf{A}\in \mathcal{P}(\mathbf{M}_\mathbf{A})$, ktorá je merateľným rozšírením $p$ z $\mathbf{A}$ na $\mathbf{M}_\mathbf{A}$.
26. 3. 2013 Tomáš Gregor – Gyrogrupy
Abstrakt: Dvojica $(G,\oplus)$, kde $G$ je neprázdna množina a $\oplus$ je binárna operácia na $G$ sa nazýva gyrogrupa, ak operácia $\oplus$ má ľavý neutrálny prvok, každý prvok má ľavý inverzný prvok a existuje zobrazenie $\mathrm{gyr}: G\times G \rightarrow Aut(G,\oplus)$ také, že $a\oplus(b\oplus c)=(a\oplus b)\oplus \mathrm{gyr}[a,b]c$ a $\mathrm{gyr}[a,b]=\mathrm{gyr}[a\oplus b,b]$. Ak naviac $a\oplus b=\mathrm{gyr}[a,b](b\oplus a)$, tak gyrogrupa je gyrokomutatívna.
Einsteinova operácia
na množine $\{\mathbf{u}\in V; \langle\mathbf{u},\mathbf{u}\rangle\lt c^2\}$, kde $V$ je vektorový priestor so skalárnym súčinom $\langle\,\cdot\,,\cdot\,\rangle$ a $c\in \mathbb{R}$, tvorí gyrokomutatívnu gyrogrupu. Špeciálne, $(-c,c)\subset \mathbb{R}$ je komutatívna grupa s operáciou
$u\oplus v=\displaystyle\frac{u+v}{1+\frac{u v}{c^2}}$.
9. 4. 2013 Ján Haluška – Multipolárny vektorový priestor s operáciami násobenia a delenia
Abstrakt: Pokúsime sa axiomaticky definovať „multipolárny vektorový priestor“ ako potenciálne zovšeobecnenie viacerých matematických štruktúr majúcich multipolárny charakter.
23. 4. 2013 Emília Halušková – Triedy algebier uzavreté na direktné limity
Abstrakt: Trieda všetkých retraktov konečnej algebry je uzavretá na direktné limity. Trieda algebier $\cal K$, ktorá je uzavretá na homomorfné obrazy a tiež na zjednotenia podalgebier z $\cal K$, je uzavretá na direktné limity. Ďalej som definovala triedu $\cal D$ pomocou logickej formuly prvého rádu, ktorá je uzavretá na direktné limity. Túto triedu $\cal D$ sme porovnávali s výsledkom, ktorý je uvedený v učebnici Keisler, Chang: Model Theory, London, 1990, ako cvičenie 5.2.24.
21. 5. 2013 Galina Jirásková – On the boundary of regular languages
Abstract: We prove that the tight bound on the state complexity of the boundary of regular languages, defined as $\operatorname{bd}(L)=L^* \cap \big( \, \overline{L} \, \big)^*$, is $3/8 \cdot 2^{2n} + 2^{n-2} - 2\cdot 3^{n-2} - n + 2$. Our witness languages are described over a five-letter alphabet. For a four-letter alphabet, the lower bound is smaller by just one, and we strongly conjecture that the the five-letter alphabet, used to define our witnesses, is optimal.
4. 6. 2013 Judita Lihová – Lexiko-grupy a radikálové triedy
Abstrakt: Lexiko-grupou nazývame $\ell$-grupu $A$, ktorá obsahuje vlastnú konvexnú $\ell$-podgrupu $A_0$ takú, že pre každý prvok $a\in A\setminus A_0$ platí buď $a\gt A_0$ alebo $a\lt A_0$. Konvexnú $\ell$-podgrupu $A$ $\ell$-grupy $G$, ktorá je lexiko-grupou, nazývame lexiko-podgrupou $\ell$-grupy $G$.
Nech $\mathcal{M}$ je ľubovoľný podsystém systému $\mathcal{G}$ všetkých $\ell$-grúp, uzavretý vzhľadom na izomorfizmy a konvexné $\ell$-podgrupy. Označme $\mathcal{R}_{\mathcal{M}}$ systém všetkých $\ell$-grúp $G$ spĺňajúcich podmienku: „ak $A$ je lexiko-podgrupa $\ell$-grupy $G$, ktorá je lexiko-rozšírením $A_0$, tak $A_0$ nepatrí do $\mathcal{M}$“.
Veta. Ak $\mathcal{M}$ je neprázdna, tak $\mathcal{R}_{\mathcal{M}}$ je radikálová trieda, ktorá nie je torznou triedou.
Systém všetkých radikálových tried typu $\mathcal{R}_{\mathcal{M}}$ s usporiadaním pomocou inklúzie označme $\mathbf{R}$.
Veta. $\mathbf{R}$ je úplný zväz s najmenším prvkom $\mathcal{R}_{\mathcal{G}}$, najväčším prvkom $\mathcal{R}_{\emptyset}$ a jediným duálnym atómom $\mathcal{R}_{\{\{0\}\}}$.
18. 6. 2013 Miroslav Ploščica – Zväzy kongruencií s vlastnosťou kompaktného prieniku
Abstrakt: Prednáška sa zaoberala popisom zväzov kongruencií algebier z danej konečne generovanej, kongruenčne distributívnej variety ${\mathcal V}$. Hlavná pozornosť bola venovaná varietám s vlastnosťou, že prienik kompaktných kongruencií je vždy kompaktný. V týchto prípadoch je možnosť použiť Priestleyovej dualitu a popísať zväzy kongruencií pomocou usporiadaných topologických priestorov. Taký popis sme ilustrovali na niekoľkých príkladoch.
26. 9. 2013 Miroslav Repický – Supremum a infimum dvojice kardinálnych čísel
Abstrakt: Prednáška sa zaoberala existenciou suprema a infima kardinálnych čísel v teórii množín bez axiómy výberu. Boli prezentované viaceré postačujúce podmienky. Ich dôsledkom je napríklad tvrdenie, že supremom je súčet v prípade, že jedno z kardinálných čísel je idemmultiple (t. j. spĺňa podmienku $2\cdot\mathfrak{m}=\mathfrak{m}$). V prípade dedekindovsky konečných kardinálnych čísel (t. j. spĺňajúcich podmienku $\mathfrak{m}<\mathfrak{m}+1$), supremum a infimum existuje len pre porovnateľné kardinálne čísla.
11. 10. 2013 Matúš Palmovský – On the state complexity of Kleene closure of regular languages
Abstract: We prove that the automaton presented by Maslov [Soviet Math. Doklady 11, 1373–1375 (1970)] meets the upper bound $3/4\cdot 2^n$ on the state complexity of Kleene closure. This fixes a small error in this paper that claimed the upper bound $3/4\cdot 2^n-1$. Our main result shows that the upper bounds $2^{n-1} + 2^{n-1}-k$ on the state complexity of Kleene closure of a language accepted by an $n$-state DFA with $k$ final states are tight for every $k$ in the binary case. We also present some results of our calculations. We consider not only the worst case, but we study all possible values that can be obtained as the state complexity of Kleene closure of a regular language accepted by a minimal $n$-state DFA. Using the lists of pairwise non-isomorphic binary automata of $2$, $3$, $4$, and $5$ states, we compute the frequencies of the resulting complexities for Kleene closure, and show that every value in the range from $1$ to $3/4\cdot 2^n$ occurs at least ones. In the case of $n = 6$, $7$, $8$, we change the strategy, and consider binary automata, in which the first symbol is a circular shift of the states, and the second symbol is generated randomly. We show that all values from $1$ to $3/4\cdot 2^n$ are attainable, that is, for every $m$ with $1 < m < 3/4\cdot 2^n$, there exists an $n$-state binary DFA $A$ such that the state complexity of $L(A)$ is exactly $m$.
24. 10. 2013 Peter Vojtáš (MFF UK, Praha) – O niektorých starších výsledkoch a otvorených problémoch
Abstrakt: Pripomenieme dve témy, na ktoré by možno stálo za to sa znova pozrieť.
Prvá súvisí s formalizmom tzv. Galoisových-Tukeyho konexií, popísaným v práci [P. Vojtáš, Generalized Galois-Tukey connections between explicit relations on classical objects of real analysis, Set theory of the reals, Proceedings of a winter institute on set theory of the reals held at Bar-Ilan University, Ramat-Gan (Israel), January 1991. Israel Mathematical Conference Proceedings 6 (1993), 619–643], kde bol využitý na dôkaz niektorých nerovností medzi kardinálnymi charakteristikami kontinua. Fenomén Galoisových-Tukeyho konexií sa však prirodzene vyskytuje aj v iných oblastiach matematiky a informatiky.
Druhá téma súvisí s odlíšením boolovej algebry generovanej usporiadaním divergentných radov porovnávacím kritériom od algebry $\mathcal{P}(\omega)/\mathit{fin}$. V práci [S. Fuchino, H. Mildenberger, S. Shelah, P. Vojtáš, On absolutely divergent series, Fundamenta Mathematicae 160 (1999), 255–268] bol nájdený model rozlišujúci distributivity oboch algebier. Publikovaný dôkaz sa odlišuje od pôvodného, jednoduchšieho dôkazu.
8. 11. 2013 Václav Skřivánek – States on IF-events
Abstract: Recently, B. Riečan in [B. Riečan, Analysis of fuzzy logic models. In: Intelligent Systems (ed. V. M. Koleshko), In Tech, Rijeka 2012, 219–244] has shown that it is possible to develop a reasonable probability on IF structures introduced by K. Atanassov in [K. Atanassov, Intuitionistic Fuzzy Sets: Theory and Applications. Studies in Fuzziness and Soft Computing. PhysicaVerlag, Heidelberg (1999)]. Starting with a structured system $F$ of IF-events, $F$ can be “lifted” to an MV-algebra $M$ and the corresponding probability theory on MV-algebras yields limit theorems for IF events. The construction is based on a representation theorem for states on IF-events and their “lifting” to states on MV-algebras. We give an alternative representation of $M$ via a bold algebra $B$ and prove a representation theorem for states on $B$. We describe the transition from $F$ to $M$ in terms of an enlargement of a cogenerator of probability domains [R. Frič, M. Papčo, On probability domains. Internat. J. Theoret. Phys. 49 (2010), 3092–3100], [R. Frič, M. Papčo, On probability domains II. Internat. J. Theoret. Phys. 50 (2011), 3778–3786].
29. 11. 2013 Peter Mlynárčik – On prefix-free languages
Abstract: We introduced concept of prefix-free languages with focus to class of regular languages. There was presented necessaary and sufficient condition for a structure of automata accepting a prefix-free language. We also presented some language operations as reversal, shuffle and showed state complexity of languages which are results of mentioned operations. We also mentioned maximal cardinality of finite prefix-free language, where length of strings is bounded by some constant.