2007/10/18

• 本講義を受講するB3学生へ
  • 成績は基本的に「期末試験＋レポート課題」で付けます。出欠は取りますが，「試験＋レポート」をしっかりやれば単位は取れますので，授業に出る必要は必ずしもありません。もちろん，Javaがよく分かっていない学生は出た方が良いでしょう。
  • 課題の連絡や授業の進捗状況は随時webにuploadしますので，このページは随時チェックするように。
• 配布資料
  • 「コンピュータってどうやって動いているのか？」についてのプリント
  • 峯松の自己紹介＆本授業の概要に関するプリント
  • 皆さんのこれ迄の計算機とのお付き合い度を調べるアンケート
  • 今年の2年生は1年の時にプログラミングをやっていない学生が多いですね。駒場での情報教育カリキュラムが変わったと聞いていますが，コンピューター言語＆プログラミングは省かれた，，，のでしょうかね？
  • 今年から，C&Java の授業以外に，演習の時間があります。こちらの方も履修しましょう。演習をしっかりやっておかないと，後々苦労します。
• 講義内容
  • 峯松の自己紹介（私の駒場時代を含めて・・・）
  • 授業の概要（Javaの言語仕様＋アルゴリズム／数値解析の基本）
    • ３年になってから更にアルゴリズムの授業があります。本授業は導入部分ですね。
  • コンピュータの native language についての説明
    • コンピュータ＝CPU＋メモリ＋IO，として考え，各々について簡単に説明しました。
    • CPU＝演算バカ，メモリ＝記憶バカ，それを制御するのが人間（皆さん）
    • CPUの母語をマシン語と言い（00110101,,,），それを少し分かり易い命令語で置き換えたものがアセンブリ言語。このレベルになってCPUの母語と言える。
      • ちなみに，，，母語と母国語は異なる。母語はその人の第一言語，母国語はその人の国籍となる国の言語，韓国育ちの日本人は母語が韓国語，母国語が日本語で，母語の方が流暢になる，，ということもよくある（一応，自然言葉の研究してますので，ここらへんの定義には，ちとうるさい）。
    • マシン語／アセンブリ言語というのを初めて見た／聞いた人は，図書館に言って，簡単な図書を読んでみると良いでしょう。例えば，これとかこれとか。学部を出るまでに一度は，101010000 でプログラムを組んでCPUを動かす，という経験をすると良い。何事も，話として知っているのと，経験／感覚として知っているのでは雲泥の差があるものです。
      • ちなみに，ですが，これを"% gcc -S test.c"としてアセンブリ言語に変換したものが，これです。"% gcc -v" で "gcc version 4.0.0 20041026 (Apple Computer, Inc. build 4061)" と表示される gcc 使っています。
    • 結局，CやJavaが書けたって，計算機に「語りかけている」ことにはなりません。プログラマ雇って，作成するプログラムの仕様を，彼らの母語（日本語，英語，，，）で伝えて，プログラム書いてもらう，のと，CやJavaで書いて，コンパイラさんという翻訳家にマシン語に翻訳してもらうのと同じじゃん，，，という意識を少しは持った方がよい（計算機の生の姿を知ろう，という意味で）。コンパイラ氏などに，私のJava作文の翻訳など任せておけん，自分で翻訳してやる！という意気込みを一度は持つと良い。一度でいいですが。
• 宿題
  • 今週はありません。次回以降のお楽しみ，ということで。
• 次回予告
  • 次回は，教科書の 3-2 節辺りまでやると思います。なお「読めば分かる」と思われる部分はスキップします。一通り読んできてください。
  • この教科書に掲載されているソースコードは入手可能です。ここから。
    • 「補足情報」をクリックして出てきた画面の下半分がソースコードの説明。Windows用とLinux用とがあるが，iMacで作業する人は，SRC.lzhを入手すれば大丈夫のはず。各自，自分の作業環境にダウンロードしておくこと。
    • Javaの本が無い人は，教科書を購入した方がよいでしょう。教科書，及び，教科書に出てくるソースコードなどを見ながら説明します。
  • なお，教科書ですが，前半戦でやるのは，１〜10章です。時間があれば，11章もちょっとやります。12章，13章（ネットワークとGUI）はこの授業では扱いません。あしからず。

2007/11/1

• 配布資料
  • 無し
• 講義内容
  • 教科書第一章，第二章，第三章（3.1節）までやりました。
  • Javaプログラミングのお作法と，データ型についてやりました。整数だけでもメモリとの絡みで値域別に4種類，浮動小数点は2種類の型があります。文字型も，かつては1バイト整数型としての文字型だったのが（C言語など），Javaでは2バイト整数型として文字型ができていること，などをやりました。
• 宿題
  • 計算機上では全ての情報が数値として表現されます（最終的には01100の2進数）。文字もその例外ではありません。例えば，文字 'w' もある数値として扱われます。この文字と数値との対応としてJavaではUNIコードなる体系を使っています。この他にも，asciiコード，JISコード，シフトJISコード，EUCなど様々なコード体系が存在します。つまり，今，目の前にある 'w' という文字は，場所と環境によって，その実体（数値）が異なることになってきます。対象とする 'w' の意味・概念は変わらんのに，それを数値表現するときの対応は変わるってか？どうして複数のコード体系が存在するのだろうか？asciiコード，JISコード，S-JISコード，EUCコード，UNIコードの順に調査し（web 上の情報リソースで構いません），これらのコード体系を説明し，複数のコード体系が存在する由来・理由について調査せよ！Computer Scienceの歴史における文字の取り扱いの変遷，といったところでしょうか？
  • 整数型に1/2/4/8バイト幅の型があり，浮動小数点型に4/8バイト幅の型がありました。整数型の場合は，数値を0/1のビットパターンに変換するのは，10進数を2進数に変換するような形で行なわれるのだろうな，という想像がつくと思います。では，浮動小数点というのは，例えば，double型の場合8バイト（64ビット）をどのように使うことで，浮動小数点を表現しているのでしょうか？webリソースで構いませんので，これについても調査せよ！
  • 整数の負の数をどうやって2進数で表記するのか，ということを少し解説しました。「ビット反転して（正数だと考えて）1足す」と負の数になること，と同時に，何故，その操作が「マイナス」という概念と結びつくのか，について説明しました。少し説明の時間が短かったかもしれませんが，凡そ通じたかな，と思っています。確認の意味で，「ビット反転して（正数だと考えて）1足す，という操作が，何故，マイナス，負，という概念と結びつくのか」について，貴方自身の言葉で説明して下さい。そうですね。相手が高校生だと思って，2進数を知ってる高校生に教える積もりで作文してみて下さい。人に教えることが「自分が何をまだ理解していなかったのか」に気付く手っ取り早い方法です。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-11-01-NNNNNNX と記入する。11-01 はその宿題に対応する授業が行なわれた日付（11月01日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 〆切は，11/7午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • 健闘を祈る。
• 次回予告
  • 第三章の残りと第四章の終わりまでやりたいですね。

2007/11/8

• 配布資料
  • 無し
