{"id":2016,"date":"2025-02-18T11:43:05","date_gmt":"2025-02-18T10:43:05","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=2016"},"modified":"2025-07-12T13:46:35","modified_gmt":"2025-07-12T11:46:35","slug":"alfabety-nieskonczone-infinite-alphabets","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/2024-2025\/alfabety-nieskonczone-infinite-alphabets","title":{"rendered":"Alfabety niesko\u0144czone \u2022 Infinite alphabets"},"content":{"rendered":"<p>The lecture is about computational models, such as automata, which are based on a more relaxed notion of finite set. The lecture notes are in the moodle page.<\/p>\n<h3>Grading<\/h3>\n<p>Your grade will be a weighted average: 1\/3 homework + 2\/3 final exam.<\/p>\n<ul>\n<li><strong>Homework. <\/strong>There are 11 homework problems, giving you up to 110 points. You get a grade according to the following table:\n<ul>\n<li>5: \u2265 100 points<\/li>\n<li>4+: \u2265 90 points<\/li>\n<li>4: \u2265 80 points<\/li>\n<li>3+: \u2265 60 points<\/li>\n<li>3: \u2265 50 points<\/li>\n<\/ul>\n<p>You can supplement your homework score, and thus also your grade, by reporting mistakes in the lecture notes. Here you will find a recent version of the lecture notes, which you can freely annotate with mistakes that you find (first come, first serve, and please use the latest version):<\/p>\n<ul>\n<li><a href=\"https:\/\/kami.app\/tqG-tGr-n8u-Zdp\">June 11<\/a><\/li>\n<li><a href=\"https:\/\/kami.app\/xmq-Eci-q2r-vLT\">June 13<\/a><\/li>\n<li><a href=\"https:\/\/kami.app\/VHf-CLy-TY4-3Zg\">June 21<\/a><\/li>\n<li><a href=\"https:\/\/kami.app\/aDn-1U6-GUj-FiN\">June 26<\/a><\/li>\n<li><a href=\"https:\/\/kami.app\/LT2-K5n-vMf-UYE\">July 3<\/a><\/li>\n<li><a href=\"https:\/\/kami.app\/BWi-iB3-CfS-6Eb\">July 12<\/a><\/li>\n<\/ul>\n<p>You get 1 homework point for each mistake and 2 points for each mistake in your designated chapter. (The list of designated chapter was sent by email.) That means that finding 5 mistakes in your designated chapter is the same as doing one homework problem.<\/li>\n<li><strong>Oral exam. <\/strong>Below you will find a closed list of topics for the oral exam. You choose n topics from the list, and I start asking questions about your chosen topics. Assuming that you give good answers, you get a grade based on the number of chosen topics, according to the following table:\n<ul>\n<li>5: \u2265 12 topics<\/li>\n<li>4+: \u2265 10 topics<\/li>\n<li>4: \u2265 9 topics<\/li>\n<li>3+: \u2265 7 topics<\/li>\n<li>3: \u2265 6 topics<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Topics for the oral exam<\/h3>\n<p>Here is the closed topics, with references to the lecture notes:<\/p>\n<ol>\n<li>Polynomial orbit-finite sets, and the equivalence of two representations from (Lemma 1.6).<\/li>\n<li>Prove decidability of reachability in pof graphs \u00a0(Theorem 1.9)<\/li>\n<li>Show that nondeterministic pof automata do not determinise, and are not closed under complementation (Theorem 2.4)<\/li>\n<li>Show that universality is undecidable for pof automata (Theorem 2.5).<\/li>\n<li>For the equality atoms, \u00a0show that orbit-finite sets are the same as quotiented pof sets (Theorem 4.6).<\/li>\n<li>The least support theorem, and the accompanying representation (Theorem 4.13).<\/li>\n<li>Definition of oligomorphic structures, and Theorem 5.7 about first-order definability.<\/li>\n<li>Definition of homogeneous structures, and the Fraisse Theorem (Theorem 6.6)<\/li>\n<li>Two examples of homogeneous structures: the random graph and bit vectors.<\/li>\n<li>Prove the Finite Length Theorem (Theorem 8.5).<\/li>\n<li>Define orbit-finite Turing machines, and show that the nondeterministic ones are expressively complete, under suitable assumptions (Theorem 9.2)<\/li>\n<li>Prove that P \u2260 NP for the bit vector atoms (Theorem 9.9)<\/li>\n<li>Prove that Turing machines cannot be determinised for the equality atoms (Theorem 9.13)<\/li>\n<li>Define representable sets, and show that equality is decidable for them (Theorem 10.11)<\/li>\n<li>Define while programs with atoms, and show implication 1 =&gt; 2 in Theorem 11.2.<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The lecture is about computational models, such as automata, which are based on a more relaxed notion of finite set. The lecture notes are in the moodle page. Grading Your grade will be a weighted average: 1\/3 homework + 2\/3 final exam. Homework. There are 11 homework problems, giving you up to 110 points. You [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1991,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-2016","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2016"}],"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=2016"}],"version-history":[{"count":13,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2016\/revisions"}],"predecessor-version":[{"id":2037,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2016\/revisions\/2037"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1991"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=2016"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}