Information Technology Seminar I: Schedule

Understanding Computation

Aoyama Gakuin University, Summer 2018, Martin J. Dürst (last updated 2018-07-18)

(links to presentations and minutes are only accessible with a password)

Chapter and page numbers refer to Understanding Computation - From Simple Machines to Impossible Programs, Tom Stuart, O'Reilly, 2013.

Code for this book is available at https://github.com/tomstuart/computationbook (use Download ZIP if you don't want to install git). To execute, move to the directory where the code is and start irb with irb --simple-prompt. Once in irb, use require 'absolute_program_name' or require_relative 'relative_program_name'.

April 11
Introduction: Martin J. Dürst
Homework for April 18: Install Ruby (install the latest versions of Ruby 2.5 (or Ruby 2.4) from RubyInstaller (including Devkit), or make sure that your cygwin installation includes a recent Ruby version)
For a gentle introduction to Ruby, please also see Programming Basics II (2011)
April 18 (Martin J. Dürst)
Introduction to Ruby (pp. 1-14 + Learning Rails, Logic and Conditionals, pp. 340-347)
April 25 (minutes: 久田)
a) Programs and Machines (pp. 15-32): 小野
b) Statements (pp. 33-48): 高橋
May 2 (minutes: 小野)
c) Denotational Semantics (pp. 49-62): 原田
d) The Simplest Computers (pp. 63-79): 高田
May 9 (minutes: 高橋)
e) Regular Expressions (pp. 79-94): 立川
f) Equivalence and Minimization (pp. 94-103): Schalkwijk
May 16 (minutes: 原田)
g) Just Add Power (pp. 105-118): 東
h) Nondeterministic Pushdown Automata (pp. 118-134): 澤浦
May 23 (minutes: 高田)
i) The Ultimate Machine (pp. 135-147): 伊藤
j) Nondeterministic Turing Machines (pp. 147-158): 稲葉
May 30 (minutes: 立川)
k) Computation and Computability (pp. 159-174): 前川
l) Numeric Operations (pp. 174-192): 久田
June 6 (minutes: 前川)
A) Advanced Programming Techniques (pp. 192-206): 原田
B) Universality is Everywhere (pp. 207-224): 東
June 13 (minutes: 伊藤)
C) Iota, Tag Systems (pp. 224-235): Schalkwijk
D) Cyclic Tag Systems (pp. 235-251): 小野
June 20 (minutes: Schalkwijk)
E) Impossible Programs (pp. 253-269): 立川
F) Decidability (pp. 269-284): 高橋
June 27 (minutes: 東)
G) Programming in Toyland (pp. 285-296): 稲葉
H) Implementation (pp. 296-308): 澤浦
July 4 (minutes: 澤浦)
I) Ruby Gems: Main parts of Rubygems Guides (presentation): 久田
J) Bundler: Various pages from bundler.io, How does Bundler bundle? (presentation): 高田
July 11 (minutes: 稲葉)
K) SVuGy - Exploring the Space between Procedural and Declarative Graphics (presentation): 前川
L) Ruby on Rails: The Rails Doctrine (presentation): 伊藤
July 18: Research at the Software Lab (reports by B4/M1/M2 students and interns):
(July 25: makeup classes)
(July 26 to August 2: Term final exams)