• 講義内容
  • 先週の課題の存在を知らずに，まだ出してない人がいたら，提出しましょう。多少減点はしますが，提出したらしたで点はつきます。
  • 出欠表が一枚しか峯松のところに戻ってきてません。もう一枚が行方不明です。持って帰った人，次回必ず提出して下さい。
  • ブラウザ上の文字が小さい！という人は，メニューバーから「表示」「文字の拡大」でも使って下さい。ラジオの音が小さいなら，ボリュームを上げるのと一緒。
  • 教科書第三章（3.2節〜），第四章（〜4.4節）までやりました。
  • 配列に関してかなり時間を割いて説明しました。C言語やマシン語との比較をしながら，メモリーにアクセスする場合，通常アドレス（番地，住所）を指定してアクセスするのが本来の姿であることを説明しました。これは，携帯電話で「山田太郎」という項目を選んでボタン一つで電話する場合も，ちゃんと「山田太郎」の電話番号の情報が伝送されるのと同じで，変数名としてaという名前を使っていたとしても，マシン語のレベルでは「XX番地から始まる4バイト分のメモリ領域にYYを書き込む」というようなマシン語になります。数字を使ってアクセス先を特定する，ということです。電話，郵便番号，部屋番号，座席番号，世の中には数字で場所を特定する習慣が至る所にありますが，計算機も同じで，番号を使って場所を特定しています。
    • その番地を整数として格納するための変数が（C言語で言う）ポインタ変数です。こう考えると何も難しくありません，よね。
  • じゃ，いつも番号（アドレス）で特定すればいいじゃん，となりますが，結局携帯電話では，「山田太郎」という項目を選択してボタン一つで処理するように，獲得したメモリ領域に対して，a とか，b とか，名前を付けて，その名前に対してデータを代入する，という形で「表記」した方が理解しやすい，ということで，通常のプログラミング言語では，a = 15; のような形で表記することになります。
  • int a; という形で基本型の変数を宣言した時に，使われるメモリ領域は毎回変わるのか？という質問を受けました。作成したプログラムを走らせる時にメモリのどの部分が使えるのか，というのはその時その時によって異なります。Word や Excel を裏で走らせていたら，当然使用できるメモリ領域は限られてきます。よって，その都度，その都度割り当てられるメモリの物理位置は変わってきます。逆に言えば，どのアドレスのメモリが使えるか，その時にならないと分からないので，アドレスを具体的に指定するようなプログラムは通常は書かない，となります。変数で a, とか，b とか名前を付けておいて，その名前と実メモリとの対応は，そのプログラムを実行した時に，OS の方が担当してくれます。
  • まだ「参照型」というものをきちんと定義してませんが，配列は参照型の一つ，ということで，参照型と基本型の違い，及び，参照型と（C言語で言う）ポインタ変数を使ってメモリーにアクセスする方法の類似性について説明しました。基本型と参照型の違いについては（これから何度か出てきますが），次のことを常に意識して考えるようにして下さい。「メモリ内のある部分空間に付けた名前，ラベル」を通して，そのメモリ空間の中身にデータを書き込む／そこからデータを取り出すのか（ラベルさえあれば，そのメモリ空間が，全空間の中のどこに位置しているのか，その場所についてはあまり意識する必要がない）」，「そのメモリ空間の場所の情報を使って，（間接的に）データを書き込む／取り出すのか（場所の情報を意識する必要あり）」この二つの方法のどちらを使ってメモリアクセスを行なっているのか，ということです。この違いを，今のうちにきちんと身につけておかないと，いつまでたっても，計算機（特にメモリーアクセス）というものがぼんやりしたイメージでしか捉えられません。
  • ちょっとくどいようだが，例えば，，，あるホテルのフロントでの会話。
    「このバラの花を，山田花子さんに届けたいのですが，，，」
    「今，外出中ですね。後で届けておきます，，，」
    （一時間後）「おい，田中（スタッフの一人），そこのバラ，35号室のお客さんに渡しといて」
    山田花子というラベルで送り先を指定するのか，35号室という数字で（場所情報）で送り先を指定するのか，みたいな違いです。何でそこまでくどい説明をするのか，と感じている学生もいるかと思いますが，いずれ，この二つを混同している自分を見つけることになる，，，かもしれません。
  • 演算子についても，'+' 一つとっても色んな「意味」をこの '+' に持たせていることを強調して説明しました。'=' も厳密にはそうですね。こういう微妙な「意味」の違いを感覚できる，ということが，計算機をマシン語レベルで眺めることができている，といったことに繋がるのだと思います。逆に言うと，日頃使っている自然言語の運用が，如何に我々の暗黙知に支えられているのか，ということでもあります。そういうのに敏感な人は，言語学者になるのでしょうね。
• 宿題
  • ちょっと変な課題を出してみたいと思う。教科書59頁のリスト3-10（Array4.java）に対して，プログラミングを始めたばかりの高校生が以下のような質問をしてきた。君なら何と答える？自分の言葉で説明するように！
    • 「Array4.java において配列 a, b を定義して，a は {1, 2, 3} で初期化しているから，各々の要素に対する実体（メモリ）が確保されて，そこに 1, 2, 3 が代入されています。その後 b=a; と a を b に「代入」しています。この場合，b 用に実体（メモリ）が確保されて，b の実体に対して，b[0]=a[0], b[1]=a[1] というように各々の値がコピーされるのでは「なく」，b=a; というのは，b を a の「別名，あだ名」として初期化している，と聞きました。でも，a, b が普通の int 型なら，b=a; は，a の内容を b にコピーする，という「意味」なんだから，a, b が配列の時だって，b=a; というのは，a の内容が b にコピーされる，と解釈するのが自然だと思います。配列の時だって，a の内容が b にコピーされる，というように考えちゃいけないんですか？あだ名とか，別名とか，何か変！そもそも，b=a; という見た目が同一の表現にどうして複数の解釈を認めるのか，それがよく分かりません！変なの！」という，へ理屈高校生を救って下さい。
  • 教科書76頁において，加算演算子（'+'）が多種多様な機能を持つことを学んだ。「文字列 '+' 数値」なんてのは，ピントこなかった人もいると思う。授業でこれまで扱った型（基本型と文字列）を使って，色んなものを「足してみて」Javaが定義する '+' の多様性を確認せよ。数値と言っても，float やら double やらあるでしょう。また，'+' 記号にここまで多様な機能を持たせる，というのは，作ったプログラムが「思いも寄らぬ動作」をする（'+' 記号が，思った以上のことをしてしまうが為に，こちらの意図通りに動作してくれない）可能性がでてくると思われるが，この点についてどの思うか？素直な感想を述べよ（君がプログラミング言語を設計する場合，どういう戦略を立てるのか，というのを考えてみよ）。
  • int型のキャスト「(int)」を用いて double 型の変数 x を四捨五入して int 型にするにはどのようにすればよいか。x が負の数の時のことも考慮して回答せよ。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-11-08-NNNNNNX と記入する。11-08 はその宿題に対応する授業が行なわれた日付（11月08日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 〆切は，11/14午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • 健闘を祈る。
• 次回予告
  • 第四章（4.5節）〜第六章終わりまで解説する予定。

2007/11/15

• 配布資料
  • 無し
• 講義内容
  • 教科書第六章の6-3-3までやりました。六章は6-3-4のみを残す形で時間切れとなりました。
  • 演算子の残り，制御構造（if, switch），ループ構造（for, while, do while）の辺りです。これは，どの計算機言語にも備わっている言語仕様ですので，多くの学生にとっては復習になったのだろうと思います。
  • 演算子に関しては，種々の「何だ？この表記は？」というのを幾つも取り上げました？基本的には「頻出する表現に関してはより少ないタイプ数で済ませよう！」というズボラさからきた（？）発想かと思います。「a>b?a:b」なんてのは，一番初めに「こういう表現を使おうじゃないか！」と言い始めた人は白い眼で見られたのでは無いでしょうか？今となっては色んな計算機言語で見られる表現です。慣れてしまえば何てことないですが，初めて目にした人は（今日の教室にも数名はいたはずです），「何これ！」と思ったでしょう。やがて，そういう表記を自然な表現として感覚できるようになりますが，「何だよこれ？」という感覚は大切だと峯松は思います。
  • 「プログラム」と言うと運動会のような進行表を思い出す人もいると思いますが，あれは全てがシーケンシャルに（順番通りに）行なわれるだけです。計算機工学（Computer Science）で言うプログラムでは，もっと複雑な制御が可能です。そういう複雑な制御構造をもった指令書を計算機に与えて仕事させよう，と言う訳です。
  • ただ，同じようなことを実装するのに，異なる表現形式が用意されている，ということは，どの表現形式を使うことが「今実装しようとしている機能」を「読み手（そのプログラムを誰かが読む場合の読み手）」に分かり易く伝えることになるのか，という問題に関係してきます。「for も while もループなんだから，while だけ覚えとけばいいや」という態度が，読み手に「誰だよ，これ書いたの，読みづらいな，，，」と言わせる原因になってきます。適材適所で使い分けが出来るようになりましょう。
  • 今後，同じようなことを，異なるやり方で表現できる，というのを沢山学ぶことになるでしょう。異なるやり方が用意されている，ということは，それに何らかの理由があるはずです。「方法Aと方法Bの違いがどういう時に生きて来るのだろうか」などと考えながら読むと，単なる「暗記もの」ではなく「思考もの」になるので，身に付きやすくなるでしょう。似ているものが二つ与えらた時に「似てるなー」と感覚するでしょうが，その次に「で，何が違うン？」と考えれば，色々興味も沸いてきます。
