Seminarium zakładowe
Semestr letni 2021/22
Seminarium odbywa się w czwartki w godz. 10:30-12:00, w sali 1094. Tematyka seminarium: inżynieria oprogramowania, testowanie i jakość oprogramowania, teoria języków formalnych, matematyka dyskretna, metody formalne inżynierii oprogramowania, teoria grafów.
9 VI 2022
Prelegent: Artur Polański
Opis: Referat o konstrukcji cyklicznych kodów, które potem używane są do konstrukcji kodów, które mogą być stosowane w obliczeniach kwantowych. Na podstawie pracy Hai Q. Dinh, Tushar Bag, Ashish K. Upadhyay, Ramakrishna Bandi, Roengchai Tansuchat, "A class of skew cyclic codes and application in quantum codes construction" z Discrete Mathematics.
2 VI 2022
Prelegent: Jakub Zygadło
26 V 2022
Prelegent: Eryk Lipka
Tytuł: Uporządkowane automaty (nie)deterministyczne
Opis: Klasyczne automaty skończone są uogólniane na wiele sposobów. Na tym referacie zaprezentujemy automaty, których stany dają się w pewien naturalny sposób posortować. W klasie tych "Wheeler" automatów problemy takie jak determinizacja czy minimalizacja okazują się znacznie prostsze niż w zwykłych automatach, złożoności wielu algorytmów spadają z wykładniczej do wielomianowej. W ramach referatu pokażemy skąd bierze się ten naturalny porządek na stanach, omówimy dlaczego algorytmy się upraszczają oraz jak wygląda klasa języków rozpoznawanych przez takie
19 V 2022
Prelegent: Piotr Bienias
Tytuł: Simulating finite automata with context-free grammars
12 V 2022
Prelegent: Natalia Durlik
Tytuł: Lewis Carroll and the Red Hot Potato: A graph theoretic approach to a linear algebraic identity
Opis: The talk will be devoted to a graph theoretic interpretation of Dodgson’s rule - identity used in computing determinants. I will talk about equivalent identity involving sum of pairs of forests. I will present proof of the identity using edge transferring algorithm - Red Hot Potato. The talk is based on the paper “Lewis Carroll and the Red Hot Potato: A graph theoretic approach to a linear algebraic identity” by Melanie Fraser.
5 V 2022
Prelegent: Piotr Bienias
Tytuł: Simulating finite automata with context-free grammars
Opis: We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky Normal Form (CNF). We show that any unary DFA with n states can be simulated by a CNF grammar with O(n^(1/3)) variables, and this bound is tight. We show that any unary NFA with n states can be simulated by a CNF grammar with O(n^(2/3)) variables. Finally, for larger alphabets, we show that there exist languages that can be accepted by an n-state DFA, but which require \Omega(n/log n) variables in any equivalent CNF grammar.
21 IV 2022
Prelegent: Maciej Brzeski
Tytuł: Upper Bounding the Graph Edit Distance
Opis: I will introduce the edit distance problem on graphs and how to find an approximation solution using the linear assignment sum problem. I will present some techniques to obtain more accurate results, both with node representation and prediction using ML techniques. The presentation is based on a paper by David B. Blumenthal et al. "Upper Bounding the Graph Edit Distance Based on Rings and Machine Learning"
14 IV 2022
Prelegent: Mateusz Dobija
Tytuł: The Impact of Mislabeled Changes by SZZ on Just-in-Time Defect Prediction
Opis: During the seminar I will present the topic of JIT (just-in-time) defect prediction, described in the article titled “The impact of Mislabeled Changes by SZZ on Just-In-Time Defect Prediction” (authors: Yuanrui Fan, Xin Xia, Daniel Alencar da Costa, David Lo, Ahmed E. Hassan, Shanping Li). I will discuss the SZZ approach (implemented by Śliwerski, Zimmermann and Zeller) used in the aim of identifying changes that introduce a bug. I will present 4 basic steps: identifying bug-fixing changes, identifying buggy lines, identifying potential bug-introducing changes, and filtering away incorrect bug-introducing changes. During the presentation, I will show the impact of mislabeled changes related to variants of SZZ on the defect prediction. As a data for the analysis, the changes from selected Apache open-source projects have been used.
7 IV 2022
Prelegent: Adam Roman
Tytuł: Software Defect Prediction and Data-Flow Metrics
17 III 2022
Prelegent: Jakub Ruszil
Tytuł: The kangaroo problem
24 III 2022
Prelegent: Farnoud Ghasemi
Tytuł: Complex adaptive systems
The modeling of Complex Adaptive Systems (CAS) is an example for the integration of computer science into the very fabric of science. These models are used to understand and predict the dynamics of complex systems at both microscopic and macroscopic levels. In particular, we use the CAS theorems to study the dynamics of two-sided markets including platforms such as Uber, Airbnb and Amazon. On the other side, agent-based modeling (as a bottom-up study method) is used as a complementary tool to capture the interactions in the system. In an Agent-Based Model (ABM), the system is modeled as a collection of autonomous decision-making entities called agents and each agent interacts with the other agents in its own local environment. Collective behaviours of the agents give rise to emergent behaviours of the whole system which are not predictable through the individual behaviours of the agents at first sight. In this way, CAS models enable us to detect the relations and the interaction at a desired level and to study the feedback loops between the whole system and the individuals. Adaptation is another crucial feature of CAS models to reach the best models in terms of system dynamics considering the two main elements of decision making and learning. In particular, we use discrete choice models to obtain the desired behaviour. These models from economics are based on random utility theory and widely used to reproduce choice behaviour of the rational decision makers.
Semestr zimowy 2021/22
Seminarium odbywa się w czwartki w godz. 10:30-12:00, w sali 0086. Tematyka seminarium: inżynieria oprogramowania, testowanie i jakość oprogramowania, teoria języków formalnych, matematyka dyskretna, metody formalne inżynierii oprogramowania, teoria grafów.
27 I 2022
Prelegent: Maciej Brzeski
Tytuł: Aproksymowanie odległości edycyjnej grafów przy pomocy grafowych embeddingów
Na seminarium wprowadzę problem odległości edycyjnej na grafach, oraz przedstawię podejścia kombinatoryczne do rozwiązania tego problemu. W ostatnich latach widać jednak trend do użycia metod uczenia maszynowego do przybliżania odległości edycyjnej. Na podstawie pracy Runzhong Wang i in.: ,,Combinatorial Learning of Graph Edit Distance via Dynamic Embedding'' pokażę, jak można połączyć te dwa obszary.
20 I 2022
Prelegent: Mateusz Dobija
Tytuł: Predicting technical debt from commit contents: reproduction and extension with automated feature selection
Podczas seminarium przedstawię zagadnienie przewidywania długu technologicznego (ang. self-admitted technical debt) na podstawie zawartości commit’ów, omówione w pracy „Predicting technical debt from commit contents: reproduction and extension with automated feature selection” autorstwa Rantala & Mantyla. W ramach referatu omówię sposoby wykrywania commit’ów wprowadzających dług technologiczny, z uwzględnieniem trzech metod przetwarzania języka naturalnego: „Bag of words”, „topic modelling” i „word embedding vectors”. Zaprezentuję uzyskane rezultaty z odniesieniem do wyników wcześniejszych badań, a także przedstawię ograniczenia i dalsze kierunki analiz.
13 I 2022
Prelegent: Rafał Brożek
Tytuł: Metryki przepływu danych
Prezentacja wyników włąsnych w ramach pisanej pracy magisterskiej dotyczącej wykorzystania metryk przepływu danych do budowy modeli predykcji defektów.
16 XII 2021
Prelegent: Piotr Bienias
Temat: Deterministic Finite Automata minimization based on Backward Depth Information.
W referacie omówię problem minimalizacji automatu skończonego i przedstawię algorytm opisany w artykule:
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0165864
Metoda ta stosuje technikę Backward Depth Information, polegającą na znajdywaniu najkrótszych ścieżek do stanów akceptujących automatu z wszystkich pozostałych stanów. Algorytm cechuje wydajność zbliżona, a w pewnych przypadkach lepsza od najbardziej dotychczas efektywnego algorytmu Hopcrofta, oraz stosowalność dla dowolnej klasy automatów.
9 XII 2021
Prelegentka: Dzhesika Nimets
Temat: Hamiltonian Paths in Cayley Graphs (na podstawie pracy I. Paka)
2 XII 2021
Prelegentka: Natalia Durlik
Temat: Complexity problems in enumerative combinatorics
W swoim referacie przedstawię wybrane zagadnienia z przeglądowej pracy Igora Paka "Complexity problems in enumerative combinatorics". Omówię jakie kryteria można zastosować, by uznać wzór na dany ciąg elementów za przydatny. Rozważę złożoność obliczeniową bijekcji pomiędzy kombinatorycznymi strukturami oraz przedstawię interpretacje wybranych ciągów.
25 XI 2021
Prelegent: Marcin Podhajski
Temat: No-three-line problem on torus
18 XI 2021
Prelegent: Patryk Staniszewski
Temat: Publiczna, jednolita baza defektów
Podczas seminarium zostanie przedstawiony publiczny, ujednolicony bug dataset. Referat będzie opisywał proces wyboru pomniejszych zbiorów danych służących do stworzenia tytułowego ujednoliconego zbioru, ich analizę, metryki oraz przebieg unifikacji.
Zostaną przedstawione również możliwości wykorzystania otrzymanego zbioru do przewidywania błędów.
4 XI 2021
Prelegenci: Mikołaj Kondratek (kontynuacja), Tomasz Homoncik
Temat: Proporcja równoważnych mutantów
Testowanie mutacyjne opiera się na tworzeniu zmodyfikowanych wersji programu - mutantów. Część z nich może być jednak semantycznie równoważna z bazowym programem. Podczas referatu przedstawię metodę szacowania ilości mutantów równoważnych oraz jej zastosowania w testowaniu mutacyjnym.
Prezentacja
28 X 2021
Prelegenci: Jakub Ruszil (kontynuacja), Mikołaj Kondratek
Temat: Latin squares from multiplication tables
During the seminar, I will show that the partial multiplication table can be completed to the Latin square. The result will be more general as it is enough for the empty part of a partial Latin square to comply with some specific constraints. It will also turn out that this issue is related to Graham's Problem. I'll also explain what's special about 195.
21 X 2021
Prelegent: Jakub Ruszil
Temat: Synchronizacja automatów z punktu widzenia języków formalnych
Opis: W swoim referacie opiszę wyniki dotyczące teorii synchronizacji automatów z punktu widzenia języków formalnych. Na podstawie prac: Principal ideal languages and synchronizing automata autorstwa V. Guseva i in. oraz Reset Complexity of Ideal Languages autorstwa M. Maslennikovej.
Semestr letni 2020/21
Seminarium odbywa się w czwartki w godz. 10:30-12:00, w sali 1086 (w związku z epidemią - aktualnie na MS Teams, do zespołu można dołączyć przez kod: d70ru5i). Tematyka seminarium: testowanie i jakość oprogramowania, teoria języków formalnych, teoria grafów.
10 VI 2020
Prelegent: Maciej Brzeski
Temat: Wyszukiwanie podobnych podgrafów przy pomocy statystyki chi-kwadrat
Opis: Grafy etykietowane dostarczają naturalną drogę do reprezentowania różnych danych czy relacji. Mając zadany graf chcemy znaleźć najbardziej podobne w danym zbiorze grafów (lub najbardziej podobne podgrafy w wielkim grafie). Podejścia bazujące na izomorfizmie lub dopasowaniu grafów (tzw. graph matching) są NP-zupełne, co uniemożliwia stosowanie ich dla większych zbiorów danych. Jako alternatywę zaczęto rozważać algorytmy aproksymujące. W referacie przedstawię podejście, gdzie graf jest opisywany przez rozkład etykiet w sąsiednich wierzchołkach, a charakterystyka podobieństwa grafu jest oparta na istotności statystycznej uchwyconej przez statystykę chi-kwadrat. Referat na podstawie pracy Sourav Dutta i in., "Neighbor-Aware Search for Approximate Labeled Graph Matching using the Chi-Square Statistics".
Prezentacja
27 V 2021
Prelegent: Jakub Ruszil
Temat: Problem podziału na zbiory dominujące dla grafów skierowanych
Opis: W referacie pochylę się nad problemem podziału wierzchołków skierowanego grafu na zbiory dominujące. Udowodnię NP-zupełność tego problemu w ogólnym przypadku, a następnie przedstawię liniowy algorytm rozwiązujący ten problem w przypadku zorientowanych drzew. Referat na podstawie pracy Partitioning vertices into in- and out- dominating sets in digraphs - Kosuke Nakamura Toru Araki.
20 V 2021
Prelegent: Małgorzata Dymek
Temat: Acykliczne kolorowanie grafów i metoda kompresji entropii
Opis: Przedstawię zagadnienie acyklicznego kolorowania grafów oraz metodę kompresji entropii. Pokażę, jak może być użyta przy dowodzeniu ograniczoności acyklicznej liczby chromatycznej, poprzez przedstawienie dowodów dwóch takich ograniczeń dla pewnych rodzin grafów.
Prezentacja
13 V 2021
Prelegent: Tomasz Homoncik
Temat: Problem 4-ścieżkowego pokrycia wierzchołkowego
Opis: Podczas referatu przedstawię algorytm rozwiązujący problem 4-ścieżkowego pokrycia wierzchołkowego oraz omówię jego złożoność parametryczną.
6 V 2021
Prelegent: Mikołaj Kondratek
Temat: Grafy "wieżowe"
Opis: Podczas seminarium przedstawię pewne własności symplicjalnych grafów "wieżowych" (grafów nie-atakujących się wież na wielowymiarowej szachownicy).
W szczególności przyjrzę się zbiorom wierzchołków dominujących i niezależnych.
Rozważę również niektóre własności cyklicznych symplicjalnych grafów "wieżowych".
Prezentacja
29 IV 2021
Prelegent: Jakub Zygadło
Temat: Wprowadzenie do złożoności parametrycznej
Opis: W referacie omówię podstawy złożoności parametrycznej, która stanowi próbę dokładniejszej analizy problemów trudnych obliczeniowo - w szczególności w niektórych przypadkach metoda ta odpowiada na pytanie, kiedy problemy trudne mogą być uznane za możliwe do efektywnego rozwiązania i "z czego wynika" ich trudność. Złożoność algorytmu rozwiązującego dany problem jest tutaj podawana jako funkcja zależna nie tylko od rozmiaru danych wejściowych, ale także od wartości pewnego parametru. Przedstawię kilka klasycznych problemów uznawanych za trudne wraz z ich "naturalnymi" parametrami oraz przykłady najczęściej stosowanych technik (przeszukiwanie drzewa, kernelizacja).
22 IV 2021
Prelegent: Maciej Brzeski
Temat: Metody kernelowe na grafach
Opis: Wprowadzę w temat metod kernelowych na grafach na podstawie pracy S.V.N. Vishwanathan i in. - "Graph Kernels". Pokażę ich własności, zastosowanie oraz najpopularniejsze kernele. Następnie skupię się na kernelu: "random walk" - pokażę jak poprzez redukcję do równania Sylvestera policzyć go efektywnie, oraz jego związki z innymi kernelami.
Prezentacja
15 IV 2021
Prelegent: Jakub Ruszil
Temat: Metody algebry liniowej w synchronizacji automatów
Opis: Referat na podstawie pracy B. Steinberga "The Černý conjecture for one-cluster automata with prime length cycle". Omówię sposoby aplikacji metod algebry liniowej w teorii synchronizacji automatów. W pracy tej zawary jest dowód hipotezy Cerny'ego dla automatów jednoklastrowych z długością cyklu będącą liczba pierwszą.
8 IV 2021
Prelegent: Tomasz Homoncik
Temat: Algorytm online wyznaczający 3-ścieżkowe pokrycie wierzchołkowe grafu
Opis: Zaprezentuję algorytm online wyznaczający 3-ścieżkowe pokrycie wierzchołkowe.
Następnie pokażę, że współczynnik konkurencyjności tego algorytmu jest równy co najwyżej stopniowi zadanego grafu.
25 III 2021
Prelegent: Małgorzata Dymek
Temat: Wielomianowy algorytm wyznaczania morfizmu dla podanego punktu stałego
Opis: Słowo skończone jest punktem stałym pewnego morfizmu niebędącego identycznością, jeśli nie zmienia się pod wpływem jego działania (h(w) = w). Czy mając dane słowo możemy stwierdzić, że jest ono punktem stałym jakiegoś nietrywialnego morfizmu? Przedstawione zostaną pojęcia związane z punktami stałymi, ich konstrukcją i charakterystyką budowy, a także wielomianowy algorytm, który nie tylko odpowiada na powyższe pytanie, lecz również konstruuje odpowiedni morfizm.
Prezentacja
18 III 2021
Prelegent: Mikołaj Kondratek
Temat: Rikudo jest NP-zupełne
Rikudo to gra polegająca na znalezieniu ścieżki Hamiltona w grafie zbudowanym na komórkach hexagonalnej siatki. Przybliżę problem cyklów Hamiltona w grafach zbudowanych na krawędziach hexagonalnej siatki. Stosując odpowiednie redukcje pokażę, że gra jest NP-zupełna. Rozpatrzę również trudność łamigłówki dla zadanych już wartości o szczególnych postaciach.
Prezentacja
11 III 2021
Prelegent: Eryk Lipka
Temat: Złożoność Liego
W ramach referatu wprowadzimy pojęcie złożoności Liego dla nieskończonych słów nad skończonym alfabetem; jest to kolejny sposób opisywania ilości różnych skończonych czynników danego słowa. Pojęcie to posiada pewną interpretację algebraiczną, przez którą zostało nazwane tak a nie inaczej. Przy pomocy tego narzędzia udowodnimy kilka faktów o słowach, których złożoność (factor complexity) jest liniowa. Referat bazowany na niedawnej pracy Bell, Shallit "Lie complexity of words".
Semestr zimowy 2020/21
28 I 2021
Prelegent: Adam Roman
Temat: Data Flow Analysis
Omówię podstawowe zagadnienia związane z analizą przepływu danych, pokażę historyczny rozwój technik tej analizy związanej z wyznaczaniem osiągalności bądź żywotności zmiennych w kodzie oraz przedyskutuję kwestie zastosowania DFA do pomiaru i konstrukcji metryk przepływu danych; omówię w szczególności metrykę dep-degree i jej ciekawe własności.
21 I 2021
Prelegent: Sławomir Bakalarski
Temat: Dywizory na grafach - kontynuacja
14 I 2021
Prelegent: Mateusz Piątkowski
Temat: Krzywe eliptyczne w kryptografii - kontynuacja
Prelegent: Sławomir Bakalarski
Temat: Dywizory na grafach
Celem referatu jest zaznajomienie słuchaczy z teorią dywizorów na grafach. Referat będzie miał charakter czysto kombinatoryczny, żadna wcześniejsza wiedza z geometrii algebraicznej nie jest wymagana. Oprócz podstawowych pojęć omówimy m.in. twierdzenie Riemanna - Rocha dla grafów (udowodnione w 2007 przez Bakera i Norine'a), a także pokażemy jego wykorzystanie do rozwiązania problemu strategii wygrywającej w tzw. "chip - firing game". W drugiej części referatu omówimy obliczeniowe wyznaczanie grupy Picarda grafu (oraz jego jakobianu). W części trzeciej przejdziemy zaś do prezentacji twierdzenia Riemanna-Hurwitza w wersji grafowej (również udowodnionego przez wspomnianych wyżej autorów). Referat na podstawie wybranych pozycji z literatury, w szczególności prac Bakera i Norine'a.
Link do spotkania
7 I 2021
Prelegent: Mateusz Piątkowski
Temat: Krzywe eliptyczne w kryptografii
Na najbliższym spotkaniu zajmiemy się tematyką krzywych eliptycznych w kryptografii, a w szczególności zagadnieniu skręconych krzywych Edwardsa. Ponadto, będziemy porównywać wykorzystanie tradycyjnych krzywych Weierstrassa ze skręconymi krzywymi na przykładzie algorytmu faktoryzacji (Lenstry) w celu obserwacji optymalizacji czasu. Dla niewtajemniczonych - zrobimy odpowiednie wprowadzenie w meritum (ciała Galois + podstawy konstrukcji krzywych na ciałach Galois).
Link do spotkania
10 XII 2020
Prelegent: Tomasz Homoncik
Temat: Hunters and Rabbits
Opis: Przedstawię grę Hunters and Rabbits (wariant gry Cops and Robbers).
Omówię przypadek gry toczonej na hiperkostce oraz dla grafów z własnością zagnieźdżania izoperymetrycznego. Na koniec skupię się na wariancie gry, w którym królik nie jest zmuszony do ruchu pomiędzy strzałami.
Link do spotkania
3 XII 2020
Prelegent: Adam Ćwiertnia
Temat: Wykładnicze polepszenie wartości dolnych granic dla liczb Ramsey'a
Opis: Przedstawiona zostanie historia kolejnych poprawek dla wartości granic dolnych i górnych liczb Ramsey'a, między innymi probalistyczna metoda Erdős'a. Następnie pokazane zostanie wykładnicze polepszenie dla dotychczas znanych wartości dolnych z tych granic, przy trzy i więcej kolorowań grafów.
Link do spotkania
26 XI 2020
Prelegent: Eryk Lipka
Temat: Ograniczenie górne w problemie Grahama- Rothschilda
Opis: Na początku referatu wprowadzimy tematykę Teorii Ramseya oraz klasyczne problemy tej teorii. W drugiej części rozważymy zagadnienie znane jako problem Grahama-Rothschilda. Budujemy klikę, której wierzchołki są wierzchołkami kostki n-wymiarowej, a następnie dwukolorujemy jej krawędzie. Należy znaleźć najmniejsze takie n, że niezależnie od kolorowania w grafie tym można znaleźć cztery punkty leżące na jednej płaszczyźnie tworzące monochromatyczną klikę. Początkowe oszacowania na ten wymiar dają się w sposób zwarty opisać dopiero przy użyciu funkcji typu Ackermana, natomiast my zaprezentujemy najnowsze wyniki które dają ograniczenie przy użyciu zaledwie tetracji.
Link do spotkania |
Prezentacja
19 XI 2020
Prelegent: Edward Szczypka
Temat: Metody kompresji w matematyce dyskretnej i algorytmice (cz. II)
Opis: Przedstawiona zostanie idea wykorzystania mocno niedocenianej metody kompresji w różnych problemach z matematyki dyskretnej, języków formalnych czy algorytmiki. Jako jedno z rozwinięć, tej metody można traktować tzw. złożoność Kołmogorowa, dzięki której rozwiązano szereg problemów, atakowanych bez powodzenia od wielu lat.
Link do spotkania
12 XI 2020
Prelegent: Edward Szczypka
Temat: Metody kompresji w matematyce dyskretnej i algorytmice
Opis: Przedstawiona zostanie idea wykorzystania mocno niedocenianej metody kompresji w różnych problemach z matematyki dyskretnej, języków formalnych czy algorytmiki. Jako jedno z rozwinięć, tej metody można traktować tzw. złożoność Kołmogorowa, dzięki której rozwiązano szereg problemów, atakowanych bez powodzenia od wielu lat.
Link do spotkania
5 XI 2020
Prelegent: Maciej Brzeski
Temat: Odległość edycyjna dla drzew
Opis: O podobieństwie dwóch grafów można myśleć bardzo różnie - najczęściej rozważane jest podobieństwo oparte na strukturze bądź etykietach. Na seminarium wprowadzę problem "graph matching" na grafach etykietowanych, gdzie istotne jest wyznaczenie odpowiadających sobie wierzchołków. Omówię pracę wprowadzającą pojęcie odległości edycyjnej dla drzew oraz algorytm znajdujący minimalną odległość, a następnie jej związek z powyższym problemem. Na koniec krótko omówię trudności przy rozszerzeniu powyższego problemu na szerszą klasę grafów.
Link do spotkania |
Prezentacja
29 X 2020
Prelegent: Mikołaj Kondratek
Temat: Współczynniki w nieskończonym produkcie (1-x^(F_n))
Opis: Przedstawię dowód faktu, że współczynniki w nieskończonym produkcie (1-x^(F_n)) wynoszą zawsze -1, 0 albo 1 (gdzie F_n to n-ty wyraz ciągu Fibonacciego).
Celem wprowadzenia zaprezentuję zostanie liczbowy system Fibonacciego.
Dowód opiera się o 4-stanowy deterministyczny automat skończony.
Poruszę zagadnienie reprezentacji liniowej powiązanej z automatem.
Finalnie przedłożę automat obliczający współczynnik przy x^F_n.
Link do spotkania | Prezentacja
22 X 2020
Prelegent: Artur Polański
Temat: Wykrywanie pojedynczej wady w DFA
Opis: Omówienie znanego wyniku dotyczącego algorytmu heurestycznego wykrywania pojedynczej wady w deterministycznym automacie skończonym wraz z możliwościami ulepszenia go oraz występującymi problemami.
15 X 2020
Prelegent: Jakub Ruszil
Temat: Synchronizacja automatów o częściowej funkcji przejść
Opis: Automat nazywamy synchronizującym, gdy istnieje słowo, które każdy stan tego automatu przeprowadza w jeden ustalony stan. W referacie przedstawię wyniki dotyczące synchronizacji automatów o częściowej funkcji przejść, w szczególności opiszę konstrukcję nieskończonej rodziny automatów, dla której słowa synchronizujące mają długość wykładniczą w zależności od liczby stanów.
english
