Notes

ようこそ

  • 今年は、American Repertory Theaterの緊密な協力のおかげで、ハーバード大学のLoeb Drama Centerにて、素晴らしい会場が準備されており、またデモ用の小道具も整っています。
  • ハーバード大学の学生Jonathan Fisherが描いた18世紀のハーバード大学のキャンパスの水彩画をステージの背景にしました。
  • 20年前、Davidは学部生として彼自身の恐怖を克服し、自分のコンフォートゾーンの外に出てCS50を履修しました。そして、このコースがプログラミングの授業であるという以上に問題解決のための授業であることを発見しました。
  • 実際、CS50受講生の2/3は、コンピュータサイエンスのコースを受講したことがありません。
  • そして、

このコースで最終的に重要なことは、クラスメートと相対的にどの程度成長したかということではなく、コースを最初に始めたときの自分と相対的にどの程度成長したかということです。

  • まず、スーパーマリオの構成要素を再作成します。そして、ユーザが株を仮想的に売買できるようにするCS50 Financeと呼ばれるWebアプリケーションを構築し、最後に独自の最終プロジェクトを作成してコースを終了します。

コンピュータサイエンスとは?

  • コンピュータサイエンスの根本は問題解決です。
  • 問題解決とは、入力 (問題の詳細) を受け取り、出力 (問題の解決) を生成するプロセスと考えることができます。真ん中にある 「ブラックボックス」 がコンピュータサイエンス、つまり私たちが書き方を学ぶコードです。
  • そのためには、標準化された方法で情報を保存また操作できるように、入力と出力を表す方法が必要です。

数値表現

  • まず部屋の人数を数えて出席を取る作業から始めます。私たちの手を使って、一度に1本ずつ指を立てて1人を表現することもできますが、あまり多くは数えることができません。このシステムは単項と呼ばれ、各桁が1つの値を表します。
  • 私たちは、0から9までの10個の数字を使う、より効率的なシステムを学んでいます。
    0 1 2 3 4 5 6 7 8 9
  • このシステムは、各桁で10の異なる値があるので、10進法または基数10と呼ばれます。
  • コンピュータは、0と1の2桁のみを使用する、2進 (バイナリ) または基数2と呼ばれる単純なシステムを使用します。
    • 各2進数はビットとも呼ばれます。
  • コンピュータは電気で動いていて、電気はオンにもオフにもできますから、スイッチをオンにしたりオフにしたりして0か1を表すことで、便利にビットを表すことができます。
    • たとえば、電球が1つの場合、これをオンにすると1と表せます。
  • 3つの電球を使用すると、異なるパターンで点灯させることで、0 (3つすべてオフ) から7 (3つすべてオン) まで表せます。
  • 現代のコンピュータは電球ではなく、トランジスタと呼ばれる小さなスイッチを無数に持っており、それらをオン・オフしてさまざまな値を表すことができます。
  • たとえば、私たちは次の10進数は123を表すことを知っています。
1 2 3
  • 3は1の位、2は10の位、1は100の位です。
    • ですので、123は100×1 + 10×2 + 1×3 = 100 + 20 + 3 = 123と考えられます。
    • 数字の各桁は10の累乗を表します。これは各桁で10通りの数字があるからです。一番右が100、真ん中が101、一番左が102です。
102 101 100
1   2   3
  • 2進数では、数字は2通りのみで、各桁に2の累乗が対応します。
22 21 20
#  #  #
  • これは以下と同じです。
4  2  1
#  #  #
  • すべての電球またはスイッチをオフにすると、値は0のままです。
4 2 1
0 0 0
  • ここで、2進数の値をたとえば0 1 1に変更すると、2と1を加算するため、10進数の値では3になります。
4 2 1
0 1 1
  • 電球がさらにいくつかあるとすると、2進数は例えば110010になり、10進値はこの時50になります。
32 16  8  4  2  1
 1  1  0  0  1  0
  • 32 + 16 + 2 = 50. 32 + 16 + 2 = 50であることに注意してください。
  • ビットが多ければ多いほど、さらに大きな数を表せます。