• 宿題
  • 指定した通りのSubjectを付けて来ない人がいます。日付はメールを出した日付ではなく，授業があった日付です。何通かはゴミ箱に行ったかもしれない・・。
  • 11/08日の出欠表を持っている人は連絡下さい。2枚の紙に出欠を書いてもらったのですが，1枚しか峯松のところに届いていません。
  • 問１：教科書p.128（第六章の最後）にこんなことが書いてある。
    • 6-1-2でも述べたように「，」（カンマ）を使うと，for文の初期化式と更新式に複数の文を記述することができます。この時，更新式に文を複数記述すると，判定式でfalseになった時（forループが終了する時）にも処理を実行させられます。例えば，1から1000までの足し算を行なうプログラムは，次のように書くことができます。
      for( i = 1 ; i < 1000 ; x += i, i++ ) {
      
    • さて，上記の教科書の記述に対して問題です。上記の記述は正しいかどうか，頭で考えよ（実際にプログラムを書いて動かすのではなく）。仮に誤っている場合「どこが誤っているのか」を明記し，及び「何故，そのような誤りを彼はしたのか」を推測せよ。
  • 問２：昨年までは第四回目の授業の後に簡単なプログラムを書かせて，実行させて提出させてました。今年からは金曜日の演習の授業があるので，そちらにお任せしようか，と考えています。今，川原先生と確認しています。明日中には fix しようと思います。再度 web をチェックして下さい。
    • 宿題は問１だけです。昨年まで出していたプログラムを書く宿題は，演習の方に回します。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-11-15-NNNNNNX と記入する。11-15 はその宿題に対応する授業が行なわれた日付（11月15日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，11/21午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • 健闘を祈る。
• 次回予告
  • 第七章「オブジェクト指向プログラミング」をやります。前半戦（Java言語仕様）の後半3回に突入します。Javaマスターでない学生は，必ず一読してどこが「？」なのか，頭の整理をしてくるように。必ず，です。後半3回がC言語との違いになります。この違いが分からないと，「方法Aと方法Bの違いが，どういう時に生きて来るのだろうか」などと考えることも出来なくなります。C言語とJavaは使えるようになりましょう，ということで，この二言語を教えている訳ですが，その違いが（高校生相手に？）語れるようになりたいものです。これからの3回が前半戦のヤマです！

2007/11/22

• 駒場祭で休講です。昨年まで本授業で出していた宿題の一部を演習の方で16日に行なったと川原先生から聞きました。出来がどの位だったかも。多少変更があったかもしれませんが，昨年出していた宿題を下記に示します。Javaの言語仕様に関して三回授業が終わりましたが，ここまではあまり他の言語との違いはありません。C言語の言語仕様ともよく似ています。ので，現段階での宿題につまずいている人は，Javaが分らない，というよりも，プログラミングというものがまだしっくり来ていないのだと思います。三連休もありますので，しっかり復習して下記課題は全部こなせるようにして，後半の三回（Java言語仕様）に臨むようにして下さい。これからグンと難しくなります。
• 宿題（提出する必要は無いですが，次回の授業までにクリアするように。でないと困るのは君です）
  • 問１：与えられた数が素数であるかどうかを検査するプログラム PrimaryNumber.java（文字コード：Shift_jis, 改行コード：DOS/WIN）を完成させよ。なお，自然数 n が素数であるかどうかは，2〜n-1 の自然数で割り切れるかどうかで検査する。上記ソースコードは穴あきソースコードとなっているので，適宜埋める形で所望の機能を実現せよ。提出は「穴を埋めたソースコード」＋「実際にそのプログラムを走らせた結果」を示したファイル（text or PDF）を提出せよ。
  • 問２：とある中学校の各クラスの学生数が与えられている（ソースコード参照）。
    あ）全学年，全クラスを通して得られる１クラス当りの平均生徒数
    い）各学年毎に得られる（その学年の全クラスを通して得られる）１クラス当りの平均生徒数
    う）各クラス毎に得られる（３学年を通して得られる）１クラス当りの平均生徒数
    を求めるためのプログラム ClassSize.java を完成せよ。穴埋めソースコードとプラグラム出力結果を一緒に示したファイルを提出すること。
  • 問３：与えられた配列の最大値，最小値を求めるプログラム MaxMin.java を完成し，結果の出力と一緒に提出せよ。
  • 問４：与えられた配列に対して，値の大きい順に並べ替えるプログラム Sort.java を完成し，結果の出力と一緒に提出せよ。
• 次回予告
  • 「オブジェクト指向プログラミングと構造化プログラミングの違いについて，へ理屈高校生にその違いを分かり易く説明しなさい」という問いを与えられて，「はい。分りました」と言う自身が無い人は，しっかり予習してきて下さい。毎回次回の授業で扱う範囲を指定してますが，その部分に目を通してこないと，出席しても意味無いでしょう。

2007/11/29

• 配布資料
  • 無し
• 講義内容
  • 6.3.4をさくっと終わらせ，七章に入りました。7.4.3までやりました。オブジェクト指向プログラミングとしてのJavaの説明に入りました。
  • Javaを通して計算機言語を初めて学ぶ学生は「一体何がオブジェクト指向なのか」分からないのでは，と思います。比較対象としての計算機言語の知識が無いからです。その一方，PascalやC言語を通してプログラミングに精通した人は，「ヘ〜，こんなことができるんだ，面白そう。こういうのがオブジェクト指向なのねん。なるほど」と思うのでは無いでしょうか？この両者の感覚の違いは「大きい」です。
  • ということで，C言語との比較を通して峯松流にオブジェクト指向という「プログラミング・パラダイム」を説明しました。Cにしろ，Javaにしろ「人間流の思考プロセス」を「計算機流の思考プロセス」に翻訳するのが目的です。計算機流の思考プロセスとは，まあ，アセンブリ言語の世界としておきましょう。皆さんが「こういうことを計算機にさせたい」と感覚したことをアセンブリ言語に翻訳するに当たって，どういうインタフェースを用意することが「より楽に」翻訳作業ができるようになるのか，これを考えるのが計算機言語設計者の仕事です。つまり，歴史的に古いPascalやCなどと比べながら，何故，Javaなどのオブジェクト指向言語が出てきたのか，ということを考えながら教科書を読むようにしましょう。
  • PascalやCといった構造化プログラミング言語は「関数呼び出し」が基本です。データを関数（function, procedure, subroutineなど色々呼び名があるので注意）に投げて，その出力を受け取る，という流れでプログラムを書きます。主役は関数，データはその脇役，みたいなイメージです。
    • 峯松は言語研究者（言語研究者と言っても，計算機言語ではありません。自然言語，音声言語です）ですから，関数が主役の言語，と言うと，述語が主役となる言語を想像してしまいます。通常の自然言語は（その統語，文法構造のみを考えれば）述語が主役と考えられています。述語（アクション）がまずあって，その主体は誰？，客体は誰，何？と考えます。
    • 関数が主役，データはその脇役として捉える以上は，両者は分離されて考えられていることになります。実際のアセンブリ言語でもメモリーはCODE部とDATA部に分かれる様子を示しました。
  • 一方オブジェクト指向言語というのは，関数が主役ではなく，オブジェクトが主役になります。実世界では，目の前にいるのは例えば「猫のミケ」であって，「あくび，という行為があって，その主体がミケである」とは感じない，，，でしょう。と同時に「猫のミケ」であれば，ニャーと無く，ゴロゴロ喉を鳴らす，あくびする，など色々なアクションが「猫のミケ」の（属性としての）アクションとして存在する，と考えることもできます。こういう物事の見方を通して計算機に様々な依頼をできるような言語を作ろう，として生まれたのがオブジェクト指向言語が生まれました，と峯松は捉えています。
    • 結局，オブジェクトとは主体（データ）とアクション（関数）とを分離せず，同居させて考えるプログラミング・パラダイムであり，構造化言語と比較すれば，遥かに主体（データ）にスポットライトが当たっている，という感じがします。
    • 「あくび（ミケ）」，と書くのではなく「ミケ．あくび」と書きたい訳です。上記した自然言語論との絡みで考えれば，統語構造のみを考えれば，自然言語はC言語的（構造化プログラミング言語的）なのかもしれません。ですが，（世界の）意味記述というものを考えれば，自然言語はJava的となるのかもしれません。
    • なお，情報の隠蔽などの機能もオブジェクト指向プログラミングの重要な側面です。次回以降説明します。
  • もう少し，計算機言語的な記述をしましょう。例えば，行列を表現する参照型（クラス）として，matrix というのがあった場合，
    matirx m1, m2;
    
    m2 = m1.inverse();
    と言った感じで，m1 の逆行列を計算して m2 に代入する，ということが可能ですが，C言語では，例えば，
    CalcInverse(m1, &m2);
    みたいなコーディングになります。「どっちでも良いじゃん」と言って来る学生も多いと思います。そういう学生の気持ちも理解できます。前者が「データ」という主体に対して「これやってね」とお願いしている感じがするのに対し，後者は「これやりたいんだ。あ，このデータにね」と言っている感じでしょうか？どちらの方が皆さんの感覚に対して「より自然に」訴えかけるか，です。そしてその「より自然」という価値判断が，一体，何に基づくのか，です。プログラミング作業（計算機に対するお願いごとの記述）を，皆さんの実世界に対する世界観と同一の枠組みで出来れば，オブジェクト指向プログラミングの方が自然になる，のかもしれません。
  • プログラミングはプログラミングで，単なる作業であって，そこに世界観だの何だの，いちいちうるさい！と感じる方は，構造化プログラミングも「そういうものか」，オブジェクト指向プログラミングも「そういうものか」で終わりだと思います（何れもアセンブリに落ちれば同じようなコードになりますしね）。変な例を出してみましょう。「彼女に惚れたのか」，あるいは「恋することに恋い焦がれて，で，とりあえず今の彼女と付き合っているのか」の違い，と言うと，無茶苦茶でしょうか。本当に惚れたことがある人はオブジェクト指向プログラミングが理解でき，そうで無い人は，，，。もう止めましょう。「データ」と「処理」この両者の関係をどう捉えるのか，という観点から二つのプログラミング・パラダイムを吟味してみると良いでしょう。
• 宿題
  • 問１：C言語の構造体をまだ学んでいない，と聞きました。まず，C言語で言う構造体とは何者なのか，これを調査せよ。教科書を読むもよし，google様にお伺いを立てるのも良いだろう。コピペではなく，自分の言葉で説明して下さい。へ理屈高校生を想定してください。
  • 問２：オブジェクト，クラス，インスタンスについて，授業での説明を踏まえ「各自の言葉」で説明せよ。特にクラスについては，C言語の構造体との比較を通して説明せよ。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-11-29-NNNNNNX と記入する。11-29 はその宿題に対応する授業が行なわれた日付（11月29日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，12/5午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
• 次回予告
  • 引き続き，オブジェクト指向プログラミングの基本的概念の説明を行ないます。金曜日の演習も通してしっかり理解して下さい。

2007/12/6

• 配布資料
  • 無し
• 講義内容
  • 情報のアップデートが遅れ気味になって申し訳ない，，，。師走モードに突入しています。
  • 教科書7.4.4から8.3.4までやりました。
  • オブジェクト，クラス，インスタンスについての再確認，オーバーロード，コンストラクタによるインスタンス生成，ラッパークラスによる基本型のオブジェクト化，継承，オーバーライド，情報の隠蔽（カプセル化）と内部情報へのインタフェイスメソッド，クラス間のキャスト，などがキーワードです。オブジェクト指向言語と言われる計算機言語には凡そ備わっている機能ですので，しっかり身につけておきましょう。各々について自分の言葉で説明できるようにすべきであることは勿論ですが，何故，そのようなプログラミングの枠組みが提唱されたのか，C言語などの構造化プログラミング言語との違いを意識しながら，整理整頓すると良いと思います。Java だけ知ってても，Javaのメリットは分からないと思います。C言語と比較しながら，Javaの長所，短所を自分なりに吟味する癖を付けると良いと思います。
  • オブジェクト指向プログラミングのお作法的な事柄について，幾つか解説しました。情報の隠蔽化をして（クラス内のメンバー変数に直接 = で値を代入することを避ける），メンバ変数のアクセスのためのメソッドを準備しておく，などは，その代表例だと思います。getXXXX，setXXXX というメソッドに何度も遭遇することでしょう。そういう遭遇を通して「こうやってメソッド群を揃えるのだな」という感覚が身に付くのだと思います。
  • あと，参照型が，インスタンス（メモリ実体）が存在する場所の情報を有する，ということから，参照型変数が実際に指す相手（インスタンス）が，その参照型クラスの実体だったり，その参照型の親クラスの実体だったり，その参照型の子クラスの実体だったり，と色々面倒なことが起こる可能性があります。C言語のポインタ変数も，
    char mojiretsu[30];
    double *dptr;
    
    dptr = (double*)mojiretsu;
    などと言うことが可能なように（char型の配列の先頭から，double型のデータが詰まっているかのように扱える），場所の情報を使ってメモリをアクセスする場合，その場所にどのようなフォーマットでデータが書き込まれているのか，ということに注意する必要が生じます。コンパイラなどの言語処理系が型の整合性をチェックしてくれる場合もありますが，最終的にはプログラマの責任でメモリへのアクセスが行なわれることも多いです。参照型／ポインタ変数の使い方に注意すると共に，慣れて行きましょう。変数名（ラベル名）でメモリにアクセスするのか，場所（アドレス）の情報でメモリにアクセスするのか，です。
• 宿題
  • 問１：クラスの継承とはどのような機能を言うのか，「各自の言葉」を用いて説明せよ。特に計算機言語系に継承という機能が実装されていることでどのような恩恵をユーザは得ることになるのか？考えよ。
  • 問２：授業で分数計算を行なうためのクラスを設計し，コンストラクタや幾つかのメソッドを設計，実装した。複素数を表現するためのクラスを設計し，複素数の計算を行なうためのメソッドを設計することを考える。下記について考察せよ。
    • どのようなコンストラクタを実装しておく必要がありそうか，そのクラスが使われる状況を考えて考察せよ。
    • どのようなメソッドを実装しておく必要がありそうか，そのクラスが使われる状況を考えて考察せよ。
    • なお，具体的な実装は演習の方で行なうことになるでしょう。上記の問いは「どう設計すべきか」という観点から考えなさい，ということです。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-12-06-NNNNNNX と記入する。12-06 はその宿題に対応する授業が行なわれた日付（12月06日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，12/12午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
• 次回予告
  • 教科書8章の残り，10章（ストリーム）をやります。時間の余り具合に応じて，9章（例外処理），11章（マルチスレッド）をやります。いずれにせよ，次回でJavaの言語仕様は終了です。
  • なお，12/20から始まる後半5回でアルゴリズムの基礎をやります。アルゴリズムの方はプリントを配ります。12/13の授業中に，3回分のプリントを配ります。出席していない友人の分ももらっていく，というのは基本的に「×」とします。欠席者は自分で友達の分をコピーしなさい。
  • 毎年「アルゴリズムに入っていきなり難しくなった」という感想が来ます。今年は少しペースダウンしてやろうと思っていますが，学生の方も予習をしてくるようにしましょう。渡すプリントは自習用テキストのコピーです。
  • 逆に「アルゴリズムの部分はもっと難しくしてもよいのでは」という意見も少数ですが，来ます。アルゴリズムの授業は三年になってからもあります。この授業は基礎の基礎を担当しています。「もっと難しくして！」という妙な学生は，来春まで待ちましょう。

2007/12/13

• 配布資料
  • 次回以降，三回分の授業で使うプリントを配布しました。次回使うのは「計算量」と書いてあるプリントです。なお，60部刷って持って行きました。本日の学生数は58名です。授業後「プリントが無い」と言ってきた学生がいます。すぐ上に「欠席した学生の分をもらっていくことは禁止している」と書いています。黙って欠席者の分までとっていった学生，あるいは「プリントをもらってきてくれ」と頼んだ学生，「悪いことをした」と思うのなら，次回，コピーをとって持ってくるように。小学生相手にするような作文を，教官にさせないように。
• 講義内容
  • 教科書八章の残り，九章「例外処理」，十章「ストリーム」をやりました。これで，Javaの言語仕様の解説は終わりです。
  • 「抽象クラスと，それを継承する形で存在する具象クラス」及びそれに似た枠組みとして存在する「インタフェース」など，類似した項目が計算機言語には色々存在します。何度か言っているように，似たような（でも異なる）モノが存在する場合，各々何らかの必要性があって，そのような類似した（でも異なる）枠組みが存在している訳です。抽象クラス−具象クラス，とインターフェイスも，両者の違いだけでなく，なぜ，そのような類似した枠組みを敢えて揃えているのか，といったことについても調べてみる（考えてみる）と良いでしょう。宿題で「XXXについて説明せよ」というのを出していますが，理解できているようには思えない文章も結構あります。よそから借りてきた言葉だな，と思える文章も結構あったりします。
  • 第十章「ストリーム」で，ファイルやキーボードからの情報入力／出力について学びました。ストリームのopen, close操作，及びopen操作（メソッド）を行なうことで得られるインスタンス変数を使って，より便利なクラス（のコンストラクタ）を呼び，そのインスタンスを得る。そして，そのインスタンスのメソッドを使って，効率的に，情報の入出力をする。最後は close する。という一連のお作法を学びました。及び，便利（そう）なメソッドの幾つかについて学びました。テキストファイル／バイナリファイルの違いについても解説しました。
• 宿題
  • 問１：「抽象クラス−具象クラス」と「インタフェース」の相違点について「自分の言葉」で論ぜよ。参考にした情報源についても明記せよ。
  • 問２：「オーバーロード」と「オーバーライド」の相違点について「自分の言葉」で論ぜよ。参考にした情報源についても明記せよ。
  • 問３：ファイル（ストリーム）操作を行なうために，種々のクラスが用意されていることを学んだ。ストリーム操作のために用意されているクラスについて調査せよ。各クラスの継承関係，各クラス間の差異，用意されているメソッド等々，調べることは沢山あるが，特に範囲を限定せず宿題として課してみようと思う。ストリーム操作に関するクラスを調査して報告せよ。参考にした本，webなどがあればそれも明記せよ。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-12-13-NNNNNNX と記入する。12-13 はその宿題に対応する授業が行なわれた日付（12月13日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，12/19午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • なお，c-algo@gavo 宛に出したメールに対して，返事が自動的に送られるようにしている。その返事の様子が今までと少し変わってきた，との報告を受けた。Mac OS X に標準で付いているMailクライアントを使っています。特定フォーマットの Subject のメールが来たら，自動返信するようにしています。従来と何も設定を変えていないので，何かが変わったと言われても「？」な状況です。いずれにせよ，届いたことを知らせる目的でやってますので，そのメールが届いていれば問題無いでしょう。
    • あと，返信メールが来ていない人もいるのでは，と思います。昨年までのMailクライアントはこの返信機能がまともに動かなくて困りました。今年は（Leopardは）まともに動いてくれているようですが，時々「？」な時があります。近々，レポート受理状況に関する excel ファイルを upload する予定ですので，最終的にはそれで確認して下さい。
• 次回予告
  • 本授業の後半に突入します。アルゴリズム基礎編です。配布した資料の「計算量」と一ページ目に書いてあるプリントを使います。とある自習書をコピーしているので，基本的には読んで理解できるはず，，です。必ず一読してから次回の授業に参加するようにして下さい。

2007/12/20

• 配布資料
  • アルゴリズム基礎を3回行ないますが，その後2回行なう数値計算のプリントを配布しました。
• 講義内容
  • 遅れて申し訳ない。師走になると，あれこれ忙しくなって，updateしている時間がありません。
  • 後半戦開始です。1)計算量，2)参照型とObjectの復習，3)配列を使ったリストの実装（スタック）をやりました。待ち行列に関しては次回に持ち越しです。
  • 計算量ですが，なぜ，このような大ざっぱな指標が存在するのか，をよく考えるようにしましょう。CPUの種類，メモリの量，雇ったプログラマの質，計算機を走らせる時の室温（？？）など，プログラムを計算機で実行させる時には様々なものが影響してきます。その中で，純粋にアルゴリズムの善し悪しを議論したい（言い換えれば，アルゴリズムの善し悪し以外の要因を揃えたい）場合に，結局どういう指標とならざるを得ないのか，を考えましょう。計算時間が入力データ量nの増加に対して，どのような増加関数となるのか，を見ることになります。
  • 参照型とObjectに関して「Robotクラスの作成」という良い例が教科書にありました。参照型を使ったコピーには，幾つものレベルが可能であること，実際に行ないたいコピーはどういうコピーなのか，考えて実装する必要があることが理解できたかと思います。また，全てのクラスはObjectという神（アダムとイブ？）の子どもたちとして位置づけられますので，Objectクラスで定義されているメソッドは，どのクラスにおいても使えることになります（メソッドの継承）。ですが，作成したクラスで意味のある動作をするように，オーバーライドする必要があります。equals()メソッドや，ToString()メソッドなどは，どのようなクラスを作成した場合でも，必要になるメソッドですよね。こういうメソッドの「ひな形」がObject神には既に用意されていて，それを下々の者は使える訳です。こういう枠組みがきちんと見えて来ると，オブジェクト指向言語ってのは結構有り難いな，という感覚が芽生えて来るかもしれませんね。
  • 授業の中で，アルゴリズムやデータ構造という「言葉」についての説明が不足していたかもしれません。アルゴリズム＝問題解決のための手順一覧。対象とする問題を解決できるアルゴリズムであっても，賢い（計算量が小さくなる）ものから，NGなもの（計算量が大きくなる）まで色々です。今授業で取り扱っている題材に即して言えば，大量にあるデータを，如何に賢く格納し（登録し），検索する（時には削除もする）にはどういう戦略を立てればよいか，といったことになります。実世界でも，色んな書類をどうやって「整理整頓」して棚に置けば，その後ハッピーになれるのか，というのを考えると思います。要は，それ，です。自分の引き出しを開けてみて，日頃の自分の行いをチェックしてもよいかもしれません。３年生向けに書いた資料があることを思い出しました。参考になるかもしれません。こちらからどうぞ。
  • データ構造を考える際に，物理的にデフォルト的に用意されてあるデータ格納の枠組み（＝配列）とリストとの違いを強調しました。元々ハードウェア的に備わっているデータ収納の枠組み（一番チープなデータ構造です）に対して，その枠組みを色々脚色して，お化粧して，非常に使い易いインタフェースを作ってあげると，データの格納（追加），削除などの操作が楽になる，といった感じで説明しました。「使い易いインタフェース」を作るためには，どういう目的で使われるのか，どういう機能，functionsが実装されていなければいけないのか，といった議論が必要で，Table 4.1 は良い例です。「あると便利な」機能が，賢く（計算量小さく）実装してあれば，それが，良いインタフェースとなり，良いデータ構造，良いアルゴリズムになります。毎年試験をすると，物理的に備わっているデータ格納の枠組みと，ソフトウェア的なお化粧とをキチンと区別できていない学生が少なからずいるように感じています。
  • 計算量について学生から一つ質問がありました。whileループなどを展開すれば，有限個の（例えば15回とか）関数呼び出しに展開されるので，個々の関数呼び出しがO(1)であれば，結局，15 x O(1) -> O(1) となって，全ての計算量はO(1)になるのでは，という質問でした。確かに，入力のデータ個数 n に対して具体的に150とか数字を与えると，whileループの回数とかは具体的に決まってきます。で，個々の関数呼び出しの計算量はO(1)であれば，15 x O(1) といった議論になります。ですが本来計算量とは，そのアルゴリズムが必要とする処理量が，入力データの大きさを n とした時に，（処理量が）n の何に「比例」するのか，という議論です。つまり，n が 150 から 1500に変化した時に処理量がどう変化したのか，が問題であって，n=150の時に何分かかったか，ではありません。入力データの量やサイズが変化した時に，全体の処理量がどう変化したのか，を議論する必要があります。計算量の基本的な考え方を再度復習しておきましょう。
