Spring semester 2022
Cellular Automata
The room information below is valid starting March 7.
Lectures (28 times 2 hours) Jan 12 – Feb 25 and Mar 7 – Apr 27:
- 10:15-12:00 Wednesdays in room M3 (Quantum, 3rd floor)
- 10:15-12:00 Fridays in room M2 (Quantum, 2nd floor)
Homework sessions (13 times 2 hours) Jan 17 – Feb 21 and Mar 7 – Apr 25:
- 10:15-12:00 Mondays in room M3 (Quantum, 3rd floor)
Course Web Page: http://users.utu.fi/jkari/ca2022
Instructors:
- First half: Ville Salo
- Second Half: Jarkko Kari <jkari@utu.fi>; office: Quantum 365, 3rd floor
Prerequisites:
- No formal prerequisites. Tilings&Patterns, Topology, Automata theory are recommended.
Textbook:
- No textbook. Lecture notes will be posted on the course web page.
About homework:
- To pass the course, at least 25% of the homework problems must be completed. The more problems you solve, the more credit towards the final grade you get: You get demo class
-
- A, if you complete 70%-100%,
- B, if you complete 45%-70%,
- C, if you complete 25%-45%
of the given problems.
-
Midterms
- Two midterm exams: Dates TBA.
- Not mandatory. The class requirements can also be satisfied by taking a single final exam.
- Both midterms (3 hours) consist of 4 problems, each of which has maximum score of 4 point.
- A minimum of 5 points is required in both midterms.
- Homework activity (demo class A, B or C) and the combined score of the two midterms determine the final grade according to the following table:
|
Final Grade |
Demo class |
||
|
A |
B |
C |
|
|
1 |
13-14 |
14-15 |
15-16 |
|
2 |
15-18 |
16-19 |
17-20 |
|
3 |
19-22 |
20-23 |
21-24 |
|
4 |
23-27 |
24-28 |
25-28 |
|
5 |
28-32 |
29-32 |
29-32 |
Final exam:
- An alternative way to pass the class. One can take the exam more than once (even if one has passed the course) to improve the final grade.
- Dates TBA
- Anyone with democlass at least C has qualified to take the exam within one year.
- Exams (4 hours) consist of 5 problems, each of which has maximum score of 8 points.
- Homework activity (demo class A, B or C) and the score of the final exam determine the final grade according to the following table:
|
Final Grade |
Demo class |
||
|
A |
B |
C |
|
|
1 |
17-18 |
18-19 |
19-21 |
|
2 |
19-23 |
20-24 |
22-26 |
|
3 |
24-29 |
25-30 |
27-31 |
|
4 |
30-34 |
31-35 |
32-36 |
|
5 |
35-40 |
36-40 |
37-40 |
Tentative course outline
- Basic definitions of cellular automata and symbolic dynamics
- Injectivity, surjectivity, reversibility
- Garden-of-Eden theorem, Hedlund’s theorem
- Conservation laws, reversible CA
1st midterm
- Computational universality in CA
- Undecidability in CA
- Dynamical properties of CA, limit sets
2nd midterm