計算機科学概論講義メモ
2011 年前期 佐々政孝 （注）これは講義のメモである．これ以外の資料を示したり，配付することも多い． この講義メモには，分かりにくいところや誤りも多いと思われる．遠慮なく指摘してい た だ き た い ． 講 義 中 で も よ い し ， 気 づ い た と き に 電 子 メ イ ル ア ド レ ス [email protected] に送ってもらってもありがたい．佐々政孝の居室は，西 8W 号 館 9 階 906 号室． ［講義と実習］ 講義は，講義メモの内容と Java の本の解説と最終回に科学技術者倫理，を行う． 実習は，初回に情報科学科の計算機環境の使い方を説明し，以後は Java の本にほぼ同 期してプログラミング実習を行う． 成績評価は，講義の試験 50%，実習レポート 50%． ［参考書］ 概論● Biermann, A. W. and Ramm, D.: Great Ideas in Computer Science with JAVA, MIT Press, 2002.（旧版の和訳）Alan W. Biermann 著，和田英一監訳：やさしいコンピュ ータ科学，アスキー出版局，1993. 4800 円. ● 徳田雄洋：はじめて出会うコンピュータ科学，1 巻− 8 巻，岩波書店． ● 徳田雄洋：ジュニア版コンピュータ科学入門，1 巻− 5 巻，岩波書店．各 1500 円. （以上 2 冊は計算機科学のいくつかの話題を青少年向けにわかりやすく説明してい る．） ● 川合慧（編）：情報-東京大学教養学部テキスト，東京大学出版会，2006. 1900 円 （本学 1 年次の「コンピュータサイエンス入門」の発展形とも言えるが，復習を兼ねて 読むと新しい知見が得られる．）
● Goldschlager, L. and Lister, A.: Computer Science - A Modern Introduction, second edition, Prentice-Hall, 1988.（和訳）ゴールドシュレーガー，Ｌ．，リスタ ー，Ａ．著，武市正人，他訳：計算機科学入門第 2 版，近代科学社，2000．（全体の概 論．プログラム言語は特定しない．やや古いので購入は勧めない．）
● 徳田雄洋：デジタル社会はなぜ生きにくいか，岩波新書．700 円＋税． Java 言語
● （教科書）千葉滋：やさしい Java プログラミング，アスキー，2004．3600 円. ● ジョゼフ・オニール著，トップスタジオ訳：独習 Java，第 4 版，翔泳社，2008．3800 円. アルゴリズムとデータ構造 「アルゴリズムとデータ構造」の授業も参照． 下記 4 つは Java によるアルゴリズムとデータ構造の本．
● Sedgewick, R.: Algorithms in Java, 3rd ed., Parts 1-4, Addison Wesley, ISBN 0-201-36120-5, 2003.
● 近藤嘉雪：Java プログラマのためのアルゴリズムとデータ構造，ソフトバンクパブ リシング，2004．2835 円.
● クリフォード・シェーファー著，久野禎子，久野靖訳：JAVA によるデータ構造とア ルゴリズム解析入門，ピアソン・エデュケーション，2000．5040 円．
● Robert Lafore 著，岩谷宏訳：Java で学ぶアルゴリズムとデータ構造，ソフトバン クパブリシング，1999．5040 円． Java でなくてよければ，たくさんよい本があるが，3 種類だけあげる． ● セジウィック，Ｒ．著，野下浩平ほか訳：アルゴリズム C，1 巻− 3 巻，近代科学社 （上の英語の本の旧版の C 言語版の和訳．同じシリーズで Pascal，C++版もある．例題 の図が多くわかりやすい．） ● T. コルメン，R. リベスト，C. シュタイン，C. ライザーゾン著，浅野哲夫ほか訳： 数学的基礎とデータ構造 (アルゴリズムイントロダクション)，アルゴリズムの設計と 解析手法 (アルゴリズムイントロダクション)，近代科学社，2007．（T. Cormen et al.: Introduction to Algorithms, Third edition, MIT Press, 2009. の旧版の訳） ● 石畑清：アルゴリズムとデータ構造，岩波書店，1989． 3806 円. 関数型言語 ● サスマン，エイブルソンほか（著）和田英一（訳）：計算機プログラムの構造と解 釈，第2版，ピアソン．4830円． 計算 ● 渡辺治，米崎直樹：計算論入門，日本評論社，1997．2000 円. ● 渡辺治：計算可能性・計算の複雑さ入門，近代科学社，1992．2330 円. タッチタイピング ● 木村泉：ワープロ徹底操縦法，第 4 章（岩波新書）岩波書店． （1 年次にタッチタイピングは習得したと期待するが，もし出来ない場合はここで頑張 ろう．英字は，1 日 1 時間の練習で 1 週間で，キーボードを見ないで打てるようになる．）
オンライン・ドキュメント 情報科学科の WWW ホームページ http://www.is.titech.ac.jp/ の「講義と演習」をクリックすると，学科の講義，実習関係のいろいろな資料が見られ る． 計算機科学概論の WWW ページは次にある． http://www.is.titech.ac.jp/~sassa/keisankikagaku-gairon11/index.html 講義の例題プログラムは次にある． porto:~sassa/keisankigairon-from-daidai/の下の koukai-java/や koukai-c-scheme-prolog-porto/などいくつか
1 計算機とは 計算機それ自身は，自動車やテレビとは違って，原理的には多目的機械である．使用 目的に合せたプログラムを与えることで様々な働きをさせることができる． 一方，一旦そうしたプログラムが与えられると，計算機は「決まりきった仕事」を高 速に行うもの，と考えてよい．（もちろん，いわゆる人工知能のような分野に計算機を 適用するとき，その内容は，決まりきったものとは言えないが，その基本は上のように 述べてよかろう）． 仕事をどのように行うかを明確に記述したもので，実行が有限時間で終るものをアル ゴリズム (algorithm)という．アルゴリズムという言葉の由来は，9 世紀前半に活躍し たアラビア人の「姓」である al-Khuwarizmi であると書いている辞書もある． 処理（プロセス） ｜ アルゴリズム ｜ ステップの例 --- セーターを編む ｜ 編み模様 ｜ 表編みする；裏編みする 模型飛行機を作る ｜ 組立て方の説明 ｜ 板 A を支柱 B に接着する ケーキを燒く ｜ 料理法，レシピ ｜ ３個の卵を泡立てる 洋服を作る ｜ 型紙 ｜ わきを縫う ベートーベンのソナタを弾く ｜ 楽譜 ｜ 図 1 日常生活におけるアルゴリズムの例 （ゴールドシュレーガー，リスターより） ここで，計算機の歴史を簡単に述べておこう． Pascal の計算器 Charles Babbage の解析エンジン 機械的歯車を用いる．織機に使う穴あきパンチカードがプログラム ENIAC ペンシルベニア大学．1946 年．真空管 18,000 本 プログラムはプラグボードとスイッチ
John von Neumann の提案
プログラム内蔵方式．メモリにプログラムを入れる．1945 年 EDSAC Cambridge 大学の Wilkes, M.V. 1949 年 パラメトロン計算機（日本） 東京大学の高橋秀俊，後藤英一．1958 年 現在の計算機は，電気を用い，ディジタルで，プログラム内蔵方式であることが特徴
と言えよう． 1.1 ハードウェア ハードウェア (hardware) とは，英語では金物のことで，計算機システムを組み立て ている物理的な装置をいう．ハードウェアはソフトウェアに対照する概念である． ハードウェアという言葉は，電子回路の素子のレベルのものも含むが，プログラムを する場合には，それよりもっと上のレベルから考えればよい． 計算機の構成 上のように，計算機を機能レベルで見たものを計算機アーキテクチャ (computer architecture)という．アーキテクチャとは，もともと建築物の意味である． 計算機アーキテクチャのあらまし インターネット 端末 ＼ ／ 人 ⇔ プリンタ − ネットワーク − 他の計算機 ↑ ＼ 二次記憶装置 ↓ 人 ⇔ 入出力装置 ⇔ 中央処理装置 ⇔ 記憶装置 (キーボード， (CPU) (メモリ, ディスプレイ) 二次記憶装置) （実線が基本的な構成）
中央処理装置 (Central Processing Unit, CPU)：
計算機の中心となる，基本的な演算を実行する部分． CPU は，入力装置からデータなどを入力し，二次記憶装置からメモリに 持ってきたプログラムとデータを用いて，四則演算その他の演算を行う． 最近は複数の CPU や 1 つの CPU にコアを 2 つ以上持つものも多い． 結果のデータは二次記憶あるいは出力装置を通して外界へ出力する． 記憶装置（メモリ，memory）： プログラム（ アルゴリズム）やデータ（演算の対象，結果）を保存す る装置． 主記憶 (main memory)（たんにメモリともいう）と 二次記憶装置，補助記憶装置 (secondary memory)（ハード・ディスク（磁 気ディスク），CD-ROM (650 M Byte 位)，DVD など） がある．
入出力装置： データを入出力する装置． 入力 (input) ：キーボード，マウス，マイク，カメラ，測定器よりの 入力 出力 (output)：ディスプレイ，プリンタ，スピーカ マイク，測定器，プリンタなどを周辺装置 (peripheral device)という こともある． その他，広い意味では，他の計算機，ネットワークがつながるので， ネットワーク装置を 4 つめの構成要素とすることもある． プリンタ，二次記憶装置はネットワークにつながることも多い． CPU と記憶装置（と入出力装置の一部）までの部分を計算機ということも多い． 西 7 号館の計算機システムは，ファイルサーバ装置（計算機），管理用計算機と多数 の MacPro（これも計算機，ファイルを共有している）からなる． 計算機の大きさ スーパーコンピュータ，超並列計算機，ベクトル計算機 （盛衰が激しい，名前の区別はあいまい）
［例］米国のIBMの Blue Gene，本学のスーパーコンピューティング・グリ ッドTSUBAME2.0（理論値ピーク性能2.4 P Flops (毎秒2400兆回の浮動小数 点演算を実行，Pについては後述，世界で４位)，NECの地球シミュレーター （理論演算性能 40 T FLOPS）
メインフレーム（汎用計算機，大型計算機）（すたれつつある） ワークステーション［例］Sun Microsystems 社の Sun Fire
PC クラスタ［例］NEC の Express5800（CPU 680 個，センターにあった） パーソナルコンピュータ
［例］Intel 64 やその互換機，Apple の Macintosh
マイクロコンピュータ［例］家電製品，自動車に組込み，ARM，SH-4 携帯端末［例］iPad 傾向として，ダウンサイジング (down sizing)：同じ能力が小さい計算機で実現され ていくこと． ちなみに，数字の 10 進桁数を表わす接頭語は，SI（国際単位系）では ミリ m=10-3, マイクロμ=10-6, ナノ n=10-9, ピコ p=10-12, キロ k=103, メガ M=106, ギガ G=109, テラ T=1012, ペタ P=1015 である．ただし，計算機のメモリ容量については，k = 210 = 1024, M = 220, G = 230, ... を表すこともあり，たとえばメモリが 1GB というときはこちらである．
速度
計算機の速度は，たとえば，ワークステーションでは，100 億命令／秒のオーダであ る．スーパーコンピュータで浮動小数点演算を行う場合は 1000 兆浮動小数点演算命令 ／秒＝1 P FLOPS (Peta Floating Operations Per Second) のオーダである．（オーダ (order)，というときは 10 倍とか 10 分の 1 くらいまでを含む！）
（M=Mega=106=100 万，G=Giga=109=10 億，T=Tera=1012=1 兆，P=Peta=1015=1000 兆，ただ
し計算機のメモリでは M＝220＝1,048,576 等とすることもある） 記憶容量 主記憶（メモリ）：多くのパソコンでは，数 GB のオーダ(B は Byte，1 GB は 10 億英 文字) 二次記憶（ふつうはディスク）：情報科学科の教育用サーバでは数 TB のオーダ コンピュータ・ネットワーク
ふつうは転送速度が 100 M bps (bit per second) 1 G (1000 M) bps のものをいう． LAN (Local Area Network)：数 100 メートルくらいまでの近距離で，一つの組織で運 営されているネットワーク．
ワ ー ク ス テ ー シ ョ ン の 間 で は 光 フ ァ イ バ FDDI (Fiber Distributed Digital Interface)，イーサネット (Ethernet) ケーブルがよく使われる． インターネット (Internet)：ネットワークのネットワークで世界的 1.2 ソフトウェア ソフトウェア (software) とは，ハードウェアに対照して作られた言葉で，柔物（や わもの）と訳す人もいる．これは，ハードウェアの上で，好みのシステムをプログラム により実現したものである． 現在の計算機は，日本語や英語など自然言語でプログラムを書いても受けつけない． そこで，自然言語に比べると文法がより厳密に定めてある人工言語を用いる． プログラムはプログラム言語（JIS の用語），プログラミング言語 (programming language)で書く．
プログラム言語には，機械語 (machine language)，アセンブリ言語 (assembly language)，高水準（プログラミング）言語 (high-level (programming) language)な どがある．
機械語
機械語とは，機械が直接理解できる言葉である． ［例］機械語のプログラム
1000000100001010 レジスタ 1 に 10 番地の内容を入れる 1000001000001011 レジスタ 2 に 11 番地の内容を入れる 0100001100010010 レジスタ 1 とレジスタ 2 を足してレジスタ 3 に入れる 1010001100001100 レジスタ 3 の内容を 12 番地にしまう 機械語は計算機ファミリ（同類のこと）ごとに異なっている． 機械語はもともと 2 進数である．2 進数または 16 進数で書くことになる．そこで， 人間が書くのはきわめてやっかいである． アセンブリ言語 アセンブリ言語は，機械語を人間にわかりやすく書けるようにしたものである． 機械語やアセンブリ言語のそれぞれのステップを命令 (instruction)という． アセンブリ言語の各命令は，機械語とほぼ 1 対 1 に対応している． ［例］アセンブリ言語のプログラム load %r1,10 レジスタ 1 に 10 番地の内容を入れる load %r2,11 レジスタ 2 に 11 番地の内容を入れる add %r3,%r1,%r2 レジスタ 1 とレジスタ 2 を足してレジスタ 3 に入れる store %r3,12 レジスタ 3 の内容を 12 番地にしまう アセンブリ言語も計算機ファミリごとに異なっている． 高水準（プログラミング）言語 高水準言語は，計算機の種類によらず共通で，人間にわかりやすい言語である． ［例］Java（この講義で主に用いる），C や C++や C#（システム記述），Fortran（お もに数値計算），Scheme や Lisp や ML や Haskell（記号処理，関数型言語），Prolog （論理型言語），Pascal（教育用），Basic（パソコン），Cobol（事務計算）... ［例］上のアセンブリ言語プログラムは，Java では次の 1 行で済む． k = i + j ; （注意）Java での「=」は比較ではなく，右辺の値を左辺の変数にしまう「代入」を表 す． 高水準言語では，プログラムのそれぞれのステップを文 (statement)という． 高水準言語の実行方式 機械語やアセンブリ言語は，計算機によって異なる．高水準言語は計算機によって異 ならないので，計算機に依存しないプログラムが書ける（ことになっている）． あるプログラミング言語で記述されたプログラムを実行するシステムをプログラミン グ言語処理系あるいは言語処理系とかたんに処理系という．高水準言語の言語処理系に は，コンパイラ方式とインタプリタ方式がある．
コンパイラ コンパイラ(compiler)または変換系(translator)はプログラムを一括して機械語に変 換する． コンパイル 高水準言語のプログラム − − − − → 機械語のプログラム （ソースプログラム） コンパイラ （目的プログラム） 上のような変換をコンパイル (compilation)，翻訳・変換 (translation)などという． （場合によっては，機械語の代りに中間言語というものに変換するものもある） 左側をソース・プログラム (source program) ，右側を目的プログラム (object program) という． 翻訳そのものも計算機で行える．つまりコンパイラも計算機上で動く． C，C++，Fortran などでは上の方式を用いる． ただし Java コンパイラは，Java のプログラムを中間言語のプログラムにコンパイル する（後述）． プログラミングと実行の流れ プログラミングと実行の流れは，コンパイラ方式では次のようになる． アルゴリズム ↓ （プログラミング） ↓ 高水準言語によるプログラム ↓ （コンパイル） ↓ 機械語によるプログラム（実行時には主記憶に置かれる） ↓ 入力データ→（CPU で実行）→出力データ 実際には，1 回限りでなく，前へ立ち戻って繰り返すことも多い． インタプリタ コンパイラに対照されるものとしてインタプリタ (interpreter)というものがある． これは，プログラムを解釈しながら実行する．この方式は同時通訳に喩えられ，対話性 にすぐれているのが特徴である．たとえば，Scheme はインタプリタ方式が基礎になっ
ている． インタプリタ方式では，プログラムを打ち込むとすぐ実行され，プログラミング以降 の流れは次のようになる． ↓ プログラム ↓ （インタプリタで実行） ［例］Scheme DrScheme の場合 > (* 1 2 3 4 5 6 7 8 9 10) 3628800 コンパイラ・インタプリタ 実は，Java のふつうの処理系はコンパイラとインタプリタを組み合わせたものであ る． コンパイル 解釈実行 Java のプログラム − − − − → 中間言語プログラム − − − − − → (ソースプログラム) コンパイラ (クラスファイル) インタプリタ 1.3 ソフトウェアとハードウェアの階層 ソフトウェアには，次のような種類がある． (1) ユーザプログラムや応用ソフトウェア (application software，アプリケーショ ン)： ユーザプログラム：利用者（ユーザ，user ともいう）が書くプログラム 応用ソフトウェア：出来合いのプログラム，たとえば ワープロソフト，清書システム（例：LaTeX2e），作図ソフト（例：tgif）， 表計算（例：Excel），数式処理，グラフ表示，...
経理，建築設計，CAD (computer aided design)，... (2) システムソフトウェア (system software)：
コンパイラ ［例］javac（Java コンパイラ） インタプリタ［例］java（Java インタプリタ） エディタ ［例］emacs 電子メイルソフト［例］Apple Mail 言語開発環境（コンパイラ＋インタプリタ＋エディタ等）［例］Eclipse （(1)と(2)の境界はあいまい）
(3) オペレーティングシステム (OS, operating system)
応用ソフトウェアやシステムソフトウェアを支える基礎となるソフトウェア． ［例］UNIX，Windows, MacOS ●プリンタなどの入出力装置などを管理し，ユーザに，ハードウェア特有の事項 を意識させない． ●ユーザのコマンドやマウスの操作にしたがって，コンパイラなどを呼び出す． ●複数のユーザが同時に計算機を利用できるように見せかけたり，一人で複数の 仕事を同時に行えるような機能を与える． ●ネットワークに接続し，ネットワークを介してつながったプリンタの利用やフ ァイル共有，インターネット上の WWW ブラウジングができるようにする． ソフトウェアの最近の傾向として，視覚的にわかりやすい表示，良い操作性をもたせ たグラフィカル・ユーザ・インタフェイス (graphical user interface, GUI) の充実 があげられる． 上に述べたことから，ソフトウェアとハードウェアの階層を考えることができる： ユーザプログラム，応用ソフトウェア（例：ワープロソフト） システムソフトウェア（例：コンパイラ） オペレーティングシステム（OS）（例：UNIX, MacOS） ハードウェア（例：CPU，記憶装置，入出力装置） ユーザから見れば，ユーザプログラム，応用ソフトウェア，システムソフトウェアが 動けばよいのだから，その実現法にはいろいろあり，ハードウェアとソフトウェアの境 界は流動的である． ［例］組み込み用計算機などで 乗算器のある計算機 → 乗算をハードウェアで実現 乗算器のない計算機 → 乗算をソフトウェアで実現
（整数）乗算器のある機械を使えば，（整数）乗算は速いが機械の値段が高い．乗算 器のない機械を使えば，その逆となる．こういうのをコスト (経費, cost) と性能 (performance) とのトレードオフ (trade-off)という． 一般に，異なった機種の計算機でも利用できることを互換性 (compatibility) とい う．これには，ハードウェアの互換性，ソフトウェアの互換性がある．上の乗算の例は ソフトウェアの互換性である．高水準言語は互換性が高い． 1.4 計算機は何ができるか 定型的な仕事では人間より速い． 非定型的な仕事では，まだまだ．
人工知能 (artificial intelligence, AI) ゲーム
バックギャモンとオセロは人間の世界チャンピオン並み．オセロは人間に 6 勝 0 敗（1997 年）．
チェス：IBM の Deep Blue (RS/6000 ワークステーション 32 を含んだ並列 計算機 IBM SP2．各ワークステーションに 16 個の特別チップ)が世界チ ャンピオン Garry Kasparov を 2 勝 1 敗 3 引分けでくだした(1997 年 5 月)． 将棋：2010 年 10 月 11 日に，コンピュータ将棋「あから 2010」が清水市代 女流王将に勝利した．「阿伽羅」とは，華厳経にある 10 の 224 乗を表す 単位で，将棋の探索空間（10 の 220 乗）に近いことから命名された． 詰め将棋：十数手なら数十秒 数百秒．数十手詰までは十分強い． 囲碁：アマチュア三段くらいか．（チェスが一段落したので，これからは 将棋と囲碁だと言われている） 自然言語の処理，機械翻訳 音声認識 チューリング・テスト：相手が人間か計算機かを見破れるか その他，最近の需要は， マルチメディア (multi-media) グラフィクス，音，静止画，動画など複数の媒体を扱う． 人工現実感 (virtual reality) 遍在計算(ubiquitous computing)，モーバイル，ウェアラブル・コンピューティ ング 1.5 議論 信頼性 計 算 機 が ど れ く ら い 正 し く ， 思 っ た と お り 動 く か を （ 広 い 意 味 で の ） 信 頼 性
(reliability)という．信頼性にはいろいろな要素がからんでくる． ハードウェアの誤り：電気的な欠陥，配線や IC 設計の欠陥 ［例］Intel Pentium プロセサの浮動小数点除算命令の虫．1994 年． ソフトウェアの誤り：虫，バグ (bug) という．この原因には，人間のプログラミ ング誤り，プログラム言語の不完全さ，システムの不完全さがある． 人間のプログラミング誤り：考え違い，入力ミス．初期段階では 1％ 数％ 人間の誤りは，本来は計算機のせいではないが，実際には大きな要因である． 製品プログラムの誤り（人間の誤りの一つ）：あまねく存在し，実際に使われてい るものでも 0.2 10 個／千行，くらいはある． プログラミング言語の不完全さ：たとえば次の［例 9］． ［例 1］銀行のオンライン端末で振込をしていたら突然画面が消えた． ［例 2］パソコンのファイルが全部消えた．コンピュータウィルス？
［例 3］昔，金星ロケットMarinerが迷子になった［Myers, G.J.: Software Reliability- Principles and Practices, Wiley, 1976.（邦訳）近代科学社 1977］．プログラムは Fortranで書かれていた．これは，3 の場所まで 3 回繰り返すつもりのプログラム． DO 3 I=1,3 このコンマがピリオドになっていた Fortran では空白を無視するので，これは次を意味することになる． DO3I=1.3 （DO3I という変数に 1.3 をしまう）
［例 4］1996 年に European Space Agency の Ariane 5 ロケットが軌道を大きくはずれ たため，破壊処理された．この事故の原因は，Ada 言語で書かれたプログラムで 64 ビ ット浮動小数点数を 16 ビット整数に変換するときに起こったオーバフローの処理の誤 りと言われる [IEEE Software May/June 1997, pp. 15-16]．
（ちなみに 1986 年のスペースシャトル「チャレンジャー号」の爆発事故は，オーリン グというゴム部品に起因する．）
［例 5］清書プログラム [Naur, P: Comm. ACM, Vol. 21, No.9, 1978]
Naur が正しいという証明をした約 80 行のプログラムに 6 箇所の誤りがあとで発見さ れた［有沢誠：bit 1981 年 9 月号］． ［例 6］西暦 2000 年問題：西暦の 2 桁表示 ［例 7］みずほ銀行のオンラインシステムに大規模障害が発生（2002 年 4 月） この類の障害は多数ある． ［例 8］東京証券取引所のシステムダウンと誤発注 (2005 年 12 月) ［例 9］危ういプログラム− 2 倍 2 倍にしていくプログラム > cat PowerOfTwo.java public class PowerOfTwo {
int j = 1;
for (int i = 0; i <= 40; i++) {
System.out.println("2**" + i + "¥t= " + j); j = j * 2; } } } > javac PowerOfTwo.java > java PowerOfTwo 2**0 = 1 2**1 = 2 2**2 = 4 2**3 = 8 2**4 = 16 2**5 = 32 2**6 = 64 2**7 = 128 2**8 = 256 2**9 = 512 2**10 = 1024 2**11 = 2048 2**12 = 4096 2**13 = 8192 2**14 = 16384 2**15 = 32768 2**16 = 65536 2**17 = 131072 2**18 = 262144 2**19 = 524288 2**20 = 1048576 2**21 = 2097152 2**22 = 4194304 2**23 = 8388608 2**24 = 16777216 2**25 = 33554432 2**26 = 67108864 2**27 = 134217728 2**28 = 268435456 2**29 = 536870912 2**30 = 1073741824 2**31 = -2147483648 2**32 = 0 2**33 = 0 2**34 = 0 2**35 = 0 2**36 = 0 2**37 = 0 2**38 = 0
2**39 = 0 2**40 = 0 （2 31から後は正しくないが，何のエラーメッセージも出ない．Java での exception（例 外）も起こらない．） ［例 10］浮動小数点数についての同様な例．0.01 を 100 回足す > cat SumOf01.java
public class SumOf01 {
public static void main(String args[]) { float s = 0.0f;
for (int i = 1; i <= 100; i++) { s = s + 0.01f; } System.out.println("s= " + s); } } > javac SumOf01.java > java SumOf01 s= 0.99999934 なぜ，このようなおかしな値や誤差がでるのだろう？ 計算機でのメモリの 1 語は限られているので，表せる数の範囲に限りがある．そこで， 整数と浮動小数点数（実数）という 2 種類の表現法（後述）を用いることが多い． 整数は，たとえば-2147483648 2147483647 の間の数を正しく表せるが，整数の乗算 については，あふれのチェックをしないものが多い．するとこれを越えた値は化ける （［例 9］）． （単精度）浮動小数点数（実数）は，たとえば有効数字が（10 進で）7 桁位しか表せ ないので，近似値になることが多い（［例 10］）．（倍精度のときは有効数字が 16 桁 位） 浮動小数点数の数値演算については，講義ではあまり扱えないが，誤差が生じること に注意してほしい．（参考．数値解析の講義や，数値計算法についての種々の本） このように， ●理想化された計算機 と ●時代の産物である現在の計算機 の間には，大きなギャップがある． 1.6 アルゴリズム，計算の複雑さ，計算可能性 アルゴリズムの設計 (design)
「アルゴリズム」とは，解を求める具体的な手順のことである．アルゴリズムが決め られなければプログラムが作れない！ 未知の問題をどうやってアルゴリズム化するかを考えよう． たとえば，2 数の最大公約数を求めたり，数字の書いてあるカードの束を数字の順に 並べ替えたいとする．やりたいことを人に説明するのはやさしいが，機械的に行う手順 を明確にするのはけっこう難しい． 世の中には，もっと複雑な問題がたくさんあり，一般に，アルゴリズムを設計するの は，難しく，知的な作業であり，創造力が必要である． 計算の複雑さ たとえば，数字の書いてあるカードの束を数字の順に並べ替えるには，いろいろなア ルゴリズムがある（「アルゴリズムとデータ構造」の授業やアルゴリズム・アニメーシ ョンなどを参照）．それぞれのアルゴリズムで，必要とする計算時間や記憶容量は異な る． こ れ ら の ， 必 要 と す る 計 算 時 間 や 記 憶 容 量 の こ と を 計 算 の 複 雑 さ と か 計 算 量 (complexity) という．詳しく分けると，時間複雑さ(time complexity)と空間複雑さで ある． 入力の量（大きさ）を n とすると， 入力の量に比例する n 入力の量の 2 乗に比例する n2 入力の量の 3 乗に比例する n3 入力の量に指数関数的に比例する 2n（en） といったようになる．
0
5000
10000
15000
20000
25000
30000
0
10
20
30
n
n^2
n^3
2^n
計算の正当性 アルゴリズムが正しいことをアルゴリズムの正当性 (correctness)という．アルゴリ ズムが正しくなければいけないのは，当然のことである．しかし，正当性を議論するの は，なかなか難しい．正当性を証明したり議論したりするには，かなり数学的，論理的 な思考力を要する（後述）． 計算可能性 何でも計算できる，あるいは，「時間をかければ計算機でいずれは答えを出せる」， と思っている人がいるかもしれない．しかし計算できない問題もある．たとえば，任意 のプログラムと入力が与えられたとき，そのプログラムがその入力に対して停止するか どうかを判定することは一般にはできない（後述）．何が計算でき，何が計算できない かを計算可能性 (computability)という． 1.7 実習および計算機使用の際の注意（詳しくは実習の先生にお聞きください） (1) 現在では多くの計算機が IP 接続されているので，1 つの計算機に入ってから，外 国を含む多くの計算機に入ることが可能である．しかし UNIX はセキュリティが弱く， security hole とよばれる箇所がたくさんある．パスワード破りのプログラムもあり， クラッカーがその気になれば比較的簡単にどの計算機にもログインできるのが実情で ある． そこで，当然のことであるが，他人に自分の名前でログインさせたり，パスワードを 教えてはいけない．もし本学の計算機を経由してコンピュータ犯罪が起こったとすれば， 世界的な非難を浴び，現在のような便利な計算機環境を維持することは不可能になろう． パスワードには，数字のみ，生年月日，辞書にある単語，固有名詞，それらの逆つづ り，を用いないこと．パスワードはときどき変更すること． (2) 計算機におけるファイルの permission（読み書き許可）についての注意： 教育用計算機でふつうにファイルを作ったとき，それを他人が読める設定になってい る可能性がある． そこで，ディレクトリ Documents/workspace の下は他人が読めないように設定し， 本授業に限らず，課題のプログラムやレポートはこのディレクトリの下に作るようにし てほしい． 他人に対して read permission を与えるファイルを作ること自体は，一般にはかまわ ないが，他人がそのファイルを読んだときに起こる事態について十分理解しておく必要 がある． 一方，社会倫理に反する意図を持って，他人のファイルを読むこと，コピーすること， 無断でプログラムやレポート等を流用することは厳につつしまなければならない． (3) 電子メイルはもちろん学外に届く．WWW ホームページも学外に公開される．ネット ワークの倫理，法律を順守してほしい．（参考．1 年次「コンピュータリテラシ」のテ キスト）