• 宿題
  • 問：全てのクラスの親玉（というか，アダムやイブのようなもの）として，Objectというクラスがあることを説明しました。またObjectクラスに対して定義されてたるメソッドがあることも説明しました。このObjectというクラスについて調査せよ。用意されてあるメソッドや，Objectクラスの使用上の注意等，色々知っておくと得することも多いだろう。なお，クラスを自前で定義した際に，既に使えるようになっているメソッド群がある，というのは，C言語（の構造体）との大きな違いである。複数の言語を習得する場合，言語間の違いを意識しながら，習得すると良いでしょう。
  • 正月休みになります。Javaの文法について復習しておきましょう。中学，高校と6年間英語を勉強したかと思います。海外から来たお客さんをもてなすことができる学生はどのくらいいますか？日本だけで生活する場合，あまり英語が必要無いのが日本の社会です。今，JavaとC，という計算機言語を習得していますが，これが使えるようになってないと，後で大きく困ることになります。正月休みのうちにきちんと復習して，再度頭に叩き込んでおきましょう。なお，修士課程に行こうと思っている人は，英語もきちんとやっておきましょう。でないと，困るのは君です。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-12-20-NNNNNNX と記入する。12-20 はその宿題に対応する授業が行なわれた日付（12月20日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，1/9午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • なお，c-algo@gavo 宛に出したメールに対して，返事が自動的に送られるようにしている。その返事の様子が今までと少し変わってきた，との報告を受けた。Mac OS X に標準で付いているMailクライアントを使っています。特定フォーマットの Subject のメールが来たら，自動返信するようにしています。従来と何も設定を変えていないので，何かが変わったと言われても「？」な状況です。いずれにせよ，届いたことを知らせる目的でやってますので，そのメールが届いていれば問題無いでしょう。