テキスト

  • 文字を表現するというのは、数字と文字をどのように対応させるかを決めるだけです。何年も前に、数と文字の標準的なマッピングを定めまとめた人がいました。たとえば、文字 「A」 は番号65、 「B」 は66のようになります。このようなルールで、スプレッドシートや電子メールなど、異なるプログラムが同じビットを数値やテキストとして解釈して表示できます。
  • 標準的なマッピングであるASCIIは、小文字と句読点も含まれます。
  • 10進値が72、73、および33のビットパターンを持つテキストメッセージを受信した場合、これらのビットはHI!という文字にマッピングされます。各文字は通常、8ビットまたは1バイトのパターンで表されるため、受信するビットシーケンスは01001000、01001001、00100001になります。
    • データの測定単位として、メガ (百万) バイトやギガ (十億) バイトなどの用語にはすでに慣れていることでしょう。
  • 8ビットまたは1バイトで、28つまり256の異なる値 (0を含む) を持つことができます。(数えられる最大値は255です) 。
  • 他の言語のアクセント記号付きの文字や記号など、その他の文字はUnicodeと呼ばれる規格の一部で、ASCIIよりも多くのビットを使用してこれらの文字すべてに対応します。
    • 絵文字を受け取ると、コンピュータは実際にはバイナリ形式の数字を受け取り、Unicode標準に基づいて絵文字のイメージにマップします。
    • たとえば、 「泣き笑い顔」 の絵文字はビット000000011111011000000010に他なりません。

イメージ、ビデオ、サウンド

  • 絵文字のように、画像は色で構成されています。
  • 色を表すシステムにはさまざまなものがありますが、一般的なのはRGBです。RGBは、各色の赤、緑、青の量を示すことで、異なる色を表します。
  • たとえば、再びビットのパターンを使うと、72、73、33は、その色の赤、緑、青の量を示します (プログラムは画像ファイルを開くと、これらのビットが色に対応していることを知ります (テキストメッセージを受け取るのではなく))。
    • それぞれの数値は1バイトで、256通りの値がとれますから、3バイトで何百万もの色を表現できます。先ほどの例の3バイトのコードは黄色の濃い色を表します。
dark yellow
  • 画面上の点や四角はピクセルと呼ばれ、画像は何千~何百万ものピクセルで構成されています。3バイトで各ピクセルの色を表現することで画像を作ることができます。例えば、拡大すると絵文字のピクセルが見えます。
  • 画像の解像度は水平方向と垂直方向のピクセル数であるため、高解像度イメージの方がピクセル数が多く、保存に必要なバイト数も大きくなります。
  • 動画は多くの画像で構成されており、1秒間に複数回変化することで、昔ながらのフリップブック (パラパラ漫画) のような動きを表現しています。
  • 音楽もビットで表現することができ、数字から音符やデュレーション (音の長さ) へのマッピングなど、各瞬間の音の周波数へのより複雑なマッピングが可能です。
  • JPEGやPNG、WordやExcelのドキュメントなどのファイル形式も、情報をビットで表現するために特定の決められた標準に基づいています。

