理学部数理学科４年・大学院多元数理科学研究科
講義担当：内藤久資
実習担当：内藤久資・服部哲弥・坂上貴之
【講義の内容】
情報科学・計算機に関連する種々の数学及び,計算機を利用した数学を概観する. 特に,その中にあらわ れる各種のアルゴリズムを解説し,そのアルゴリズムの実現のための言語としてのＣ言語を解説する.また, コンピュータおよびコンピュータ・ネットワークの仕組みやそれに関連する話題も解説する.
【講義の目的】
コンピュータと数学が深い関わりを持っていることを,アルゴリズムという視点から考える.また,コン ピュータおよびネットワークの基礎を理解することにより,それらを正しく使える汎用的知識・能力とコン ピュータに何をさせることが出来るのかを判断・創造する力を身につけることが主要な目的である.また, プログラム言語の仕様を正しく理解することを通じて,アルゴリズムを正しく実装する力を身につけるとと もに,コンピュータの動作原理と言語仕様との関連を理解する.
▼ 講義の目的ではないこと
単に「コンピュータの使い方がわかれば良い」とか,「電子メールの使い方や「ホームページ」の書き方 を知りたい」と言うのは,本講義の目的ではない.また,「特定のアプリケーションの使い方を教えてほし い」なんてのは論外である.
【授業の進め方】
基本的には,１時間目を講義,２時間目をでの実習または演習とする.ただし,１・２時間目両方を講義に あてることや,中途半端な時間から実習または演習を開始することもありうる.実習を行う場合には,学部 生については「情報メディア教育センター理学部サテライトラボ」を利用する.大学院生については,情報 メディアセンター理学部サテライトラボまたは,多元数理科学研究科計算機室のいずれかを利用する.（人 数によってその場で考えることにする.）
▼ 実習について
はじめに電子メールなどの具体的な利用法やUNIXオペレーティングシステムの利用法の実習を行う.こ れらは,その後プログラムを書く場合やレポートを提出する際に必要となる知識である. また,この実習を 通じて,ネットワーク環境に置かれたコンピュータを理解することも目的としている.その後,講義で解説
する各種のアルゴリズムをＣ言語を利用して,実際にアルゴリズムを実装する（プログラムを書く）ことを 実習の内容とする.
実習で利用するアプリケーションに関しては,各機種固有のものではなく,できる限り標準的と思われるも のを利用する.それ以外のものを利用するのは自由だが,そのことに起因するトラブルなどに対しては一切 責任を持たない.各自のオペレーション・ミスなどに起因するトラブルに関しては,各自で責任を持つこと.
▼ 演習について
Ｃ言語の利用法についての実習を１〜２回程度行った後は,授業時間内での演習を行う.演習の内容は,講 義中などに提示したＣのプログラムを「紙の上に書いて,紙の上でトレース」する.課題に対して演習担当 教官のいずれか一人のＯＫが出た後に,各自で実習室に行き,実際のプログラミングを行う.
▼ 出席について
講義に関して,毎回出席をとるが出席は成績には一切関係しない. また,（特に指定しない限り）毎回授 業終了後に電子メールにより「感想・その他」の提出を求める.この「感想・その他」のメールは授業の翌 日午前中までに下に指定するメールアドレス宛に送付すること.「感想・その他」のメールの内容を講義に フィードバックしたい.
就職活動・教育実習等で講義または実習を欠席する場合には,事前にその旨を電子メールで連絡すること.
▼ レポートについて
授業中に課題として出したプログラムに関しては,指定の日時までに電子メールによりレポートとして提 出すること.ただし,特に問題のない限り,個別にレポートのコメントは返送しない.（つまり,コメントが 戻ってこなければ,特に問題がなかったと思って欲しい.）
▼ 授業の進め方
1. 講義は８時４５分から開始する.
学生諸君の中に「朝イチの授業は苦手」と感じている人が多いのは良く理解している.（かく言う私 も,学生時代は朝の授業はサボりまくっていた.）しかし,春学期の授業でもあるので,遅刻しないよう に出席してもらいたい.
2. 講義は約９０分から１２０分.その後は演習.
通常は,講義を９０分〜１２０分程度（きりが良いところまで）行い,１０分〜１５分程度の休憩の後 に,実習または演習を行う.
【勉強の方法】
コンピュータを勉強する方法は,基本的には数学を勉強する方法と全く同じである.すなわち,
• 単純かつ正確な論理を正しく積み上げて,大きなものを作るという考え方.（“Building Block”という）
• アルゴリズムを正しく理解し,筋の良い教科書を参考にしながら,自力でプログラムを書くこと.（こ れを数学で言えば,「概念を正しく理解し,筋の良い教科書を参考にしながら,自力で問題を考えるこ
と」となる.）逆に,正しいプログラムに到達することにより,アルゴリズムとそこに潜む数学をより 深く理解できるはずである.
• 一発で正しいプログラムを書けるようなことはなく,何度も失敗しながら,どこが間違っているのか を考えることが必要である.プログラムを書くことは非常に時間の掛る作業である.「プログラムを 書き始めたら,徹夜も覚悟！」
• プログラムは「動けば良い」という考え方は間違いである.数学だって,「計算できれば良い」なん て考え方は間違っているのと同じである.
【講義内容】
前期の講義でとりあげるテーマは以下の通りである.
• コンピュータとネットワークの基礎知識（コンピュータリテラシ）
• Ｃ言語
• 各種のアルゴリズム
この中で,「コンピュータリテラシ」の部分は,教育実習で４年生の出席が少なくなる６月に講義する1.
▼ 具体的な講義内容
以下の予定で講義を行う.しかし,これは「現在での予定」であって,授業の進度によっては変更があり うる.また,「リテラシ(2, 3)」の部分に関しては,教育実習で欠席する学生が多い２週間を選んで講義する.
第１回(04/17)
【イントロダクション】
• 講義の目的などの説明
【ＵＮＩＸ(1)】
• ＵＮＩＸワークステーションの基本的な 概念
• ログイン・ログアウトの方法
• パスワード
• Window Systemの利用法
• emacsの利用法
【実習】
• Window Systemの利用法
• 電子メールの利用法
• emacsの利用法
第２回(04/24)
【ＵＮＩＸ(2)】
• ＵＮＩＸの基本概念と基本操作 – ファイルシステムとディレクトリ
– シェル
– 基本コマンド
【Ｃ言語(1)】
• Ｃ言語とは？
• 処理系の利用法
• 簡単なプログラム
• 変数と値
【実習】
• UNIXの利用法
• 簡単なプログラムを書く.
第３回(05/08)
【リテラシ(1)】
• コンピュータ内での整数の表現
• コンピュータ内での浮動小数点数の表現
• デジタル回路と加算器
【Ｃ言語(2)】
• 簡単な演算
1本来は,教職につく学生こそリテラシを身につけるべきであるが,リテラシを他の時期にやると,Ｃ言語やアルゴリズムの内容が 佳境に入った頃に４年生が抜けるため,４年生で落ちこぼれる学生が大量に発生するための措置である.この方針に関しては,賛成・
【実習】
• 簡単な演算のあるプログラムを書く.
第４回(05/15)
【Ｃ言語(3)】
• 式
• 演算子と算術変換
• 条件文
【演習】
• 簡単な条件文のあるプログラムを書く.
第５回(05/22)
【アルゴリズム(1)】
• 位取り記数法
【Ｃ言語(4)】
• 繰り返し文
• その他の制御文
【演習】
• 手で基数変換を計算する.
• 繰り返し計算のあるプログラムを書く.
第６回(05/29)
【アルゴリズム(2)】
• ユークリッドの互除法
• その計算量の評価
• ２進互除法
【演習】
• 互除法のプログラムを書く.
第７回(06/05)
【リテラシ(2)】
• コンピュータの歴史
• コンピュータ・ハードウェア
• コンピュータ・ソフトウェア 第８回(06/12)
【リテラシ(3)】
• コンピュータ・ネットワーク
• コンピュータとネットワークに関する社 会的問題
第９回(06/19)
【Ｃ言語(4)】
• 配列
• 文字列(1)
• 関数呼び出し
【アルゴリズム(3)】
• エラトステネスのふるい
【演習】
• ふるいのプログラムを書く 第１０回(06/26)
【Ｃ言語(5)】
• 関数と変数のスコープ
【演習】
• 基数変換のプログラムを書く
• 互除法を関数として実現するプログラム を書く
第１１回(07/03)
【Ｃ言語(6)】
• ポインタ
• 文字列(2)
【演習】
• 文字列操作のプログラムを書く 第１２回(07/10)
【アルゴリズム(4)】
• 浮動小数点演算とその誤差
• 数値的不安定性
• 再帰的関数呼出し
【演習】
• フィボナッチ数列を計算するプログラム を書く
第１３回(07/17)
【アルゴリズム(5)】
• 区間分割法による数値の計算
• ニュートン法による代数方程式の解の値 の計算
• ニュートン法の計算量
【演習】
• √
2を計算するプログラムを書く
【夏休みのレポート問題の説明】
【評価の方法】
夏休み明けを締め切りとしたレポートの内容および９月に行う試験で評価する.（講義の進度によって は試験は行わないことがある.）基本的には,夏休み明け以外のレポートは評価の対象としない.すなわち講 義・実習中に提出を求めたレポートの内容は,受講者の理解度を判断するための材料としてのみ用いる.
レポートはＣ言語によるプログラムと講義で扱った数学的な内容に関するものの２種類がある. Ｃ言語 によるプログラムは以下の指示にしたがって,電子メールで提出する.数学的な内容に関するものは,電子 メールではなく文書で提出する2.これら２種類のレポートと試験結果を総合的に判断して評価を行う.
いかなる場合でも,レポートは自力で作成すること.他人のレポートまたは,教科書・参考書を写した（コ ピーして単純に書き直したものを含む）と考えられるものがあった場合には単位を出さない.（当然,元の レポートを作成した学生にも単位を出さない.）レポート提出の詳細に関しては,夏休み前に別途指示する.
▼ 電子メールによるレポート・感想文の提出方法
電子メールによりレポート（プログラムやLATEXのファイル）を提出する場合には,以下の宛先に提出す ること.
宛先 [email protected] 送付する電子メールに関する条件は以下の通り.
1. 電子メールの発信元は学部生の場合は情報メディア教育センターであること. 大学院生に関しては, 多元数理科学研究科のワークステーションであること.ただし,プライベートな電子メールアドレス を発信元にしてレポート・感想文を提出したい人は,以下の指示にしたがって,プライベートな電子 メールアドレスを事前に知らせること.
プライベートな電子メールアドレスを利用する場合には,事前に上記の電子メールアドレスから,以 下の内容のメールを上記の宛先に送付すること.
• Subjectに“private mail address”,
• 本文にプライベートな電子メールアドレスを記入.
2. 感想文のメールはSubjectを“第Ｘ回講義の感想”とすること.
3. レポート提出時のメールはSubjectを“レポート（問題番号ＸＸ）”とすること.
4. レポートの解答のプログラムが単一ファイルからなる場合には,プログラム・テキストをメールの「添付 ファイル」として送付すること.ただし,「添付ファイル」のファイル名は,user_id_report_xx.c とすること. ここで,user_idは上記のワークステーションのユーザＩＤであり,xxの部分には問 題番号が入る.学部生で電子メールアドレスが「ユーザＩＤ」と異なることがあるので,その場合に も「ユーザＩＤ」を用いること.プログラムが複数ファイルからなる場合は,user_id_report_xx
（上と同じ規則で作った文字列）というサブディレクトリ内にすべてのファイル（Makefileを含む）
を格納して,tar + gzで圧縮したものを添付ファイルとすること. この時,tarの展開時に上記の サブディレクトリが最上位ディレクトリとして展開されるようにtarアーカイブを作成すること.
なお,夏休み明けのレポートの提出に関しては別途指示する.
【その他】
レポート・感想文の提出以外で質問がある場合には,以下の電子メールアドレスに質問を送付すること.
2（ただし大学院生はレポートをLATEXで作成し,そのファイルを「添付ファイル」とした電子メールで提出すること.５月頃に大
または,個別の教官宛にメールを出してもかまわない.
内藤 [email protected] 服部 [email protected] 坂上 [email protected]
講義のWEBページのURLは以下の通り.
http://www.math.nagoya-u.ac.jp/˜naito/lecture/2002_SS/
このページには講義で配布した配布物へのリンクを作成しておく.また,休講などの予定もこのページに記 載する.
【最後に】
こんな風に書くと,非常に厳しい授業のように思うと思います.実際もその通りです.しかし,「コンピュー タを理解したい」とか「数学とコンピュータの関わりを理解したい」と思っている人や,将来コンピュー タを本格的に使う職業につきたいと思っている人は忍耐強く授業や実習に出てください.当然,それなりの
（もしかしたら死ぬほどの）努力が必要です.数学が良くわかった人もそうでなかった人も,この講義は計 算機に関してはゼロからはじめるので,気をとりなおしてがんばりましょう.
【参考文献】
▼ 一般的なコンピュータ・リテラシについて
現状ではほとんど参考文献は存在しない.
1 徳田雄洋,情報ってなんだろう,岩波書店,「ジュニア版コンピュータ科学入門」.
は元々中学生向けに書かれたシリーズの一冊だが,内容は充実している.
▼ ＵＮＩＸについて
2-1 坂本文,たのしいＵＮＩＸ,アスキー出版局, 1990.
2-2 坂本文,続たのしいＵＮＩＸ,アスキー出版局, 1993.
3 B. Kernighan, R. Pike,ＵＮＩＸプログラミング環境,アスキー出版局, 1985.
[2]は１９９０年代に出版されたＵＮＩＸの易しい（？）入門書. [3]は古典的なＵＮＩＸの環境の解説書と しては余りに有名である.
▼ Ｃ言語について
4 B. Kernighan, D. Ritchie,プログラム言語Ｃ,共立出版, 1981.
5 B. Kernighan, D. Ritchie, The C Programing Language (2nd Ed.), Addison-Wesley, 1988.
6 B. Kernighan, D. Ritchie,プログラム言語Ｃ（第２版）,共立出版, 1989.
7 S. Oualline,Ｃ実践プログラミング,オライリー・ジャパン, 1998.
8 A. R. Feuer, The C Puzzle Book, Addison-Wesley, 1999.
9 P. van der Liden,エキスパートＣプログラミング,アスキー出版局, 1996.
[5]が現在Ｃ言語の標準的教科書とされている文献であり, [6]はその日本語訳である.もともとＣ言語は[4]
によって完成されたが,１９８８年,ＡＮＳＩに定められた規格をもとに書き直されたのが[5]である. [4], [5]の差異を調べることはＣ言語の理解には重要である.また,日本語訳[6]はわかりづらい部分があり,そ のためには[5]を参照することも必要かもしれない.なお,元々[6]は「訳書改訂版」といわれるもので,最 初の第２版の訳が余りにひどいはこの世界では有名な話である. [7]は最近出版されたＣ言語の比較的良く 書けている解説書.しかし,初学者には難しい. [8]はＣの奇妙な振る舞いについてパズル風にまとめた本で あるが,内容は一読に値し,そこで使われている種々のテクニックはプログラマには必須のものである. [9]
の帯には「目指せ！！Ｃウィザード」と書かれている.その名の通りの本なのであるが,マトモなＣプログラ マはこの本の内容くらいは知っていて当然.
▼ プログラム全般について
10 B. Kernighan, R. Pike,プログラミング作法,アスキー出版局, 2000.
11 B. Kernighan, P. J. Plauger,プログラム作法,共立出版, 1982.
12 B. Kernighan, P. J. Plauger, Software Tools in Pascal, Addison-Wesley, 1981.
13 A. R. Feuer, N. Gehani, Ada, C, Pascal,工学社, 1981.
14 N. Wirth,アルゴリズム＋データ構造＝プログラム,日本コンピュータ協会, 1979.
15 N. Wirth,アルゴリズムとデータ構造,近代科学社, 1990.
16 A. V. Aho, J. E. Hopcroft, J. D. Ullman,アルゴリズムの設計と解析I, II,サイエンス社, 1977.
17 A. V. Aho, J. E. Hopcroft, J. D. Ullman,データ構造とアルゴリズム,培風館, 1987.
18 D. Kunth, The Art of Computer Programming,サイエンス社, 1981.
19 R. Sedgewick,アルゴリズム,近代科学社, 1996.
20 W. H. Press, et. al., Numerical Recipes in C,技術評論社, 1993.
21 S. McConnel, Code Complete,アスキー出版局, 1994.
22 J. Neivergelt, J.C. Farrar and E.M. Reingold,数学問題へのコンピュータアプローチ,培風館, 1976.
23 E. Post, Real programmers don’t use Pascal,http://www.mit.edu/people/rjbarbel/Humor/Computers/real.programmers.
24 N. Koblitz,数論アルゴリズムと楕円暗号理論入門,シュプリンガー東京, 1997.
25 K. Jensen, N. Wirth, PASCAL（原書第４版）,培風館, 1993.
26 R. S´eroul, Programming for Mathematicians, Springer, 2000.
27 野崎昭弘,アルゴリズムと計算量,共立出版, 1987.
28 伊理正夫,藤野和建,数値計算の常識,共立出版, 1985.
29 森口繁一,数値計算術,共立出版, 1987.
30 杉原正顕,室田一雄,数値計算法の数理,岩波書店, 1994.
[10]から[12]はプログラムとはどう書くべきかを,Ｃ言語の神様であるKernighanが解説した名著. [11]は
Fortran, PL/I, [12]はPascalで記述されている. [10]は[11]の内容を現代流にC, C++, Javaで解説してあ
る. 一読の価値がある. [13]はC, Pascal, Adaという似て非なる言語の比較を行った論文集. その中にある
Kernighanの「私はなぜPascalが嫌いか」とWirthの「プログラム言語Pascalの評価」という２本の論文
は必読. [14], [15]はPascalの作者であるWirthによる名著. [14]に掲載されているプログラムはPascalで 記述されている. [15]はそれをModular2で書き直したものと考えて良い.アルゴリズムとデータ構造の意 味が明快に示されている. [16], [17]は各種の基本アルゴリズムに関する基本文献. [18]は「神様」Kunthに
ので,とてもじゃぁないけど私には原著は読めない.内容は極めて重要な各種のアルゴリズムや概念が極め て難解に解説されている.しかし,本格的にプログラムを書きたい人は必ず読まなくてはならない. [19]は 最近出版されたアルゴリズムの解説書.比較的読みやすい. [20]は数値計算の各種のアルゴリズムとその実 装に関する名著であるが,これを数学の本として読めるようになるのが望ましい. [21]は副題に「完全なプ ログラミングを目指して」と書かれている,プログラミングとはどのように進めるべきかの一つの形を示 した文献.趣旨は[7], [10], [11], [12]などと同一である.ただし,これらに書かれている内容は,著者が考え るプログラミングの進め方の一つのプロトタイプであり,相互には明らかに矛盾した内容が書かれている.
[22]は算術式,組合わせ問題,数の計算などに対するコンピュータでのアプローチの方法を解説したもの.
[23]はプログラムを書くとはどのようなことかを逆説的に述べた文書.もともとはネットワークニュースに 投稿されたもの. [24]は公開鍵暗号理論に対する数学からの入門書として有名である.各種の初等整数論的 アルゴリズムもここで学ぶことが出来る. [25]はPascalというＣに似て非なる言語の解説書である. Pascal とＣの差異を学ぶことは,目的の違う言語の仕様の差異がどのようにあらわれるかを知ることである. [26]
はごく最近出版された数学とプログラミングの関わりを解説したもの.ただし,例に挙げられているプログ
ラムはPascalで記述されている. [27]は各種のアルゴリズムに関して,その計算量評価の議論を平易に解説
したもの. [28], [29]は数値計算を行う際に注意すべきことを極めて易しく解説してある. [30]は数値計算に 関する難解な専門書. [28], [29], [30]は数値計算を勉強する際には必ず目を通すべきである.
おしまい