• 次回予告
  • 本日のやり残し（待ち行列）を片付けます。その後，連結リストと木構造に入ります。プリントは，必ず，一度目を通してくるようにしましょう。

2008/1/10

• 配布資料
  • 無し
• 講義内容
  • 前回のやり残しである，待ち行列を片付けた後に，連結リスト・循環リスト・双方向リストについて解説し，木構造は二分木の説明までしました(p.155)。なお，教科書はこれを使っています（特に，授業に出てない学生さんへ。下記で教科書のページ数とか出しているので）。
  • 待ち行列の中で「%」を使った常套手段が出てきました。カウンタの値を1〜N-1までの整数に割り振る時に頻繁に使います。また，ダミーのセルを一つ入れておく，という常套手段もありました。こういう細かい工夫が今回の授業には幾つか出てきました。個々の工夫を詳しく覚える，というよりも，そういう工夫されたソースコードを眺めた時に「何でこんなダミーセルを置いてるんだ？バグかしらん？」などと勘違いしないようにしましょう。
  • 連結リストの基本は，「データ」と「データを繋ぐリンク」がセットになったものが一つの要素（セル）になっている点です。何度も配列とリストの違いを説明しました。ハードウェア的に備わっているデータ構造である配列を，そのまま使うと，挿入／削除の際に使い勝手が悪いです。その理由は，あるデータを格納する容器の隣の容器がどこにあるのか，というのがハードウェア的に固定されているからです。その固定された容器群を使ってデータを並べるのが配列です。1331の部屋には椅子（容器）が固定されてますから，隣の椅子というのは固定です。これに対して，椅子に「ひも」を付けて，その「ひも」を遠く離れた椅子に付けることを考えます。そして，「隣の人（データ）」とは，そのひもによって連結された椅子に座っている人のことを指す，と定義すると，ハードウェアのしがらみから離れて「隣のデータ」を定義することができます。これが配列とリストとの違いです（良い例かどうか，分かりませんが）。物理（ハードウェア）的に用意されている原始的な容器群に対してお化粧を施して，論理（ソフトウェア）的に非常に使いやすい容器群があるように「見せかける」，ということです。デートする時に身だしなみを整えるのと一緒です。そのうち化けの皮が剥がれるのは時間の問題ですが。
  • この，「データ」と「データを繋ぐリンク」のセットを一方向に繋げたものが一番単純な線形リストで，ぐるっと回したのが循環リスト，そして，双方向に移動できるようにリンクを二種類もたせたのが双方向リストとなります。
  • 幾つか，定石的な方法が示されていました。ダミーセルを設ける，p, q 二つのリンク（ポインタ）を使ってリストをスキャンする，などです。これらの定石を使うと，最初のセル，最後のセルなどの境界条件の扱いが楽になります。「境界条件に注意する」というのも身につけるべきセンスです。
  • 木構造，及びその一番シンプルなバージョンである二分木についてその定義を述べました。二分木はデータと，右下，左下への部分木の根に対するリンクを持ちます。双方向リストもデータと，右横，左横へのリンクを持たせたものが単位（セル）になってました。下とか，横とか言うのは，紙の上に図を書く時にどう配置するのか，の違いですから，プログラム上は違いはありません。データ＋他の２つのセルへのリンク，という意味では双方向リストも二分木も同じようなものです。次回話しますが，このリストを使って二分木を実装します。
  • 配列という原始的なデータ構造を使って，スタックや，待ち行列を（ソフト的に）作りました。リストというやや原始的なデータ構造を使って，木構造を（ソフト的に）作る，ということになります。ソフト的に作る＝バーチャルに作る，ということになります。こういうバーチャルな論理世界に興味がある人はその人のイマジネーションを使って，より使いやすい（優れたインタフェースを備えた）データ構造を作ることになるのでしょう。バーチャルな世界は嫌い，現実／物理路線で攻めたい！という人は，アセンブリ言語を使う，いやいや，電子一個の挙動を追うのも一つの選択でしょう。ただ，バーチャルのみ，アクチュアル（現実）のみ，に捕われると融通が聞かないので，バランス良く知識とセンスをモノにしていきましょう。
