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:

  1. Teoria automatów, lingwistyka matematyczna
  2. Pamięciowa złożoność obliczeniowa
  3. Teoria grafów: kolorowanie, pokrywanie, dominowanie, zbiory niezależne
  4. Algorytmy kombinatoryczne
  5. Kwantowa kryptografia
  6. Matematyczne podstawy współbieżności, Programowanie rozproszone i współbieżne
  7. Algorytmy ewolucyjne, Gene Expression Programming (GEP), zastosowania do rozwiązywania problemu klasyfikacji pochodzących z wielu klas
  8. Projektowanie, organizacja i pielęgnowanie bibliotek matematycznych
  9. 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 prof. Andrzej Szepietowski 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 prof. Andrzej Szepietowski 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.