Koło Naukowe Matematyków UŚ ENG KNM
O NAS DLA LICEALISTOW FORUM

IV sesja KNM
Automaty, gramatyki i języki formalne.

Zarzecze, 12 - 15 listopada 1998

Program Sesji

12 XI 98

14:55 Wyjazd z Katowic. 
18:00 Przybycie do Zarzecza. Zakwaterowanie. 
19:00 Rozpoczęcie sesji wykładem dr Adama Kolany. 
20:00 Kolacja. 
20:30 Dyskusja: 
        Czy ludziom trzeba pomagać? 
        Czy w Polsce są ludzie naprawdę biedni?
        Naprawdę - to znaczy nie "z wyboru" - przez zaniedbanie i brak  odpowiedzialności. 
        Czy ludzie biedni są od nas gorsi? Jeśli nie, to po co walczyć z ubóstwem?

13 XI 98

9:00  Śniadanie. 
10:00 Rozpoczęcie sesji przedobiedniej - referaty. 
14:00 Wyjście na obiad. 
16:00 Sesja popołudniowa - referaty. 
20:00 Kolacja. 
20:30 Dyskusja 1: 
        Amnesty International - kto dał im prawo określania ludzkich praw?
        Dyskusja 2:
        Reforma szkolnictwa Pana Ministra Handke a rzeczywiste potrzeby zmian w systemie edukacji.
21:30 Zawody w warcaby, szachy i inne gry świetlicowe.

14 XI 98

9:00  Śniadanie. 
10:00 Rozpoczęcie sesji przedobiedniej - referaty. 
14:00 Wyjście na obiad. 
16:00 Zawody w badmintona i inne zabawy ruchowe. 
19:00 Dyskusja: 
Analiza semantyczno-logiczna treści ustawy o samorządach studenckich. 20:30 Barbeque. 

15 XI 98

9:00  Śniadanie. 
10:00 Zwiedzanie okolicy. 
12:00 Podsumowanie sesji. Wykład dr Marka Szyjewskiego
13:00 Pakowanie i sprzątanie. Obiad. 
16:00 Wyjazd do Katowic.

Uczestnicy
Łukasz Bujak
Radosław Czaja
Włodek Fechner
Agnieszka Furmankiewicz
Paweł Gładki
Renata Gołkowska
Adam Kolany
Michał Kolany
Mariusz Klęczar
Angelika Kurzyniec
Tatiana Korzeniowska
Izabela Papuga
Joanna Pawłowska
Bibianna Sonelska
Ola Stanek
Michał Trzęsiok
Żywilla Wcisło
Radosław Wieczorek
Marek Szyjewski


Referaty
dr Adam KolanyStudium kynologiczne - akcepteriery, obliczury i turingwajlery.
Żywilla Wcisło Automaty skończenie stanowe, ASS. Przykłady: tabliczka dodawania i mnożenia; automat rozstrzygajšcy równość, mniejszość, itp.
Włodzimierz Fechner Deterministyczne i niedeterministyczne ASS. ASS z epsilon-ruchami. Dwukierunkowe ASS. Równoważność poszczególnych klas automatów.
Włodzimierz Fechner Automaty Moore'a i Mealy'ego. Przykłady: konwertery między podstawami numeracji, i in.
Aleksandra Stanek Język akceptowany przez ASS. Języki regularne, JR. Równoważność JR i języków ASS-akceptowalnych. Przykłady odpowiednich konstrukcji.
Bibianna Sonelska Lemat o pompowaniu dla JR. Przykład zastosowania: nieprogramowalność sumatorów i multiplikatorów.
Bibianna Sonelska Własności JR. Własności domknięciowe. Algorytmy decyzyjne dla JR. Twierdzenie o minimalizacji ASS. (BS)
Łukasz BujakGramatyki bezkontekstowe, GBK. Przykłady. Eliminacja epsilon-produkcji, eliminacja symboli "bezużytecznych".
Michał Trzęsiok Chomskiego i Greibacha twierdzenia o postaci normalnej. Zastosowania.
Tatiana KorzeniowskaAutomaty ze stosem, AZS. Deterministyczne, DAZS, automaty ze stosem. Akceptacja przy pustym stosie, a akceptacja przy stanie końcowym.
Tatiana KorzeniowskaRównoważność NAZS i JBK. Przykłady konstrukcji.
Paweł GładkiLemat o pompowaniu dla JBK i lemat Ogdena. Zastosowania. Własności domkniętości JBK. Algorytmy decyzyjne dla JBK.
Radosław CzajaMaszyny Turinga, MT: (jedno-) dwustronnie nieograniczone; wielościeżkowe; wielotaśmowe; wsadowe; niedeterministyczne. Równoważność tychże.
Radosław CzajaMaszyny licznikowe ML; maszyny o dostępie bezpośrednim, RAM; maszyny wielostosowe, MWS. Równoważność z MT.
Joanna PawłowskaFunkcje i relacje obliczalne, FObl, RObl. Przykłady. Teza Churcha. Przykłady problemów nieobliczalnych.
Joanna PawłowskaUniwersalna maszyna Turinga, UMT.
mgr Joanna Napiórkowska Twierdzenia Rice'a. Twierdzenie Greibacha. Zastosowania.
mgr Joanna Napiórkowska Maszyny z wyroczniš. Hierarchia problemóww nierozstrzygalnych
Renata GołkowskaHierarchia Chomskiego. Chomskiego twierdzenie o hierarchi.
Joanna PawłowskaZłożoność obliczeniowa. Problem PNP. NP-zupełność i NP-trudność problemów. Przykłady.

ostatnia aktualizacja: 04.07.2012

Kontakt:

Koło Naukowe Matematyków Uniwersytetu Śląskiego
40-007 Katowice, ul. Bankowa 14 (pokój 524)
tel. (032) 359-20-96, e-mail: knm@knm.katowice.pl