• 宿題
  • 問：今回の授業の中で，C言語でのメモリの確保＆解放に対して，Javaはコンストラクタでメモリを確保するが，解放することは明示的に行なわなくてもよいことを説明しました。参照型を使って，メモリ実体を指していた場合，そのメモリを指しているリンクが全て外れた場合（いずれのリンクもその領域を刺さなくなったら）自動的にメモリは解放されます。この枠組みを「ガーベッジコレクション」といいます。「ゴミ集め」ということです。誰も指さなくなった領域は，誰も使えない，ということでゴミ同然です。ならば，さっさと解放して利用可能なメモリ領域に戻してあげればよい訳です。以上，ガーベッジコレクションの概要を説明しましたが，このメモリ管理という観点からJavaとC言語を比較して，自分の言葉で説明しなさい。なお，参考にした情報源も示しなさい。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-01-10-NNNNNNX と記入する。01-10 はその宿題に対応する授業が行なわれた日付（1月10日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，1/16午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • なお，c-algo@gavo 宛に出したメールに対して，返事が自動的に送られるようにしていますが，時々返事が送信されないことがあるようです。心配な人は「メール届きました？」という連絡を入れてくれれば答えます。
• 次回予告
  • 木構造のやり残しと，アルゴリズムの基礎の最終回，探索，を取り上げます。一読してから授業に臨むように。

2008/1/17

• 配布資料
  • 無し