アルゴリズム

  • さて、入力と出力を表現できるようになったので、問題解決に取り組むことができます。先ほどのブラックボックスには、問題を解決するためのアルゴリズムと手順が示されています。
  •  料理のレシピなど、人間もアルゴリズムに従うことができます。コンピュータをプログラミングするときは、命令があいまいになったり誤解されたりしないように、アルゴリズムをより正確にする必要があります。
  • 連絡先をアルファベット順に並べたアプリがあなたのスマートフォンにあるかもしれません。昔ながらのものとしては、電話帳、つまり名前と電話番号を印刷した本があります。
  • 誰かの電話番号を見つけるという問題のインプットに対して、探すべきは電話帳に載っている名前です。本を開いて最初のページから始め、一度に1ページずつ名前を探します。このアルゴリズムは正しいでしょう。名前が本に載っていれば、最終的にその名前が見つかるからです。
  • 一度に2ページずつ本をめくるかもしれませんが、名前が書かれたページをスキップするかもしれないので、このアルゴリズムは正しくありません。このバグ（誤り）は、電話帳がアルファベット順にソートされていることがわかっているので、スキップしたページを探すことで修正できます。
  • もう1つのアルゴリズムは、電話帳の真ん中を開き、探している名前が本の左半分にするか右半分にするかを決め (本はアルファベット順になっているため) 、問題のサイズを半分に減らすというものです。名前が見つかるまでこれを繰り返し、毎回問題を半分にします。電話帳が1024ページであれば、半分に分けるというステップを10回繰り返すだけで、あと1ページをチェックするというところまで到達できます。これは、1ページずつ検索するアニメーションと比較して、電話帳を繰り返し半分に分割するアニメーションで視覚化できます。
  • 実際、それぞれのアルゴリズムの効率をグラフで表すことができます。
  • 一度に1ページずつ検索する最初の解決策は、赤い線で表すことができます。つまり、問題のサイズが大きくなるにつれて、解決に要する時間は直線的に長くなります。nは問題の大きさを表す数字なので、電話帳のページ数がnの場合、名前を見つけるには最大n回の手順を踏まなければなりません。
    • 一度に2ページを検索する2番目の解は、黄色の線で表すことができます。勾配はそれほど急ではありませんが、線形です。ここでは、一度に2ページずつめくるので、 (おおよそ) n / 2ステップしか必要ありません。
    • 電話帳を毎回半分に分割するという私たちの最終的な解決策は、緑の線で表すことができます。この線は、問題のサイズとそれを解決する時間との間に根本的に異なる関係 (対数関係) があります。つまり、電話帳が1000ページから2000ページになった場合でも、自分の名前を見つけるのに必要な手順は1ステップ増えるだけです。サイズが2000ページから4000ページに倍増しても、あと1ステップで済むでしょう。緑色の線はlog2 n (2を底としたときのn) とラベル付けされています。これは、各ステップで問題を2で除算しているためです。
  • アルゴリズムを使ってプログラムを書くときには、効率などの要素を考慮して、どれだけ正確かだけでなく、どれだけうまくデザインされているかも気にします。

擬似コード

  • 私たちは疑似コードを書くことができます。これは、アルゴリズムを正確な英語 (または他の人間の言語) で表現したものです。
1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If person is on page
5      Call person
6  Else if person is earlier in book
7      Open to middle of left half of book
8      Go back to line 3
9  Else if person is later in book
10     Open to middle of right half of book
11     Go back to line 3
12 Else
13     Quit
  • これらの手順を使用して、中央のページをチェックし、何をするかを決定し、繰り返します。探している名前がページ上になく、本のページが残っていない場合は、作業を中止します。そして、この最後のケースは特に覚えておくことが重要です。コンピュータ上の他のプログラムがその最後のケースを忘れた場合、説明されていないケースに遭遇したためにフリーズしたり、応答を停止したりするかもしれません。または、何のメッセージもなく、バックグラウンドで同じ作業を何度も繰り返すでしょう。
  • これらの行の一部は、動詞 (アクション) で始まります。これらを関数と呼ぶことにしましょう。
1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If person is on page
5      Call person
6  Else if person is earlier in book
7      Open to middle of left half of book
8      Go back to line 3
9  Else if person is later in book
10     Open to middle of right half of book
11     Go back to line 3
12 Else
13     Quit
  • また、道路の分岐のように、異なる経路につながる分岐もあります。これを条件と呼びます。
1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If person is on page
5      Call person
6  Else if person is earlier in book
7      Open to middle of left half of book
8      Go back to line 3
9  Else if person is later in book
10     Open to middle of right half of book
11     Go back to line 3
12 Else
13     Quit
  • どこに行くかを決める質問はブール式と呼ばれ、最終的にはyesまたはno、trueまたはfalseの値になります。
