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

<<  2013  >>

24. 1. 2013 – prof. Ing. Edita Pelantová, CSc. (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 – doc. RNDr. Ján Borsík, CSc. – 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 – RNDr. Peter Eliaš, PhD. – 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.

  1. Je pravda, že ak $\{n_k\}_{k\in\mathbb{N}}$ je rastúca postupnosť prirodzených čísel a $\{a_k\}_{k\in\mathbb{N}}$ je postupnosť prvkov $\mathbb{T}$ tak existuje postupnosť prirodzených čísel $\{m_j\}_{j\in\mathbb{N}}$ taká, že $\sum_{j\in\mathbb{N}}\|m_jx\|\le\sum_{k\in\mathbb{N}}\|n_kx+a_k\|$ pre všetky $x\in\mathbb{T}$?
  2. Je pravda, že ak $\{n_k\}_{k\in\mathbb{N}}$ je rastúca postupnosť prirodzených čísel, $\{a_k\}_{k\in\mathbb{N}}$ je postupnosť prvkov $\mathbb{T}$ a $c>0$, tak existuje postupnosť prirodzených čísel $\{m_j\}_{j\in\mathbb{N}}$ taká, že $\sum_{j\in\mathbb{N}}\|m_jx\|\le c$ pre všetky $x$ také, že $\sum_{k\in\mathbb{N}}\|n_kx+a_k\|\le c$?

Zatiaľ čo odpoveď na prvú otázku je negatívna, druhý problém ostáva otvorený.

12. 3. 2013 – doc. RNDr. Roman Frič, DrSc. – 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}$.

  1. $\mathbf{M}_p$ je $\sigma$-pole, $\mathbf{A}\subseteq\mathbf{M}_p$ a ak $B\subseteq X$ a $p^*(B)=0$, tak $B\in\mathbf{M}_p$.
  2. Definujeme $\overline{p}(B)=p^*(B)$, $B\in \mathbf{M}_p$. Potom $\overline{p}$ je pravde­podobnostná miera na $\mathbf{M}_p$ a je rozšírením $p$ z $\mathbf{A}$ na $\mathbf{M}_p$.
  3. $\mathbf{M}_p$ je najväčšie $\sigma$-pole podmnožín $X$, ktoré obsahuje $\mathbf{A}$ a na ktorom $p^*$ definuje pravde­podobnostnú mieru.
  4. Ak $B\subseteq X$, tak existuje $A\in \sigma(\mathbf{A})\subseteq \mathbf{M}_p$ taká, že $B\subseteq A$ a $p^*(B)=\overline{p}(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 – Mgr. 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

$\mathbf{u}\oplus\mathbf{v}= \displaystyle\frac{1}{1+\frac{\langle\mathbf{u},\mathbf{v}\rangle}{c^2}} \left[\mathbf{u}+\frac{1}{\gamma_\mathbf{u}}\mathbf{v}+ \frac{1}{c^2}\frac{\gamma_\mathbf{u}}{1+\gamma_\mathbf{u}} \langle\mathbf{u},\mathbf{v}\rangle\mathbf{u}\right]$, $\displaystyle\frac{1}{\gamma_\mathbf{u}}=\sqrt{1-\frac{\langle\mathbf{u},\mathbf{u}\rangle}{c^2}}$,

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 – doc. RNDr. Ján Haluška, CSc. – 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 – RNDr. Emília Halušková, CSc. – 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 – RNDr. Galina Jirásková, CSc. – 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 – doc. RNDr. Judita Lihová, CSc. – 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 – doc. RNDr. Miroslav Ploščica, CSc. – 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 – RNDr. Miroslav Repický, CSc. – 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 – Mgr. 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 – Prof. RNDr. Peter Vojtáš, DrSc. (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 – Mgr. 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 – Mgr. 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.