• 講義内容
  • 二分木にぶら下がっている節を全て走査する方法として，三通りの方法（順番）があることを示しました。現在着目している節，その節の左側の部分木，右側の部分木，の三者を考えた場合，どこから順次走査するか，で三通りあります。三通りあることよりも，走査するプログラム（関数，メソッド）が自分自身を再帰的に呼び出している点に注意して下さい。何も考えずに自分自身を呼び出せば，無限回呼び出すことになり，プログラムが終了しません。再帰的なプログラムは必ずその関数の冒頭に「ある条件が満たされたら，更に再帰的に自分自身を呼び出す前にさっさと returnする」となっているはずです。
  • 一般的な木を線形リストを使って実装する方法についても説明しました。配列を使って，スタック／待ち行列を実装するように，リストを使って木構造を実装する訳です。より原始的なデータ構造を使って，ちょっと賢い（賢く見えるだけ？）データ構造をこしらえる訳です。二通りの方法が示されていました。前者は，各ノードから一方通行リスト（線形リスト）を伸ばし，そのリストのセルに子供のノードへのポインタ（リンク）を入れます。もう一つは，親→長男→そのまた長男，，というようにリンクを伸ばし，個々の世代から，兄弟に向けてリンクを伸ばす，という方式です。で，これは首を45度傾けると，あら不思議，二分木になってるじゃない，という代物です。この本では，子だくさんの木を「一方通行リスト」と「二分木」で実装しています。他にも方法がある，かもしれません。これらはデータ構造としては同じものになりますが，その実装方法は異なっています。
  • あと，教科書のソースコードに Java らしい記述を見つけました。p.163のリスト77行目から始まる，BinaryTreeNode tree = の宣言ですが，これが，Fig. 6.7 そのもの，というのが分かりますか？ new BinaryTreeNode （つまりコンストラクタ）の連発ですね。メモリを動的に確保しています。こういうコーディングを見ると，C言語に染まった頭だと（峯松自身はそういう頭をしていると思う），どこで確保したメモリ開放してやるんじゃい？と問いたくなりますが，そこらへんを賢く処理系の方で対処しているのがJavaの有り難いところです。逆に言うと，メモリの開放をプログラマがしょっちゅう忘れてしまうので，処理系で面倒見ましょうね，というのがJavaがジャバジャバしている所以です（？？）。
  • 探索方法としてハッシュ法を説明しました。その前に，線形探索，二分探索についてちょこっと復習しました。
  • ハッシュの概念は至った簡単です。「な〜んだ」というのが分かるように解説したつもりです。例えば文字列データを格納する場合に，その文字列をじーっと眺めると，35 という数字が見えてきたので，35番目の配列（部屋）に入れちゃえ！みたいな方法論です。こうすれば，データ（厳密には key）を見ただけで，それを格納すべき場所が一発で見つかる，即ち，O(1)が実現できる，ということです。
  • ですが，問題は異なるkeyが同一の場所情報（ハッシュ値）を返す場合があり，それにどう対処するか，で，チェイン法とオープンアドレス法というのがある，というお話でした。
  • チェイン法は「場合分け機能付き線形リスト」として解釈できることを示しました。で，場合分けがハッシュ関数に相当します。異なるkeyが同一の場所に来ることを念頭に置いて，バケツに線形リストをぶら下げる（即ち，場合分け）ということです。こう考えると，チェイン法やらハッシュ法やらという名前を付けるのではなく「場合分け線形リスト」として覚えた方が頭が混乱しなくて済む，と思うのは私だけでしょうか？
  • オープンアドレス法は，チェイン法とは考え方が全く異なります。文字列を見て 35 という数字が見えてきたので，35番目の部屋に入れちゃえ！までは同じなのですが，そこが埋まっていた時に「じゃ，隣でいいや」と隣の部屋をノックして空き部屋が見つかるまで探すのがオープンアドレス法です。
  • 「こんなんで，賢く探索／削除ができるんかいな」と思われるかもしれませんが，「削除済み」マーク，「空室」マークをうまく使うとそれができちゃう，というのも示しました。
• 宿題
  • 問：教科書p.194に，オープンアドレス法に関して下記の記述がある。
    「再ハッシュとの兼ね合いから，オープンアドレス法では，バケットの個数B（＝ハッシュ表の大きさ）は素数，あるいは，2^n−1（2のn乗−1，nは整数）といった数にするのが望ましいとされています」
    何故そうなのかを考察し，自分の言葉で説明せよ。また，各種情報源を自分で調査し，上記も含め，賢いハッシュ関数を作るための指針についてまとめなさい。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-01-17-NNNNNNX と記入する。01-17 はその宿題に対応する授業が行なわれた日付（1月17日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，1/23午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • 検討を祈る。
• 次回予告
  • アルゴリズムの前半戦（３回分，データ構造とアルゴリズムの基礎）はこれで終了です。データ構造とアルゴリズムの続編は，３年前期の授業でまたありますので，そちらでまた，揉まれて下さい。田浦先生が担当しています。
  • 本授業のアルゴリズムの後半戦は数値解析です。計算機を使って，微分／積分を行なう，方程式を解く，行列演算をする，といったことをやります。いずれも近似手法ではありますが，解析的に（数式的に）は解けない問題でも，計算機をつかってガリガリ計算することで近似解は得られます。その方法の第一歩について解説します。
  • 数値積分，非線形方程式，ニュートン法，常微分方程式のプリントを一読してきて下さい。

2008/1/24

• 配布資料
  • 無し
• 講義内容
  • 数値計算の第一回目をやりました。数値積分，非線形方程式，ニュートン法，常微分方程式です。講義でも何度か強調しましたが，数式を展開して解ける問題は，そうやって解くべきであって，数式展開で解く方法が無い（解析的に解けない）問題に対して，計算機を使って，その多くは繰り返し計算で，近似解を求めよう，ということです。
  • 解析的に解けない，ということは，美しく解けない，ということですから，泥臭く解くしかありません。計算機を使うというのは，計算機の（文句を言わずに作業をこなす）計算パワーを当てにして解いてみよう，ということになります。
  • 数値積分，非線形方程式，ニュートン法，常微分方程式，いずれも原理は「ナーンだ」というものだったと思います。でも，その「ナーンだ」であっても，問題が（近似的に）解けることによって，初めて可能となる応用やら，技術やらが存在することを考えれば，あながち侮れません。
  • また，計算機が幾ら早くなったとは言え，解くべき問題が複雑であれば，計算に必要な時間は指数関数的に増加します。XX法，YY法と微妙に違う方法論が色々並んでいましたが，それぞれ長所・短所があり，場面によってどの方法論が一番効率よく近似解をもたらすのか，というのを考える必要があります。
  • ちなみに，ですが，数学演習で，種々の非線形な微分方程式の解放を習っていると思います。リッカチの方程式，とか色々名前がついている解法があったはずです。「こういう形をした非線形微分方程式はこういう変数変換をやって解け」みたいなknow-howが沢山出て来たと思います。別の言い方をすれば，非線形な方程式というのは基本的には解けないけど，幾つの場合は，解く方法が知られており，それを一つ一つ習得しておきましょう，ということになります。でも「解ける方程式群の裏に，何か共通の枠組みというか理論のようなものは無いのだろうか？」「know-howは色々出て来るが，これらを統一的にまとめた理論のようなものは無いのだろうか？」と感じた人がいるかもしれません。実はソリトン理論というのがそれに相当する，と聞いたことがあります。解ける非線形方程式（の解法）は，全てソリトン理論を使って導出することができる，みたいな議論です。know-howが沢山出て来て「なんだかな」と思った人は少しかじってみてもいいのかもしれない。
  • 下記，余談ですが。常微分方程式を式として解くのではなく，グラフが描ければ「解けた」ことにしようよ，みたいなことを言いました。高校での数学では，きちんと y = f(x) の形で明示して初めて微分方程式が解けた，となります。ですが，例えば物理学の中で数学を使うのは，力学の場合は，時刻 t の現象を見ることで，Δt秒後の世界がどうなっているのかを知ることが目的で，時刻 t の現象と時刻 t+Δt での現象との関係が数式で書かれなければいけない，ということは「無い」とも言えます。目的は，未来を予測することであって，予測ができれば，それがどういう数式なのかは分からなくてもいいじゃん，というものの考え方です。大学で力学（ニュートンの力学方程式）を微分方程式として初めて解釈した人もいるでしょう。微分，積分ってこのために作られた枠組みだったのか，ニュートンが力学という分野を作るためのツールとして作ったのか，というのを初めて知った人も多いでしょう。逆に言えば，それ以前は，物理学と数学とは別ものだったの？とも言えます。今となっては，物理学と数学は非常に仲良しのように皆さんは受け入れているかもしれませんが，物理の専門家，数学の専門家に言わせれば「なぜ，物理学は数学とこんなに相性が良いのか，それが分からない」となります。そもそも別物なんだ，ということです。自分の頭の中で勝手に作り上げた数学的枠組み，公理があり，その下に定理があり，，，，勝手に数学的イマジネーションの世界を作った。それが，ある時，或る物理学者から「貴方の作った数学的枠組みが，実はブラックホールの謎を解くための枠組みとして非常に有効に使えます！」という電話をもらう，といったようなことを想像してみて下さい。本人はブラックホールなんぞこれっぽっちも考えずに作ったのに，それが，こんな物理的問題を解くために使えるなんて。こういう例は幾つか実例があります。で，そういう方々は言うのです。「なぜ，物理学は数学とこんなに相性が良いのか，それが分からない」とね。計算機を使ってゴリゴリ解く，というのは，色々アルゴリズムを知る楽しみもありますが，今までとは違った見方で問題を捉えられるようになる，そういう側面もあります。
