{"id":2042,"date":"2025-10-02T09:18:43","date_gmt":"2025-10-02T07:18:43","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=2042"},"modified":"2025-12-30T16:40:42","modified_gmt":"2025-12-30T15:40:42","slug":"jezyki-automaty-i-obliczenia-ii-2025-advanced-topics-in-automata","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/2025-2026\/jezyki-automaty-i-obliczenia-ii-2025-advanced-topics-in-automata","title":{"rendered":"J\u0119zyki, automaty i obliczenia II 2025 \u2022 Advanced topics in automata"},"content":{"rendered":"<p>Wyk\u0142ad przestawia wybrane tematy o automatach. Wi\u0119kszo\u015b\u0107 wyk\u0142adu oparta jest na skrypcie <a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/paper\/automata-toolbox-book\">Automata Toobox<\/a>. W razie konsultacji zapraszam na konsultacje do mnie oraz do \u0141ukasza Orlikowskiego i Micha\u0142a Skrzypczaka. Wszyscy mieszkamy w budynku CENT. <a href=\"https:\/\/lclem.github.io\/JAiO2-2024.github.io\/\">Tutaj znajduj\u0105 si\u0119 zadania z \u0107wicze\u0144<\/a>.<\/p>\n<hr \/>\n<h3>Zasady zaliczenia<\/h3>\n<p>S\u0105 dwie oceny z przedzia\u0142u 2\u20135: ustny i zadania domowe. Ostateczna ocena to \u015brednia wa\u017cona: 2\/3 * ustny + 1\/3 * zadania.<\/p>\n<p>Poni\u017cej jest 11 temat\u00f3w z pytaniami egzaminacyjnymi. Na egzaminy ustny mo\u017cna sobie wybra\u0107 podzbi\u00f3r.<\/p>\n<ul>\n<li>na ocen\u0119 5 trzeba si\u0119 nauczy\u0107 9 temat\u00f3w<\/li>\n<li>na ocen\u0119 4 trzeba si\u0119 nauczy\u0107 6 temat\u00f3w<\/li>\n<li>na ocen\u0119 3 trzeba si\u0119 nauczy\u0107 4 temat\u00f3w<\/li>\n<\/ul>\n<p>Mo\u017cna sobie poprawi\u0107 ocen\u0119 z prac domowych, poprzez wskazywanie b\u0142\u0119d\u00f3w czy niejasno\u015bci w skrypcie, u\u017cywaj\u0105c linku poni\u017cej. Za ka\u017cd\u0105 poprawk\u0119 jest 1 pkt. (Prace domowe s\u0105 po 5kt, a zada\u0144 b\u0119dzie 10, wi\u0119c razem 50pkt).<\/p>\n<ul>\n<li><a href=\"https:\/\/kami.app\/sAi-gGX-rK9-Hs1\">wersja z 30 grudnia<\/a><\/li>\n<li><a href=\"https:\/\/kami.app\/54w-Adx-jtM-jZL\">wersja z 23 grudnia<\/a><\/li>\n<\/ul>\n<hr \/>\n<h3>Spis wyk\u0142ad\u00f3w i tematy egzaminacyjne (kompletne)<\/h3>\n<ol>\n<li><strong>Arytmetyka Presburgera<br \/>\n<\/strong>Pytania na egzamin: \u2022 udowodnij eliminacj\u0119 kwantyfikator\u00f3w w arytmetyce Presburgera \u2022 poka\u017c, \u017ce arytmetyka Presburgera definiuje dok\u0142adnie zbiory semiliniowe<\/li>\n<li><strong>Arytmetyka Tarskiego<br \/>\n<\/strong>Pytania na egzamin: udowodnij rozstrzygalno\u015b\u0107 teorii pierwszego rz\u0119du dla cia\u0142a liczb rzeczywistych<\/li>\n<li><strong>Systemy dodawania wektor\u00f3w<br \/>\n<\/strong>Pytania na egzamin: udowodnij nierozstrzygalno\u015b\u0107 problemu stopu dla maszyn dwulicznikowych \u2022 udowodnij rozstrzygalno\u015b\u0107 problemu &#8220;coverability&#8221; dla system\u00f3w dodawania wektor\u00f3w<\/li>\n<li><strong>Automaty wa\u017cone i liniowe<br \/>\n<\/strong>Pytania na egzamin: \u2022 poka\u017c, \u017ce automaty wa\u017cony i liniowe s\u0105 r\u00f3wnowa\u017cne \u2022 przedstaw algorytm r\u00f3wnowa\u017cno\u015bci dla tych automat\u00f3w<\/li>\n<li><strong>Automaty wielomianowe<br \/>\n<\/strong>Pytania na egzamin: \u2022 czym s\u0105 automaty wielomianowe \u2022 jak rozstrzyga si\u0119 ich r\u00f3wnowa\u017cno\u015b\u0107<\/li>\n<li><strong>Automaty rejestrowe i orbitowo sko\u0144czone<br \/>\n<\/strong>Pytania na egzamin: co to jest zbi\u00f3r orbitowo sko\u0144czony \u2022 jak si\u0119 rozstrzyga niepusto\u015b\u0107 dla automat\u00f3w orbitowo sko\u0144czonych<\/li>\n<li><strong>Monoidy i wyra\u017cenia bezgwiazdkowe<\/strong> Pytania na egzamin: monoidy i ich r\u00f3wnowa\u017cno\u015b\u0107 z automatami \u2022 wyra\u017cenia bezgwiazdkowe s\u0105 tym samym co monoidy aperiodyczne <\/li>\n<li><strong>Faktoryzacje Simona<\/strong> Pytania na egzamin:  udowodnij tw. Simona o drzewach faktoryzacji<\/li>\n<li><strong>Prawa zero-jedynkowe<br \/>\n<\/strong>Pytania na egzamin: udowodnij prawo zero-jedynkowe dla logiki pierwszego rz\u0119du \u2022 poka\u017c, \u017ce niesko\u0144czony graf losowy jest jeden<\/li>\n<li><strong>Parsowania gramatyk w czasie mno\u017cenia macierzy<\/strong><br \/>\nPytania na egzamin: przedstaw algorytm parsowania korzystaj\u0105cy z mno\u017cenia macierzy<\/li>\n<li><strong>Algorytm Angluin.<br \/>\n<\/strong>Pytania na egzamin: \u2022 przedstaw algorytm Angluin<\/li>\n<li><strong>Determinizacja \u03c9-automat\u00f3w<br \/>\n<\/strong>Pytania na egzamin: przedstaw podstawowe modele automat\u00f3w dla \u03c9-s\u0142\u00f3w, czyli deterministyczne\/niedeterministyczne automaty z warunkiem B\u00fcchiego oraz parzysto\u015bci \u2022 udowodnij determinizacj\u0119 (do warunku parzysto\u015bci)<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Wyk\u0142ad przestawia wybrane tematy o automatach. Wi\u0119kszo\u015b\u0107 wyk\u0142adu oparta jest na skrypcie Automata Toobox. W razie konsultacji zapraszam na konsultacje do mnie oraz do \u0141ukasza Orlikowskiego i Micha\u0142a Skrzypczaka. Wszyscy mieszkamy w budynku CENT. Tutaj znajduj\u0105 si\u0119 zadania z \u0107wicze\u0144. Zasady zaliczenia S\u0105 dwie oceny z przedzia\u0142u 2\u20135: ustny i zadania domowe. Ostateczna ocena to [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":2040,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-2042","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2042"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=2042"}],"version-history":[{"count":10,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2042\/revisions"}],"predecessor-version":[{"id":2076,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2042\/revisions\/2076"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2040"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=2042"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}