Seminarium Zakładu Języków Formalnych
2010-11-14 00:00:00
Tematyka: Szeroko pojęta informatyka teoretyczna i matematyczne podstawy informatyki,
W szczególności:
- Teoria automatów, lingwistyka matematyczna
- Pamięciowa złożoność obliczeniowa
- Teoria grafów: kolorowanie, pokrywanie, dominowanie, zbiory niezależne
- Algorytmy kombinatoryczne
- Kwantowa kryptografia
- Matematyczne podstawy współbieżności, Programowanie rozproszone i współbieżne
- Algorytmy ewolucyjne, Gene Expression Programming (GEP), zastosowania do rozwiązywania problemu klasyfikacji pochodzących z wielu klas
- Projektowanie, organizacja i pielęgnowanie bibliotek matematycznych
- Modele sieci połączeń i ich odporność na uszkodzenia
Seminarium odbywa się w środy o godzinie 12:15 w sali 122.
Kontakt w sprawie otrzymywania informacji o kolejnych seminariach.
Referaty w roku akademickim 2016 / 2017
| Data | Prelegent | Temat / Streszczenie |
| 9.11.2016 | prof. Andrzej Szepietowski, dr Janusz Dybizbański |
O grach kombinatorycznych |
Referaty w roku akademickim 2015 / 2016
| Data | Prelegent | Temat / Streszczenie |
| 4.05.2016 | prof. Andrzej Szepietowski | 1. O pracy Lee, Tan i Hsu o pokryciu hiperkostki dwoma sciezkami. 2. Rozłączny zbiór krawędzi nazywamy skojarzeniem. Otwarty problem: Czy przez każde skojarzenie można poprowadzić cykl Hamiltona? |
| 20.04.2016 | Grzegorz Madejski | O gramatykach ze skokami (jumping grammars) |
| 16.03.2016 | Maciej Dziemiańczuk | O zliczaniu ścieżek kratowych i plane trees |
| 9.03.2016 | prof. Andrzej Szepietowski, dr Janusz Dybizbański | O cyklach Hamiltona w hiperkostkach z uszkodzonymi krawędziami |
| 27.01.2016 | Monika Rosicka | O dominowaniu wypukłym w grafach pryzmowych |
| 13.01.2016 | prof. Andrzej Szepietowski | O ścieżkach Hamiltona w hiperkostkach z uszkodzonymi krawędziami |
| 25.11.2015 | dr Andrzej Borzyszkowski | O pracy M. Codish, M. Frank, A. Itzhakov, A. Miller Computing the Ramsey Number R(4,3,3) using Abstraction and Symmetry breaking |
| 18.11.2015 | Maciej Dziemiańczuk | Kilka sztuczek przy zliczaniu ścieżek kratowych |
| 21.10.2015 | prof. Joanna Jędrzejowicz | O pracy Fernau, Paramasivan, and Schmid Jumping Finite Automata: Characterizations and Complexity |
| 14.10.2015 | Karolina Rybarczyk | Automatyczna obsługa lip-sync w modelowaniu 3D |
| 7.10.2015 | prof. Andrzej Szepietowski | O cyklach Hamiltona w hiperkostkach |
Referaty w roku akademickim 2014 / 2015
| Data | Prelegent | Temat / Streszczenie |
| 3.VI.2015 | Anna Nenca | O hiperkostkach z uszkodzeniami |
| 20.V.2015 | Grzegorz Madejski | O złożoności czasowej problemu słowa dla języków z permutacjami |
| 21.IV.2015 | dr Karol Horodecki | Ograniczenia na kwantowe powtarzacze klucza. Kiedy kwantowe bezpieczeństwo jest "przechodnie"? Opowiem o pracy Stefan Bäuml, Matthias Christandl, Karol Horodecki, Andreas Winter Limitations on Quantum Key Repeaters |
| 14.IV.2015 | Monika Rosicka | O grafach uniwersalnie ustalonych |
| 4.III.2015 | Monika Rosicka | O grafach uniwersalnie ustalonych |
| 7.I.2015 | prof. Andrzej Szepietowski | O symetriach w hiperkostkach |
| 3.XII.2014 | Anna Nenca | O cyklach Hamiltona w hiperkostkach z uszkodzeniami |
| 5.XI.2014 | prof. Andrzej Szepietowski | O artykułach M. Rejewskiego o rozszyfrowaniu Enigmy |
| 29.X.2014 | prof. Andrzej Szepietowski | O automatach dwukieunkowych |
| 22.X.2014 | Maciej Dziemiańczuk | O zliczaniu pewnych ścieżek kratowych |
| 15.X.2014 | Maciej Dziemiańczuk | O zliczaniu pewnych ścieżek kratowych |
| 8.X.2014 | Relacje z konferencji |
Referaty w roku akademickim 2013 / 2014
| Data | Prelegent | Temat / Streszczenie |
| 11.VI.2014 | prof. Andrzej Szepietowski | Oszacowanie średniego czasu działania Quick-Sorta |
| 4.VI.2014 | dr Janusz Dybizbański | O skierowanych kolorowaniu grafów |
| 21.V.2014 | dr Magdalena Godlewska (PG) | Model otwartej architektury rozproszonych dokumentów elektronicznych wspierającej proces podejmowania decyzji w trybie obliczeń zespołowych |
| 14.V.2014 | dr Andrzej Borzyszkowski | O pracy The genus of regular languages, Guillaume Bonfante, Florian Deloup. |
| 26.III.2014 | Grzegorz Madejski | O pewnych językach formalnych. |
| 19.III.2014 | Janusz Dybizbański | O pewnych liczbach Ramseya. |
| 8.I.2014 | Paweł Konefal | O rozpoznawaniu gestów przy pomocy czujników przyśpieszenia |
| 18.XII.2013 | prof. Joanna Jędrzejowicz | O przekrojach języków semiliniowych |
| 20.XI.2013 | prof. Bengt J. Nilsson (Malmo University) | Using Maximum Coverage to Optimize Recommendation Systems in E-Commerce |
| 6.XI.2013 | Monika Rosicka | O dominowaniu w grafach permutacyjnych G nad H |
| 23.X.2013 | dr Andrzej Borzyszkowski | O wskazywaniu większościowego koloru |
Referaty w roku akademickim 2012 / 2013
| Data | Prelegent | Temat / Streszczenie |
| 17.VII.2013 | prof. Andrzej Szepietowski i Janusz Dybizbański |
O skierowanym kolorowaniu |
| 12.VI.2013 | prof. Andrzej Szepietowski i Janusz Dybizbański |
O skierowanym kolorowaniu cykli i kół |
| 29.V.2013 | prof. Joanna Jędrzejowicz | O językach z przeplotem |
| 22.V.2013 | prof. Andrzej Szepietowski | O problemie wyliczanie perfekcyjnego przeplotu |
| 8.V.2013 | Grzegorz Madejski | O pewnej pracy prof. J. Grytczuka |
| 23.I.2013 | Maciej Dziemiańczuk | O bijekcji pomiędzy rodzinami ścieżek Motzkina i Delannoya |
| 16.I.2013 | dr Andrzej Borzyszkowski | Ciąg dalszy: O kombinatorycznym problemie określania większościowego koloru w zbiorze kul |
| 9.I.2013 | dr Andrzej Borzyszkowski | O kombinatorycznym problemie określania większościowego koloru w zbiorze kul |
| 28.XI.2012 | Grzegorz Madejski | O pracy "Partially commutative context-free languages" Czerwińskiego i Lasoty |
| 7.XI.2012 | O automatach ze stosem ograniczonej wysokości, koszt determinizacji | |
| 24.X.2012 | Monika Rosicka | Dominowanie w grafach pryzmowych. Grafy uniwersalnie ustalone |
| 17.X.2012 | Paweł Kamiński | Wybrane zagadnienia kryptografii |
| 10.X.2012 | Doktoranci | Relacja z 4PCC 2012 |
Referaty w roku akademickim 2011 / 2012
| Data | Prelegent | Temat / Streszczenie |
| 16.V.2012 | O deterministycznym algorytmie z pamięcią logarytmiczna dla problemu osiągalności w grafach nieskierowanych | |
| 25.IV.2012 | Doktoranci | Relacja z FIT 2012 |
| 18.IV.2012 | prof. Jerzy Topp |
O szczególnych zbiorach dominujących w grafach |
| 7.III.2012 | Janusz Dybizbański |
O najdłuższych skończonych ciągach niezawierajacych 3-elementowego ciągu arytmetycznego |
| 29.II.2012 | Grzegorz Madejski |
Nieskończona hierarchia języków z permutacjami |
| 22.II.2012 | Maciej Dziemiańczuk |
O liczbach Delannoya |
| 16.XI.2011 | Grzegorz Madejski | O językach z permutacjami i językach z przeplotem |
| 9.XI.2011 | Janusz Dybizbański | O liczbach Ramseya |
| 26.X.2011 | Anna Nenca | O skierowanym kolorowaniu gridów |
| 19.X.2011 | Maciej Dziemiańczuk | O poszukiwaniu pewnego zbioru częściowo uporządkowanego związanego z liczbami Fibonomialnymi |
| 12.X.2011 | prof. Andrzej Szepietowski | O hyperminimalnych automayach |
| 5.X.2011 | Anna Nenca i Janusz Dybizbański | O tegorocznych konferencjach MFCS i CID |
Referaty w roku akademickim 2010 / 2011
| Data | Prelegent | Temat / Streszczenie |
| 31.V.2011 | prof. Jarosław Grytczuk (UJ) | Stopniowe kolorowanie grafów |
| Seminarium odbędzie się wyjątkowo we wtorek o godzinie 18:00 w sali 122. | ||
| 27.IV.2011 | prof. Jerzy Topp | O liczbach ratunkowych w drzewach |
| 16.II.2011 | Maciej Dziemiańczuk | Three ways to generalize binomial coefficients |
| Zostaną pokazane trzy metody, które pozwalają uogólnić współczynniki dwumienne do szerokiej rodziny liczb kombinatorycznych, zawierającej m.in. liczby Stirlinga, Eulera, Gaussowskie i inne. Pierwsza z metod wykorzystuje wzór jawny i pokazuje związek z problemem pakowania wielowymiarowych pudełek. Druga korzysta z uogólnionej rekurencji dla współczynników dwumiennych oraz zagadnienia zliczania ścieżek w kratach. Ostatnia wychodzi od funkcji tworzącej oraz zliczania wyborów elementów z pudełek. | ||
| 26.I.2011 | prof. Joanna Jędrzejowicz | O pracy M. Berglund, H. Bjorklund, J. Hogberg: Recognizing Shuffled Languages |
| 19.I.2011 | prof. Jerzy Topp | O liczbach związanych z dominowaniem w grafach |
| 12.I.2011 | Janusz Dybizbański | O liczbach Ramseya |
| 5.I.2011 | dr Marcin Kuropatwiński (VOICE LAB) | Probabilistyczne podstawy systemów rozpoznawania mowy |
| Na seminarium przedstawione zostaną następujące zagadnienia. Po wstępie zawierającym uwagi historyczne przedstawione będą podstawowe definicje teorii prawdopodobieństwa. Następnie omówione zostaną elementy współczesnych probabilistycznych systemów rozpoznawania mowy, w tym niejawne łańcuchy Markowa, algorytm Viterbiego, trening Viterbiego i algorytm Baum-Welch’a. Omówione zostanie również modelowanie sygnału mowy jako system dynamiczny (proces). Kolejno przedstawione zostaną pojęcia statystycznej teorii uczenia (gromadzenia wiedzy z obserwacji) i jej koneksje z podstawowym problemem sztucznej inteligencji jakim jest rozpoznawanie wzorców. Kolejna cześć poświęcona będzie elementom teorii informacji tzn. kwantyzacji wektorowej, generowanym przez kwantyzator wektorowy podziale przestrzeni znanym jako diagram Voronoi i zastosowaniu diagramu Voronoi do estymacji prawdpodobieństw. Na koniec przedstawione zostaną założenia leżące u podstaw tworzonego w VOICE LAB systemu rozpoznawania mowy ciągłej z dużym słownikiem. | ||
| 22.XI.2010 | prof. Andrzej Szepietowski | Ciąg dalszy O automatach hyper-minimized |
| 15.XII.2010 | dr Andrzej Borzyszkowski | Ciąg dalszy Podpis cyfrowy - szczegóły niektórych wariantów podpisu cyfrowego |
| 8.XII.2010 | dr Andrzej Borzyszkowski | Podpis cyfrowy: o pewnym szczególnym rodzaju podpisu grupowego |
| 1.XII.2010 | Grzegorz Madejski | O pewnych klasach języków z przeplotem |
| Streszczenie: Po krótkim wstępie do algebraicznej teorii języków przeanalizujemy klasy języków z przeplotem przedstawione w artykule "The expressive power of the shuffle product" J.Berstel, L. Boasson, O. Carton, J.-E. Pin, A. Restivo. Są to klasy zawierające singletony, domknięte ze względu na operacje boolowskie, przeplot przez różnie zdefiniowane języki, oraz ewentualnie - konkatenację. | ||
| 24.XI.2010 | prof. Andrzej Szepietowski | O pracy Badr, Geffert and Shipman, Hyper-minimizing minimized deterministic finite state automata |
| 20.X.2010 | Maciej Dziemiańczuk | Problem podziału wielowymiarowych pudełek |
| Streszczenie: Problem istnienia podziału d-wymiarowego pudełka o wymiarach A1 × A2 × ... × Ad przy pomocy bloków o wymiarach a1 × a2 × ... × ad dla pewnej rodziny ciągów wyznaczających wymiary pudełek i bloków. W drugiej części pokazany będzie związek problemu z interpretacją kombinatoryczną pewnej rodziny uogólnionych współczynników dwumiennych, które zawierają m.in. współczynniki Gaussowskie oraz Fibonomialne. | ||
| 6.X.2010 | Janusz Dybizbański | Wartość liczb Ramsey'a R (K2,2, K2,14) i R (K2,2, K2,15) |
| Streszczenie: W trakcie referatu przybliżona zostanie tematyka liczb Ramsey'a w klasycznej wersji oraz dla pełnych grafów dwudzielnych. W celu wyznaczenia liczby R(K_{2,2}, K_{2,14}) udowodnię lemat pozwalający ograniczyć przestrzeń przeszukiwań kolorowań kliki K_{22} do sprawdzenia sześciu możliwości kolorowań krawędzi incydentnych z sześcioma wierzchołkami. Przedstawię algorytm pozwalający na sprawdzenie czy istnieje kolorowanie kliki K_p nie zawierające ani K_{2,2} w kolorze 1 ani K_{2,n} w kolorze 0. Algorytm został uruchomiony dla każdej z tych możliwości i stwierdził, że nie istnieje takie kolorowanie dla n=14 i kliki K_{22}. Dla n=15 algorytm wyznaczył kolorowania kliki K_{23}. Oba te fakty wraz z dotychczas znanymi ograniczeniami pozwoliło na wyznaczenie dokładnej wartości dla obu liczb. | ||
