Atlas

Atlas

Atlas(地図)というブログタイトルのとおり、読者のみなさまのキャリアや思考の道しるべとなる情報を発信していきます

講義ノート:Introduction to Computer Science and Programming Using Python - edX

最終更新日:2018年6月20日

f:id:raye4483:20180523135454j:plain

講義:Introduction to Computer Science and Programming Using Python - edX [link]

概要

このコースはMITの学部生が1年次に履修する講義を、edXのプラットフォーム用に焼き直したものである。

計算機科学とプログラミングの知識を持たない人向けに、問題解決に取り組むために必要な「計算論的思考」「プログラムの書き方」を教えることを目的としている。

本記事は、私がこの講義で学んだことを順に示していく、講義ノートである。読者のみなさまの学習の指針になれば幸いである。

この講義で学ぶこと

  • 計算の概念
  • プログラミング言語"Python"の紹介
  • 単純なアルゴリズム
  • テストとデバッグ
  • 計算複雑度
  • データ構造

Week 1: Python Basics

Introduction to Python

Introduction

コースの紹介がなされる。本コースの目的は、簡単に言えば

  • 計算論的思考
  • コンピュータにして欲しい事をやらせる方法

を身につけることである。具体的なトピックとして以下の6点が挙げられている。

  • 知識表現とデータ構造
  • 反復と再帰
  • 抽象化とデータ型
  • クラスとメソッドによるモジュール化
  • アルゴリズムの種類
  • アルゴリズムの複雑度

コンピュータが行う基本的な操作は次の2つである。「計算(calculation)」「記憶(memorization)」だ。

尋常ではない速さでこの2つを実行する。それがコンピュータだ。

しかし、いくら速く計算ができても、アルゴリズムが貧弱であれば意味がない

例えば、インターネットで検索をする場合やチェスをプレイする場合には、組み合わせの数は膨大となり、「賢い」アルゴリズムを用いなければ何日もかかってしまう。

また、優れたアルゴリズムを用いても解ききれない問題や、元より計算で解けない問題というのも存在する。

Knowledge

知識には種類がある。宣言的知識(declarative knowledge)手続き的知識(imperative knowledge)だ。

宣言的知識(declarative knowledge)

事実を述べたもの

例:椅子の下にテープが貼られている
手続き的知識(imperative knowledge)

レシピまたはhow-toのこと

例:
1. 教室の前で学生と向き合う
2. 列数える
3. 真ん中の列の左端から始める
4. 右に1つずつ数える
5. 目的の椅子に到達し、テープを見つける

コンピュータにとっては手続き的知識が特に重要だ。コンピュータに細かく指示を出して問題を解決することが出来るからだ。

レシピは以下の要件を満たす。

1. 単純なステップの連続
2. いつそのステップが実行されるかを指定する
3. いつ停止するかを指定する

これをアルゴリズムと呼ぶ。

Exercises 1

Video: Introductionの項で学んだ範囲から選択式問題が出題される。

Exercises 2

こちらはKnowledgeの範囲からの出題だ。

Machines

計算機の構成の話が解説される。歴史的には、2種類のコンピュータが存在する。fixed program computerとstored program computerである。

fixed program computer

実行される命令があらかじめ決定されている。プログラムの変更はできない。

例:チューリングボム(Alan Turing's Bombe)

第二次大戦中にアラン・チューリングが開発した、ドイツの暗号機エニグマを解読する機械。
暗号解読に特化しており、他の問題を解くことは出来ない。
stored program computer

命令を保持し実行する機能を有した計算機。

例:我々がいつも使っているパソコン

stored program computerは主に記憶装置(Memory)、演算装置(Arithmetic Logic Unit)制御装置(Control Unit)で構成されている。

f:id:raye4483:20180617142610p:plain

Figure 1. 計算機の構成
記憶装置(Memory)

データや命令列を記憶する。

演算装置(Arithmetic Logic Unit)

記憶装置からデータを取り出して読み取り、加算および減算、そして論理演算を行ったあと、記憶装置に戻す。

制御装置(Control Unit)

演算装置で実行された操作を追跡・格納する。記憶装置に保存されたプログラムのどの部分を実行しているか管理している。

f:id:raye4483:20180618153341j:plain

Figure 2. チューリングマシン(Wikipediaより引用)

上図はチューリングマシンと呼ばれるもので、四角形が描かれた無限の長さのテープで出来ており、それぞれの四角形の中には記号が書かれている。
チューリングは、以下の6つの基本プリミティブさえあれば、計算可能な計算である限り、どのような計算でも行えることを証明している。

プリミティブとは、構造の構成要素である基本的な構造のことを意味している。

1. move left
2. move right
3. read
4. write
5. scan
6. do nothing

一見不可能に思えるが、これらのプリミティブを組み合わせて抽象化を行えば、さらに高度な操作を行うことができる
現在使用されているプログラミング言語は、より便利で高度なプリミティブを実行できるようになっている。

また、任意のプログラミング言語で実行できる計算は、他のいかなるプログラミング言語を用いても同様に計算できる
この性質をチューリング完全(Turing-complete)と呼ぶ。

Exercise 3

Machinesで学んだ内容に関する真偽・選択式問題が出題される。

Language

プリミティブの複雑かつ正当な組合わせを式(expression)を呼ぶ。正当な式および計算は値(value)を持ち、それは式の意味を表している。

この講義では、プログラミング言語の構造について説明するために、自然言語である英語をアナロジーとして用いて分かりやすく説明している。

プリミティブの構成要素

英語:英単語

プログラミング言語:
・数字(numbers)
・文字列(strings)
・演算(operations)
 文法(syntax)

英語:
"cat dog boy" → 文法的に誤り
"cat hugs boy" → 文法的に正しい

プログラミング言語:
"hi"5 → 文法的に誤り
3.2*5 → 文法的に正しい

つづく