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


Referaty
dr Adam KolanyStudium kynologiczne - akcepteriery, obliczury i turingwajlery.Żywilla WcisłoAutomaty 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: 21.02.2011

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