# HG changeset patch # User Christian Urban # Date 1497865468 -3600 # Node ID 5c9de27a5b30cc1accfb70077c431b6f164709c5 # Parent 7d9d86dc7aa01fe153b5ef2140bba8e5db1e0b85 updated diff -r 7d9d86dc7aa0 -r 5c9de27a5b30 handouts/ho01.tex --- a/handouts/ho01.tex Wed May 31 09:14:39 2017 +0100 +++ b/handouts/ho01.tex Mon Jun 19 10:44:28 2017 +0100 @@ -18,6 +18,8 @@ %% email validator %% http://www.ex-parrot.com/%7Epdw/Mail-RFC822-Address.html +% https://jackfoxy.github.io/FsRegEx/emailregex.html + %% regex testers % https://regex101.com diff -r 7d9d86dc7aa0 -r 5c9de27a5b30 handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r 7d9d86dc7aa0 -r 5c9de27a5b30 handouts/notation.tex --- a/handouts/notation.tex Wed May 31 09:14:39 2017 +0100 +++ b/handouts/notation.tex Mon Jun 19 10:44:28 2017 +0100 @@ -69,9 +69,9 @@ \defn{Strings} are lists of characters. Unfortunately, there are many ways how we can write down strings. In programming -languages, they are usually written as \dq{$hello$} where the +languages, they are usually written as \dq{\texttt{hello}} where the double quotes indicate that we are dealing with a string. In -programming languages, such as Scala, strings have a special +typed programming languages, such as Scala, strings have a special type---namely \pcode{String} which is different from the type for lists of chatacters. This is because strings can be efficiently represented in memory, unlike general lists. Since @@ -114,12 +114,10 @@ write \textit{foo}, \textit{bar}, \textit{foobar} or \textit{foo $@$ bar}. -Occasionally we will use the notation $a^n$ for strings, which -stands for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is -a string that has as many $a$s by as many $b$s. - -A simple property of string concatenation is -\emph{associativity}, meaning +Occasionally we will use the notation $a^n$ for strings, which stands +for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is a string that +has as many $a$s by as many $b$s. A simple property of string +concatenation is \emph{associativity}, meaning \[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\] @@ -141,15 +139,19 @@ \{1, 2, 3\} \] -\noindent The notation $\in$ means \emph{element of}, so $1 -\in \{1, 2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false. -Sets can potentially have infinitely many elements. For -example the set of all natural numbers $\{0, 1, 2, \ldots\}$ -is infinite. This set is often also abbreviated as -$\mathbb{N}$. We can define sets by giving all elements, for -example $\{0, 1\}$ for the set containing just $0$ and $1$, -but also by \defn{set comprehensions}. For example the set of -all even natural numbers can be defined as +\noindent The notation $\in$ means \emph{element of}, so $1 \in \{1, +2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false. Not that the +\emph{list} $[1, 2, 3]$ is something different from the \emph{set} +$\{1, 2, 3\}$: in the former we care about the order and potentially +several occurrences of a number; while with the latter we do not. +Also sets can potentially have infinitely many elements. For example +the set of all natural numbers $\{0, 1, 2, \ldots\}$ is infinite. This +set is often also abbreviated as $\mathbb{N}$. Lists can be very large, but they cannot contain infinitely many elements. + +We can define sets by giving all elements, for example $\{0, 1\}$ for +the set containing just $0$ and $1$, but also by \defn{set + comprehensions}. For example the set of all even natural numbers can +be defined as \[ \{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\} @@ -162,8 +164,9 @@ \{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\} \] -\noindent Notice that set comprehensions could be used -to define set union, intersection and difference: +\noindent Can you see why this defines the set $\{0, 1, 2\}$? Notice +that set comprehensions could be used to define set union, +intersection and difference: \begin{eqnarray*} A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\ @@ -200,13 +203,28 @@ \noindent but using the big union notation is more concise. -While this stuff about sete might all look trivial or even -needlessly pedantic, \emph{Nature} is never simple. If you -want to be amazed how complicated sets can get, watch out for -the last lecture just before Christmas where I want you to -convince you of the fact that some sets are more infinite than -others. Actually that will be a fact that is very relevant to -the material of this module. +While this stuff about sets might all look trivial or even needlessly +pedantic, \emph{Nature} is never simple. If you want to be amazed how +complicated sets can get, watch out for the last lecture just before +Christmas where I want to convince you of the fact that some sets are +more infinite than others. Yes, you read correctly, there can be sets +that are ``more infinite'' then others. If you think this is obvious: +say you have the infinite set $\{1, 2, 3, 4, \ldots\}$ which is all +the natural numbers except $0$, and then compare it to the set +$\{0, 1, 2, 3, 4, \ldots\}$ which contains the $0$. Yes, the second must be more infinite\ldots{} well, then think again. Because the two +infinite sets + +\begin{center} + $\{1, 2, 3, 4, \ldots\}$ and + $\{0, 1, 2, 3, 4, \ldots\}$ +\end{center} + +\noindent +contain actually the same number of elements. Does this make sense? +Though this might all look strange this about infinite sets will be a +topic that is very relevant to the material of this module. It tells +us what we can compute with a computer (actually algorithm) and what +we cannot. Another important notion in this module are \defn{languages}, which are sets of strings. One of the main goals for us will be how to