• 宿題
  • 問：「パイこね変換」に関する話題について検討してみる。まず「パイこね変換」について，これの1.1節辺りを読んで下さい。「パイ」をこねるような変換が「パイこね」変換です（説明になってませんね）。この「パイこね」操作を計算機で追って行くことを考えたい。この図に従って，パイこね変換を数式化する。パイの初期状態では，パイは0<=x<=1の領域に広がっている。図には，これを二倍に引き延ばし，折り畳む様子が示してある。このパイこね操作を繰り返した時に，初期状態時の点Xの座標（つまりx）はどこに動くかを求めたい。当然，xの初期値は 0<=x<=1 を満たす任意の実数となる。点xは「引き延ばし＋折りたたみ」によって，どこに移動するかと言えば，x<=0.5の場合は，2xとなり，x>0.5の場合は，2-2xとなる（図参照）。この 2x，あるいは，2-2x を再度初期値として「引き延ばし＋折りたたみ」を延々と繰り返す演算をする。パイ生地を作るためにどのくらいこねる必要があるのか峯松はよく知らないが（研究室の中国人留学生で以前イタリアン・レストランでバイトしていた学生がいるので聞いておこう），上記の演算を繰り返して，点xがどう動くのかを追跡する。
    1-1：x=0.1から開始して，N回（定数として与えればよい）「引き延ばし＋折りたたみ」操作を繰り返した後のxを計算するプログラムを作成せよ。
    1-2 : N=5,6,7,8,9,10の時の x の値を求め，xはどのように動いているのか考察せよ。
    1-3 : N=100の時の x の値はどのようになっているか求めよ。N=1000の場合はどうか？
    1-4 : 「え！」と目を疑った人，なぜ，そのような結果になったのか考察せよ。中国人留学生がパイをこねるとパイは消失しないだろうが，計算機に任せるとパイは消失してしまうのだろうか？
    1-5 : 上記の考察を踏まえ「計算機を使って，数値計算させる場合に注意すべきこと」について考察せよ。
  • 提出はメールにて行なう。下記の注意事項を守ること。守っていない場合はそのレポートはゴミ箱行きかもしれない。
    • Subject の欄に必ず半角でかつ全て大文字で，C-ALGO-01-24-NNNNNNX と記入する。01-24 はその宿題に対応する授業が行なわれた日付（1月24日），NNNNNNは学籍番号である。学籍番号が5桁の者は一桁目を0（ゼロ）とする。Xは学生番号最後のアルファベットである。月や日が一桁の場合は，一桁目を０（ゼロ）として二桁化するように。Subject の文字列を参照して上記フォーマットのメールのみ宿題として受入れる。誤った Subject のメールは無視する可能性があるので注意せよ。
    • メールの本文冒頭に学籍番号，氏名を明記すること。毎年名無しのゴンベの宿題が来る。Subjectの番号から氏名を割り出すのは結構面倒である。
    • メールに直接書くか，ファイルを添付する場合は，PDF に変換して添付するように。添付ファイルが PDF で無いものは，見ない可能性がある。
    • 提出先のアドレスは c-algo@gavo.t.u-tokyo.ac.jp である。
    • 〆切は，1/30午後11時59分59秒（次回授業の前日，メールの送信日を見て判断する）とする。
    • 検討を祈る。
• 次回予告
  • 最終回です。行列演算に関するプリント，一読して来るように。補講を入れています。部屋はいつも通り，1331です。

2008/1/31

• 配布資料
  • 無し
• 講義内容
  • webの更新が遅れてしまいました。申し訳ない。修論審査週間に突入しております。
  • 数値計算の2回目です。基本的には連立一次方程式の解法ですが，準備として行列の操作，また，紙と鉛筆で行なう連立方程式の解法とは異なる（計算機らしい）解き方についても解説しました。最後に，この連立一次方程式が解けるようになるとできる応用として，最小二乗誤差最小の評価基準の下での直線近似，多項式近似について簡単に説明しました。
  • 行列の操作，即ち，列の交換，行の交換というのは，紙と鉛筆で中学生に連立方程式を教える際には，何ら意味を持たない操作です。3x+2y を 2y+3x と書き直せることに感動する中学生がいれば別ですが，，，，。なぜ，こういう操作が計算機相手に連立方程式を解く際には重宝されるのか，というのを理解すると，計算機使いに一歩近付けた，ということにもなります。
  • 前回の宿題でやった「パイこね」変換で，誤差というのが時として思いも寄らない（想像すら出来ない）結果をもたらすことを知りました。となれば，そういう誤差項ができるだけ生じないように計算機のお尻を叩けるようになっておくと，後で後悔しないで済みます。計算機が表現する情報は有限個のビット列でしかありません。となれば，そもそも実数という集合全体を表現できないのは当たり前で，計算機を使って実数計算すること自体「意味ねえんじゃないの？」と言いたくもなりますが，そういう誤差が出来るだけ生じないように注意しながら使えば，そこそこ良い近似解（実用的な解）を出してくれるのは事実です。
  • 今回の場合，割り算の分母に来る数字がゼロに近くなると，その割り算が誤差項を生む可能性が高くなる，ということが問題でした。ですので，中学生には意味は無くても，行と列の置き換えをすれば，解の精度が上がりますので，それを事前にやった，ということになります。同様の問題は，例えば，かけ算した結果に，更にある数をかけ，さらにかけ，，，とかけ算を繰り返すと，かける数が1より大きいと overflow してしまう，1より小さいとやがてはゼロになってしまう。といった問題もあります。かけ算を繰り返す，あるいは，割り算を繰り返す，ということで double 型のレンジでは足りなくなるような場合には，数値を対数化して足す／引く，といったことも広く行なわれます。
    • そもそも，聴覚系や視覚系が刺激の物理量に対してその対数値に比例するような反応を示すのは，自然界にある刺激の物理量のレンジが非常に広いから，その対数値に比例して反応するような枠組みをもっていた方が生体のハードウェアとしてコストがかからない，といった議論もあります。まあ，皆さんの体が知らないうちに学習したことを，君らの脳は意識下で学習できるか，ということでもあります。
  • 中学生が連立方程式を解く手順を，難しい言葉で，前進消去＆後退代入法と言います。これが分からない人は，家庭教師先の中学生に聞きましょう。面白いのは，反復法の方でしょうか。(7.20)式のように書けば，右辺の(x1,x2)を初期解，左辺の(x1,x2)を更新された解として解釈することは可能ですが（ズバリ方程式の解ならば，左辺と右辺は等しくなります。その式を更新式と強引に解釈しています。），その場合，更新することで解の精度が良くなってないと意味ありません。で，その後の議論により，ある条件が満たされる場合においては，更新することで解の精度が上がることが証明されます。線形代数を知っていると，たまには役に立つこともあるのであ〜る。
• 宿題
  • 遅れてしまったので，提出義務は設けませんが，昨年出していた宿題を示します。各自自分でやってみて下さい。
  • 配布資料93頁の演習課題7.1の前半，及び，101頁演習課題7.2を解け。連立方程式を消去法とガウス（ザイデル）法で解く，というものです。
    • 「やる，やらない」は皆さんの自由ですが，頭で理解することと，指使って体で体験することは別物です。
• 次回予告
  • 楽しい期末テストについて
    • 3月6日（木）9:00〜10:30，1331号室（いつもの部屋です）
    • 成績は「α x 期末テストの点数＋（1-α）x 提出課題の点数」と期末テストと提出課題とを重みを付けて加算します。重みをどのくらいにするかは未定です。
    • 提出課題を全く出していない人でも，期末テストで点数をとれば単位は取れます。優がとれることもあるかもしれませんが，課題が全く出ていなければ，困難でしょう（不可能では無いでしょうが，例外的でしょう）。
    • なお，テスト中に来年度の授業に向けて，簡単なアンケートをとります。ご協力下さい（アンケート未回答でも，点を引くことはありませんので，ご安心を）。
    • 遅くなりましたが，レポート提出状況（峯松の把握状況）と言った方が早い？を示します。excelファイルです。0=未提出，1=提出，2=〆切後に提出，です。2をどう評価するかは，，，内緒です。