1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If person is on page
5      Call person
6  Else if person is earlier in book
7      Open to middle of left half of book
8      Go back to line 3
9  Else if person is later in book
10     Open to middle of right half of book
11     Go back to line 3
12 Else
13     Quit
  • 最後に、ループと呼ばれるプログラムの一部を繰り返すサイクルを作成する単語があります。
1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If person is on page
5      Call person
6  Else if person is earlier in book
7      Open to middle of left half of book
8      Go back to line 3
9  Else if person is later in book
10     Open to middle of right half of book
11     Go back to line 3
12 Else
13     Quit

Scratch (スクラッチ)

  • このレッスンで発見した構成要素を使ってプログラムを書くことができます。
    • functions関数
    • conditions条件
    • Boolean expressionsブール式
    • loopsループ
  • さらに、次のような機能も追加されています。
    • variables変数
    • threadsスレッド
    • eventsイベント
    • …
  • Cと呼ばれるテキストベースのプログラミング言語の使用方法を学ぶ前に、Scratchと呼ばれるグラフィカル・プログラミング言語を使用して、指示を含むブロックをドラッグアンドドロップします。
  • C言語で「hello, world」を出力する簡単なプログラムは次のようになります。
#include <stdio.h>

int main(void)
{
     printf("hello, world\n");
}
  • 多くの記号や構文、またはこれらの記号の配置を理解する必要があります。
  • Scratchのプログラミング環境はもう少し使いやすいものです。
  • 右上には、プログラムが表示する画面があり、背景、文字 (Scratchではスプライトと呼ばれます) などを追加または変更できます。
    • 左側には、関数や変数などの概念を表すパズルのピースがあり、中央の指示領域にドラッグドロップできます。
    • 右下には、プログラムで使用する文字を追加できます。
  • いくつかのブロックをドラッグしてScratchに「hello, world」と表示させることができます。
  • 「緑のフラグがクリックされたとき(when green flag clicked)」 のブロックは、プログラムの開始を示します (ステージの上に緑のフラグがあり、これを使用してプログラムを開始できるため) 。その下で、 「say」 ブロックにスナップし、「hello, world」と入力しました。これらのブロックが何をするかはインターフェースを調べて実験することで分かります。
  • 「ask and wait」ブロックに「What’s your name?(お名前は?)」のような質問をドラッグし、それを”say”ブロックと組み合わせて答えを得ることもできます。
  • 「answer」 ブロックは、プログラムのユーザが入力する内容を格納する変数または値で、ドラッグ&ドロップによって 「say」 ブロックに配置することもできます。
  • ですが、最初のブロックで 「Hello」 と言った後は待たなかったので、 「join」 ブロックを使用して2つのフレーズを結合し、猫が「hello, David」と言えるようにします。
  • ブロックをネストしたり、一方をもう一方の内側に配置したりしようとすると、Scratchはブロックを使用できる場所を拡大してくれます。
  • 実際、 「say」 ブロック自体はアルゴリズムのようなもので、「hello, world」の入力を求めるようにすると、Scratch (猫) がそのフレーズを 「言う」 という出力を生成します。
  • 「ask」 ブロックも入力 (尋ねたい質問) を取り込み、 「answer」 ブロックの出力を生成します。
  • その後、 「answer」 ブロックと独自のテキスト 「hello」 を結合アルゴリズムへの2つの入力として使用できます。
  • そしてその出力を 「say」 ブロックへの入力として渡すことができます。
  • 画面の左下に拡張機能のアイコンがありますが、その1つがText to Speechです。追加した後、 「speak」 ブロックを使用して、猫の発声を聞くことができます。
  • Text to Speech拡張機能は、インターネット上のクラウドやコンピュータサーバのおかげで、テキストを音声に変換してくれます。
  • 猫にmeow (ニャー) と言わせることもできます。
  • 「ニャー」 と3回言わせることもできますが、現在はブロックを何度も繰り返しています。
  • ループ、つまり 「repeat」 ブロックを使用しましょう。
  • これでプログラムは同じ結果を得られますが、ブロック数は少なくなります。変更したいものがある場合は、3つではなく1つの場所で変更するだけで済みます。
  • ネコをマウスの方に向けて、マウスの方に移動させることができます。
  • 条件付きの 「pen down」 ブロックを使用して、Pen拡張機能を試します。
  • ここでは、猫をマウスポインタに移動し、マウスがクリックされた場合、またはマウスが下に置かれた場合、 「pen down」 で描画します。そうでなければ、ペンを立てます。これを何度も何度も素早く繰り返すので、マウスを押したままにすると、いつでも描画の効果が得られます。
  • Scratchには、キャラクターに使えるさまざまな衣装やイメージもあります。
  • カウントするためのプログラムを作成します。
  • ここで、counter は変数で、その値を設定、使用、変更することができます。
  • 画面の端にいるときはいつでも向きを変えて、猫が画面上を永遠に行ったり来たりするbounceのようなプログラムもあります。
    • bounce1は10ステップごとに異なる衣装に変更し、アニメーションを改善しています。緑の旗をクリックしてプログラムを実行すると、猫が脚の動きを交互に変えているのがわかります。
  • コンピュータのマイクを使って自分のサウンドを録音し、プログラムで再生することもできます。
  • より複雑なプログラムを作成するには、まずこれらの単純な機能から始めて、それらを相互に重ね合わせます。
  • pet0ではマウスポインタで触れるとScratchが鳴きます。
  • barkでは、同じScratchプロジェクトに1つではなく2つのプログラムがあります。緑のフラグをクリックすると、これらのプログラムが同時に実行されます。muted 変数がfalseに設定されている場合は、一方がアシカの音を鳴らします。スペースキーが押された場合は、もう一方がミュートされた変数をtrue からfalse、またはfalse からtrueに設定します。
  • もう1つの拡張機能は、コンピュータのウェブカメラで撮影されたビデオを見て、ビデオの動きがしきい値を超えている場合にニャーという音を再生します。
  • 複数のスプライト (文字) を使用すると、それぞれに異なるブロックセットを設定できます。
  • 人形に「Marco!」と言わせるブロックを追加し、次に 「ブロードキャストイベント」 ブロックをクリックします。この 「イベント」 は、2つのスプライトがお互いにコミュニケーションをとるために使われており、舞台裏でメッセージを送るようなものです。他の人形は、この 「イベント」 を待って、「Polo!」と言います。
  • 翻訳拡張機能を使って、他の言語で何かを言うこともできます。
  • ここで、 「join」 ブロックの出力は 「translate」 ブロックへの入力として使用され、その出力は 「say」 ブロックへの入力として渡されます。
  • 基本がわかったので、プログラムのデザインや品質について考えることができます。たとえば、 「repeat」 ブロックでネコにニャーと3回鳴かせるとします。
  • より複雑な概念を単純化する抽象化を使用できます。この場合、独自の 「meow」 ブロックをScratchで定義し、meow3に示すようにプログラムの他の場所で再利用することができます。利点は、これがどのように実装され、コードで記述されているかを知る必要がなく、プログラム内で使用するだけで読みやすくなることです。
  • さらに、meow4として入力するブロックを定義することもできます。このブロックには、猫が一定回数鳴くようにするブロックがあります。これで、実装の詳細やブロックの実際の動作を知らなくても、 「translate」 ブロックや 「speak」 ブロックをどのように使用するかのように、プログラム内でそのブロックを再利用して何度でも鳴き声を作成できます。
  • Gingerbread tales remixやOscartimeなど、ループ、条件、動きを組み合わせてインタラクティブなゲームを作成するというデモを紹介しましょう。
  • OscartimeはDavidが何年も前に作ったもので、最初はスプライトを1つ追加して、それから機能を1つずつ追加していき、やがて複雑なプログラムになりました。
  • 元受講生のAndrewは、Raining Menを作りました。最終的にAndrewはコンピュータサイエンスを専門としないことになりましたが、このコースで学ぶ問題解決スキル、アルゴリズム、アイデアはどこにでも応用できます。
  • また次回お会いしましょう！