Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- magistraleinformatica:mod:start:pretest [20/07/2015 alle 16:44 (10 anni fa)] – Roberto Bruni
+++ magistraleinformatica:mod:start:pretest [01/03/2016 alle 23:11 (9 anni fa)] (versione attuale) – Roberto Bruni
@@ Linea 1: / Linea 1: @@
 ==== Preliminary test for the course on Models of Computation ====
-There are no prerequisistes for MOD, but we expect the students to have some familiarity with discrete mathematics, first-order logic formulas, context-free grammars, and code fragments in imperative and functional style.
+There are no prerequisites for MOD, but we expect the students to have some familiarity with discrete mathematics, first-order logic formulas, context-free grammars, and code fragments in imperative and functional style.
-We encourage the students to use the following exercises to self-assess their level of knowledge for the above arguments.
+We encourage the students to use the following basic exercises to self-assess their level of knowledge for the above arguments.
 === Exercise 1 ===
@@ Linea 11: / Linea 11: @@
 === Exercise 2 ===
-Are the formulas "(forall x. P(x)) implies Q" and "forall x. (P(x) implies Q)" equivalent?
+Are the formulas "(∀x. P(x)) ⇒ Q" and "∀x. (P(x) ⇒ Q)" equivalent?
 === Exercise 3 ===
-Prove that for any natural number n we have that n*n + n is even.
+Let 7<sup>n</sup> denote the nth power of 7. Prove by induction that for any natural number n > 1 we have that 3 divides 7<sup>n</sup> - 1.
 === Exercise 4 ===
-Consider the strings (i.e., finite sequences) of symbols {0,1}. Let #0(s) and #1(s) denote the number of occurrences of 0 and 1 in the string s, respectively, and let s^n denote the sequence obtained as the concatenation of n instances of the string s.  Define context-free grammars that generate each of the following languages
+Consider the strings (i.e., finite sequences) of symbols {0,1}. Let #<sub>0</sub>(s) and #<sub>1</sub>(s) denote the number of occurrences of 0 and 1 in the string s, respectively, and let s<sup>n</sup> denote the sequence obtained as the concatenation of n instances of the string s.  Define context-free grammars that generate each of the following languages
-  - the set of all and only strings s such that #1(s) is odd.
+  - The set of all and only strings s such that #<sub>1</sub>(s) is odd.
-  - the set of all and only strings s such that #0(s) = #1(s).
+  - The set of all and only strings s such that #<sub>0</sub>(s) = #<sub>1</sub>(s).
-  - the set of all and only strings s such that s = (01)^n for some natural number n.
+  - The set of all and only strings s such that s = (01)<sup>n</sup> for some natural number n.
-  - the set of all and only strings s such that s = 0^n 1^n for some natural number n.
+  - The set of all and only strings s such that s = 0<sup>n</sup> 1<sup>n</sup> for some natural number n.
 === Exercise 5 ===
-Let us consider the program
+Let us consider the imperative code fragment
-while (x!=0 and y!=0) do { x:=x-1 ; y:=y-1 }
+<code>while (x!=0 and y!=0) do {
+    x := x-y;
+    y := y-1
+}</code>
+where x and y are two integer variables.
 For which initial values of x and y does the execution of the above program terminate?