Information Technology Seminar I: Schedule

Understanding Computation

Aoyama Gakuin University, Summer 2014, Martin J. Dürst (last updated 2015-05-26)

(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 (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 -E UTF-8 --simple-prompt. Once in irb, use require 'absolute_program_name' or require_relative 'relative_program_name'.

April 9
Introduction: Martin J. Dürst
Homework for April 17: Install Ruby (install the latest versions of Ruby 1.9 (or Ruby 2.0) from RubyInstaller;
currently the newest versions are 1.9.3-p545 and 2.0.0-p451. There is also a 64-bit version: 2.0.0-p451 (x64))
For a gentle introduction to Ruby, please also see Programming Basics II (2011)
April 16 (minutes: 三浦)
a) Just Enough Ruby (pp. 1-4 + Learning Rails, Logic and Conditionals, pp. 340-347) 田中
b) Objects and Methods (pp. 5-14): 山本
April 23 (minutes: 山本)
c) Programs and Machines (pp. 15-32) 佐原
d) Statements (pp. 33-48) 堀内
April 30 (minutes: 佐藤 喬樹)
e) Denotational Semantics (pp. 49-62) 宮原
f) The Simplest Computers (pp. 63-79) 岡村
May 7 (minutes: 堀内)
g) Regular Expressions (pp. 79-94) 中川
h) Equivalence and Minimization (pp. 94-103) 苅宿
May 14 (minutes: 中川)
i) Just Add Power (pp. 105-118) 元岡
j) Nondeterministic Pushdown Automata (pp. 118-134) 杉山
May 21 (minutes: 宮原)
k) The Ultimate Machine (pp. 135-147) 佐藤 淳吏
l) Nondeterministic Turing Machines (pp. 147-158) 佐藤 喬樹
May 28 (minutes: 岡村)
m) Computation and Computability (pp. 159-174) 三浦
A) Numeric Operations (pp. 174-192) 元岡
June 4 (minutes: 元岡)
B) Advanced Programming Techniques (pp. 192-206) 苅宿
C) Universality is Everywhere (pp. 207-224) 堀内
June 11 (minutes: 苅宿)
D) Iota, Tag Systems (pp. 224-235) 杉山
E) Cyclic Tag Systems (pp. 235-251) 佐藤 喬樹
June 18 (minutes: 杉山)
F) Impossible Programs (pp. 253-269) 中川
G) Decidability (pp. 269-284) 田中
June 25 (minutes: 田中)
H) Programming in Toyland (pp. 285-296) 佐原
I) Implementation (pp. 296-308) 山本
July 2 (minutes: 杉山)
J) Ruby Gems (RubyGems Guides) 宮原
Demos of Research at Software Lab:
July 9 (minutes: 佐原): Ruby Applications
L) SVuGy (SVuGy - Exploring the Space between Procedural and Declarative Graphics) 三浦
M) Rails (Getting Started with Rails) 岡村
July 16: Research on Ruby at the Software Lab (reports by B4/M1/M2 students)
Ruby Internationalization, 本多洋朗
Case Conversion in Ruby, 松井仁人
Data Visualization with SVuGy, 諸富裕人
A Rails Application for Extensive English Reading, 鈴木健一郎
(July 24: makeup classes)
(July 28 to August 4: Term final exams)