PowerPoint

アルゴリズムとデータ構造
講義スライド 1





イントロダクション
基礎的知識
ウォーミングアップ
アルゴリズムの計算量
数値計算
講義はプロジェクタを利用して行います．見にくい学生はスクリー
ンに近い座席に移動してください．
茨城大学工学部知能システム工学科井上康介
E2棟801号室
担当教員自己紹介
 井上康介（いのうえこうすけ）
 身分：講師，居室：E2棟 8階801号室
 専門分野：生物模倣型ロボット（現在は主にヘビ型ロボッ
トを扱っています）
■
2
授業の注意点
 次回以降，出席をとる (代返対策します)
 2回に1回程度宿題を出します．
 指定教科書を参照しながら進めるので，教科書を入手し，
毎回の講義に持ってきてください．
 成績評価については「宿題＋中間＋期末」で行う予定 (比
率は1:1:1の予定)
 授業中・時間外を問わず，質問することを躊躇しないこ
と！よく分からないままドロップアウトしないように．
 ぼーっと聞いていると簡単に脱落する気がするので，ある
程度の気合と集中力を要するかもしれません．
 井上は教えるのが下手糞です．必死で分かろうとしている
人以外も自然に分かってしまうような講義には…ならない
と思います．無理矢理にでも食いつかないと厳しいです．
3
授業の進め方
基本的に，教科書に沿って進める．
数値計算については，軽くふれる程度．
ソートとサーチはきっちりやる．
再帰，データ構造，ツリー，グラフと進む．
グラフィック，パズル・ゲームは扱わない．
実際にコンピュータを使った実習ができるのが理想だが…
時間的にムリなのでやらない．
 講義は PowerPoint を使って行う．つまり，全てノートに
取ることはムリ．スライドは全て，ホームページ上に掲載
する．
 教科書上に重要なポイントをメモすること．
 用語がいろいろと出てくる．中間・期末テストの1問目は,
こういった用語・概念の意味などを問う問題を出題する．
配点多め．ホームページ上に過去問あり．






4
この科目の位置づけ
 プログラミング言語の，いわば「作法」を学ぶのがプログ
ラミング演習 I・II．
 高度なプログラムを作成してコンピュータに複雑な処理を
行わせるのが知的情報処理 I・II およびその演習．
 その間に入るのがこの講義である．
 プログラミング言語の「書き方」だけがわかっていても，
いざ具体的にコンピュータに特定の問題を解かせるとき，
どのような考え方でコードを書けばよいかは分からない．
ex) 最大公約数を求めるプログラムをどう書く？
 コンピュータの内部的な仕組みも踏まえ，どのような戦略
でプログラムの構造を作っていくか，その基礎的な考え方
を訓練するのがこの講義であり，その意味では極めて重要
(配属研究室や就職先企業によっては，マジで重要です)．
5
この科目を履修すべきか？
 本学科の本来の趣旨は，「メカと情報の接合分野を取り扱
うことのできるエンジニアの育成」であり，自動車やエア
コンその他，現在生産される多くの工業製品の設計・生産
において重要な領域（例えば，組み込み系エンジニア）
 したがって，情報についての常識を有しておくことは，上
記の趣旨に即したエンジニアになるためには必須
 …と，いいつつも，どうにもプログラミングに興味がわか
ず，そこを避けて生きていきたい学生もいると思われます
 「プログラミングがどうにもこうにも理解できない」とい
う学生が，この科目で単位を取得するのは厳しい可能性が
ある，ということだけ，お伝えしておきます
 「アルゴリズムとデータ構造の基礎を習得した」とみなし
にくい学生に無理に単位を与えることは，しません
6
C言語の習得について
 知能システム工学科の養成しようとするエンジニア，メカ
と情報の融合分野を扱うエンジニアになろうとするとき，
「プログラムはからっきし」みたいな状態は許されない．
 現時点でプログラミング演習の講義でドロップアウト気味
の学生は，なんとか努力して，習得しなおすべきである．
 本講義では，プログラミング演習は習得していることを前
提として，ソース・コードを参照しながら講義を進める．
 各回で出てくるソース・コードの中に理解できない部分が
一つでも生じている場合，放置してはならない．プログラ
ミング演習の資料を復習する，井上や友達に質問するなど
して，必ずつぶしておくこと．
ガイダンスは以上．質問があればしてください
7
授業で用いる資料
 指定教科書：必携 (講義に必ず持ってきてください)
Ｃ言語によるはじめてのアルゴリズム
入門改訂第3版
加西朝雄著
技術評論社
定価 2,780円＋消費税 = 3,002円
 授業で見せるスライドは，ホームページ上にアップロード
してあります．以下のURLをメモること．
http://biorobot2.ise.ibaraki.ac.jp/inoue/lecture/ad/
8
今日の内容





講義ガイダンス (完了)
「プログラム」に関する基礎的事項
アルゴリズム・データ構造とは何か
授業の目的 (いいプログラマを目指す)
アルゴリズムの評価方法 (一般論)
9
コンピュータに仕事をさせるには？
コンピュータ：「電子計算機」 つまり「計算」をする
計算とは？  今のコンピュータにおいては「データの処理」
例）住所録データから特定の人のデータを探す
例）Mpegムービーを再生する
例）ホームページを表示する
例）入力された数値データ255と105から，最大公約数
＿＿15 を求めて表示する
ではこのような仕事をさせるためにどうすればよいか？
プログラム (手順書) を書いて渡してやる
10
大問題：コンピュータは賢くない！
 仕事：入力した2数の最大公約数を求めよ
 入力：225，105
経験的直感
人間がやる場合…
まずは5だ
5
225
105
3
45
21
15
7
3で割れる
互いに素だ
答）5×3＝15
コンピュータには経験的直感や常識は一切ない！
詳細に指定された手順を正確・高速になぞるだけ
11
どうすればいい？
 人間が常識や直感に頼って行うような作業手順を詳細に
指定した手順書に変換して渡してやる
 手順書とはプログラムであり, 手順書を作るのはプログ
ラマである
ということは…
 手順書に曖昧さ・漠然性があってはならない
 常識や直感を要する指示はできない
 どのデータをどのように処理するか，一切の曖昧さ
を含まないように事細かにきちんと指定してやる
例）「最大公約数を求めろ」という指示を与えると…
→「え…サイダイコウヤクスウって何？」
「なんか数字データが2つ来たけど，どうすれば…？」
12
手順書作成 (プログラミング) の例
 仕事：「最大公約数を求めよ」
 直感には頼れない
 機械的操作の繰り返しなどを考える
ユークリッドの互除法
2整数 m, n (m>n) があるとき， m と n の最大公約数は
m-n と n との最大公約数に等しい
手順
1. m ≠ n の間 2. を繰り返せ．m = n になったら 3. へ
2. m > n なら m := m-n ， m < n なら n := n-m
3. m (=n) が求められる最大公約数
13
実行過程
手順
1. m ≠ n の間 2. を繰り返せ．m = n になったら 3. へ
2. m > n なら m := m-n ， m < n なら n := n-m
3. m (=n) が求められる最大公約数
m
n
24 18
24-18
6 18
18-6
6 12
12-6
6
6
OK!
機械的操作の繰り返しによって
最大公約数が求まった
この機械的な手順をプログラム
に変換すればよい
14
手順書 (プログラム) の例 (p. 38)
#inculude <stdio.h>
プリプロセッサ (コンパイラへの指示)
void main(void) main関数
{
int
ちょっと確認
このプログラム，読めますね？
a, b, m, n; 変数の宣言
printf("Input two integers: "); 入力処理
scanf("%d %d", &a, &b);
}
m = a; n = b; 変数 m, n の初期化
while(m != n) { ループ (m != n の間繰り返す)
if (m > n)
m = m - n; 大きい方の変数を
else
n = n - m; 差の値に置き換える
}
printf("The G.C.D. is %d\n", m); 出力処理
15
プログラム作成に必要なもの
 プログラムでは，作業の仕方を詳細に指定する
 考えなくてはならない項目は 2つ
 まず，データをどのように処理するかを指定する．
 アルゴリズム
 次に，処理すべきデータや処理されたデータをコンピュー
タ上でどのように入出力したり保持したりするかを指定す
る．
 データ構造
16
アルゴリズムとは？
 アルゴリズム：コンピュータに行わせる手順のこと
→ 先程の例では，「ユークリッドの互除法」の手順
 アルゴリズムの実装：プログラミング言語の利用
例) C，C++，Java，VisualBasic, Fortran…
 実装に当たっては，言語特有の制御構造などを使っ
て，手順を言語において定められた文法で書く
制御構造
 順次実行 (基本は上から下へ)
 条件分岐 (if文，switch文など)
 繰り返し (for文，while文など)
17
余談：勉強すべきプログラミング言語
C
 幅広い実用，多くのプログラミング言語への影響大，デバ
イスドライバ開発や組み込み系などハードウェアに近いプ
ログラムにも有用性大 (つまり知能システム工学科的)
 とにかく最初にこれを学ぶべき．研究室の多くはこの
習得を前提としている．
C++
 C言語にオブジェクト指向という概念を組み込んだもの．
企業における大規模プログラムの共同開発で広く実用．
 学ぶ価値は大．多くのエンジニアがメインに使ってい
る．ただし，難易度高めなので，軽い気持ちで手を出さな
い方が良い．Cを十分理解してから．
18
余談：勉強すべきプログラミング言語
Java
 企業で広く利用．多様なプラットフォーム上で動く移植性
の高いプログラムに適している．動作は C や C++ に比
べて遅く，もっさりしている．若干古い．
 知っておく価値はある．C言語理解の後で学ぶべき．
Perl, PHP, Python, Javascript
 Web上で動くウェブアプリケーションの言語．
 商業的にはウェブアプリケーションもそれなりの規模
があることを考えれば，学ぶ価値は 0 ではない．わりと簡
単に理解できる．一方，ネットとかスマホとかのビジネス
に興味ない人は知らなくて良いし，必要が生じてからでも
十分簡単に理解できる．(C言語が一通り分かってれば)
19
余談：勉強すべきプログラミング言語
C#, VisualBasic
 .NETフレームワークというMicrosoftの特殊な環境上で動
くプログラムを開発．なんかXbox系ゲームを作るには必
要らしい．
 学生の時点で修得する価値はほぼない．内定先の企業
が要求してきたときとかに勉強すれば良い．
閑話休題，プログラムの基本要素の2つ目の話に戻る
20
データ構造とは？
 計算とは，「データの処理」であった．
 データをどのように処理するか，その手順であるアルゴリ
ズムとは別に，データをどのように管理するかを規定する
必要がある．
 データ構造：データの管理方法
 データをどのような形式で扱うか (型など)
 データをどのように保存するか (配列？ツリー？)
21
ユークリッドの互除法では？
#inculude <stdio.h>
void main(void)
{
int a, b, m, n;
 この部分がデータ構造に関わる
printf("Input
two integers:
");nを使うよ」と宣言
「int型の4つの変数
a, b, m,
scanf("%d %d", &a, &b);
m = a; n = b;
コンピュータのメモリ空間上に，int型のサイズ
while(m
!= n) {
if (m のメモリ領域が4つ確保され,
> n)
m = m - n;
(4バイト)
変数の
n = n - m;
名前else
(a,b,m,n) との対応付けがなされる．
}
printf("The G.C.D. is %d\n", m);
}
具体的には何が起こっているのか？
22
データの管理
 一般的なコンピュータ
は数ギガバイトの大容
量のメモリ (記憶領域)
を持っている．
 メモリの空間上には位
置を示すアドレスがつ
けられている．
 単位は1バイト．
 アドレスはふつう，16
進数で表記される．
 メモリは様々なプログ
ラムが共有している．
メモリ空間
0x00000000番地
Windows
Visual Studio
Outlook
0x3FFFFFFF番地
23
データの管理
 ユーザプログラム (み
なさんが作るプログ
ラム) は，空いている
領域を使う．
 まず，プログラムを
起動するとプログラ
ム自体がメモリ空間
上の空き領域にロー
ドされる．
 さらに，プログラム
で使うデータの領域
も必要に応じて確保
される．
メモリ空間
0x00000000番地
Windows
Visual Studio
program
Outlook
a
b
0x3FFFFFFF番地
m
n
24
データの管理
 先程の例のプログラムの
場合，int型の変数
a,b,m,nを使う．
 int型は4バイトなので，
メモリ空間上で4バイト
の領域を4つ確保．
 プログラム側では，変数
名 (例えば「a」)と，そ
のデータの格納アドレス
の対応を保持する．
 (よって，プログラマはア
ドレスを直接意識しなく
てよい．)
メモリ空間
0x00000000番地
Windows
Visual Studio
program
4バイト
Outlook
a
b
変数 a をしまった場所
は，0x25A88000番地
だったな．
0x3FFFFFFF番地
m
n
25
大量・複雑なデータの扱い
 大量・複雑なデータに対しては，データの構造化・組織化
が必要となる
 データの構造化：構造体 (，共用体)
 データの組織化：配列，スタック，キュー，ツリー，グラ
フなど
例) 住所録を作りたい場合
個人データ (名前，住所，…) を，inoue_tel,
inoue_addrなどと個別に変数にするか？
→ 井上のデータは構造体 inoue_data にまとめる
井上のデータを inoue_data，佐藤のデータを
sato_data などとするか？
→ 配列などを使ってすっきりと記述
26
ここでC言語の勉強：構造体とは
 本講義では，より実践的な学習を目指して，ソース・コー
ドに即した形でアルゴリズム・データ構造を学ぶ．
 特に，データ構造を学ぶに当たっては，構造体およびポ
インタの知識が必須である．
 そして，一般的に，C言語の習得に当たってこの2つの事
項は最も理解が難しい鬼門と呼ばれる．逆に言えば，これ
らが分かって初めて，C言語が分かったとも言える．
 「プログラミング演習」におけるこれら 2項目の扱いは，
習う時期や詳しさにおいて，本講義には必ずしも対応でき
ていない可能性がある．
 そこで，今回は「構造体」についてこちらの講義で導入を
行う．「ポインタ」においても，初出のタイミングで導入
を行う．
27
構造体とは
 例えば住所録プログラムを作成することを考える．
 扱うべきデータは「個人データ」であり，一人一人の個人
データには，氏名，性別，年齢，住所，電話番号などの要
素データが含まれなくてはならない．
 それぞれの要素的データを個別の変数として扱うのではな
く，一人ごとに関連データをバインダにまとめるようにし
てまとめられると都合がよい．
 そのバインダの働きをするものが，C言語における構造体
である．
28
構造体の使い方
 まず，構造体 (バインダ) の形式を定義しておく．
 person 構造体
struct person {
char name[256];
char tel[64];
char address[256];
};
 中かっこの中に要素的変数を
羅列して宣言する．
 上の宣言により，person という名前の構造体が定義され
る．person 構造体には，文字列 name，文字列 tel，お
よび文字列 address という要素データが含まれることと
なった．
 これらの要素的変数をメンバ変数という．
29
構造体の使い方
 次に，定義されたバインダ形式で個人データの変数を作る
には，以下のようにすればよい．
struct person {
char name[256];
char tel[64];
char address[256];
};
struct person inoue_data;
 person 構造体の変数
inoue_data を宣言
 これにより，例えば井上の住所を inoue_address など
と個別の変数にする必要はなくなって，井上の個人データ
を1つの変数 inoue_data の中にまとめて宣言できる．
30
構造体の使い方
struct person {
char name[256];
char tel[64];
char address[256];
};
struct person inoue_data;
 メモリ空間上では，構造体は1まとま
りのブロックとして作成される．
メモリ空間上では
inoue_data
name
tel
address
31
構造体のメンバの参照
struct person {
char name[256];
char tel[64];
char address[256];
};
ドット (.) をつける
struct person inoue_data;
 構造体のメンバへの参照は以下のように行う．
printf(“TEL of Inoue is %s\n, inoue_data.tel);
 井上の電話番号を表示
scanf(“%s”, inoue_data.address);
 井上の住所をユーザがキーボード入力
(ここに “&” がいらない理由は？)
32
データの組織化
 先程定義した person構造体の変数をたくさん使って住所
録プログラムを作ることを考える．
struct person
arai, inoue, sato1, sato2, wada;
こう宣言すれば，新井さん，井上さん，佐藤さん2名，
和田さんの5人のデータの変数が定義できるが…
でも住所録とは，不特定多数の人を登録するもの…
人数も名前も事前には分からない！
 そこで，データをうまく組織化することを考える．
組織化の方法：配列，リスト，ツリー，グラフ…
33
配列による組織化
メモリ空間上では
#include <stdio.h>
struct person { 構造体定義
char name[256];
char tel[64];
char address[256];
};
data[0]
void main(void) {
struct person
data[2]
name
tel
address
data[1]
data[4]; 変数の宣言
“Kousuke Inoue”
sprintf(data[2].name,
data[3]
変数への書込み
"%s",
"Kousuke Inoue");
}
34
文字列とポインタ
struct person {
char name[256];
char tel[64];
char address[256];
};
inoue_data
name
tel
struct person inoue_data;
address
 実は文字列の実体は構造体の外部にあ
り，構造体には配列の先頭アドレス
(ポインタ) が記入される．
(つまり inoue_data.name はポインタ)
 理解できない学生は，プログラミング
演習を必死で復習すること．
‘K’
‘o’
‘u’
‘s’
35
ツリーによる組織化
 階層的なデータにはツリー構造 (木構造) が適する
例) 茨城大学の組織のデータを表現するには？
茨城大学
人文学部
情報工学科
理学部
知能システム工学科
工学部
メディア通信工学科
これを構造体として，教員リスト，
学生数などのデータを格納
36
授業の目的
 プログラム＝アルゴリズム＋データ構造
 特定の問題をコンピュータに処理させるには，手順 (アル
ゴリズム) とデータの扱い方 (データ構造) を細かく指定
してやる必要がある → プログラミング
 同じ作業をするにも，いろんなプログラムがあり得る．
 プログラムを上手に書く能力を身につけるには？
 典型的なアルゴリズム・データ構造を学ぶ
 アルゴリズムの良し悪しの評価方法を学ぶ
これにより，問題に応じて適切なアルゴリズム・データ
構造を選択し，上手なプログラムを作成する能力を養う
 これがこの授業の目的
37
プログラムの評価 (一般論)
信頼性：精度の良い正しい結果を出す (当たり前)
効率性：計算回数が少なく，処理スピードが速い
一般性：特定の状況だけでなく，多様な状況に対応
拡張性：仕様変更に対して簡単に修正可能
(cf. デス・マーチ)
 可読性：他の人にも読みやすくして，メンテナンスを＿＿
＿＿容易にする
 移植性：他のOSなどにも移植が容易にできる




これらの評価基準において良質なプログラムを書く人が
良いプログラマである．
この授業では，特に効率性について詳細な評価方法を学ぶ
38
質問対応の時間
 ガイダンスということで，今日はここまで．
 本講義では，授業終了後に質問対応の時間をとります．
また，その時間では都合が悪いという場合は，メール等で
時間を決めて，その時間に質問に来てください．
 メアド：
(メモを)
 どの講義においても，「分からないまま放置」という戦略
は最低であるということを認識してください．
39
第1章ウォーミングアップ…の前に
 必要な基礎知識を導入しておく．
 データ型
 オーバーフロー
 プリプロセッサ
40
データ型とは (復習)
種別
符号ビット長表現
範囲
整数
あり 8
(signed) char
-128～+127
16
(signed) short
-32768～+32767
32
(signed) long
-2147483648～+2147483647
unsigned char
0～255
16
unsigned short
0～65535
32
unsigned long
0～4294967295
float
約10-38～10+38 (10進数7桁)
double
約10-306～10+306 (10進数16桁)
なし 8
浮動小あり 32
数点数
64
41
数データの実体 (整数)
 以下のようにビットを利用して表現している
unsigned short型各ビットに0か1を入れ2進数を表現
16ビット＝2バイト
15 14
3210
例）0000000000101001
→ 25+23+20 = 41
範囲：0 ～ 216-1 ＝ 65535まで
(signed) short型符号ビットを除いた15ビット分を
16ビット＝2バイト
正負両側に割り振る
範囲：-215 ＝ -32768 から
215-1 ＝ 32767 まで
符号ビット (0：正，1：負)
42
数データの実体 (整数)
 符号付き整数型での負の数でのビットの扱い
例えば (signed) char型の場合…
127
126
…
1
0
-1
-2
…
-127
-128
01111111
01111110
…
00000001
00000000
11111111
11111110
…
10000001
10000000
つまり，符号ビット以外の7
桁での大小関係が保たれてい
る
43
数データの実体 (浮動小数点数)
 浮動小数点数のビット表現は以下の通り
±1.[仮数部]×2[指数部]
※ 0は全てのビットが0の場合とする
4バイト
8ビット
23ビット
float型
………
指数部
符号ビット
double型
11ビット
仮数部
8バイト
52ビット
………
指数部
符号ビット
仮数部
44
int 型とは何か？
 実際には，int 型として宣言した変数は，CPU のアーキ
テクチャやコンパイラに依存した別の整数型として扱われ
る (それぞれの環境において最も自然な整数型)
 通常は long 型として扱われるが，マイコンなどでは
short 型で扱われることも多い (教科書では short 型)
 通常，計算のスピード的には int 型を素直に使うのが速
いことが多い (が，通常は問題になるほどではない)．
 一方で「どの環境でも確実に動くプログラムを作る」こと
を考慮するのであれば，int 型を使うべきではないかも
しれない．
45
オーバーフローとは何か
 既に述べたように，数のデータにおいては，型に応じて扱
いうる数値の範囲がある
 例えば char 型では，扱いうるのは -128 から +127 まで
の数である
 では，例えば以下のようなことをすると何が起こる？
char i;
やってみましょう
for (i = 0; i < 500; i++)
printf("i = %d\n", i);
本来の意図： i を 0 から 1 ずつ増加させて 499 まで表示
だが，char 型は 127 までしか記述できない！
46
オーバーフローとは何か
 結果：iは127まで増加した直後，i++
によって-128となった → 永遠に 500
に到達しないので，無限ループ
 同様に，例えば i=20*20; としてみる
と i=-112 という結果になる
 プログラマとしては，当然ながら，
オーバーフローを起こすようなプログ
ラムを書いてはならない
 オーバーフローを防ぐためにアルゴリ
ズムを変えることも時には必要となる
 「オーバーフロー」という用語自体に
は，もっと広い意味がある．
i
i
i
…
i
i
i
…
i
i
i
i
…
= 0
= 1
= 2
= 127
= -128
= -127
=
=
=
=
-1
0
1
2
47
プリプロセッサとは
 C言語プログラミングにおいては，C言語で書かれたソー
スコードをコンパイラによってコンパイルし，できたオブ
ジェクトファイル，ライブラリファイルをリンクして実行
ファイルを作成する (分割コンパイル)
コンパイルの前に前処理を行う
ソースファイル
プリプロセッシング (前処理)
コンパイル
オブジェクトファイル
オブジェクトファイル
オブジェクトファイル
リンク
ライブラリ
実行ファイル
48
プリプロセッサとは
 コンパイルに先立って行われる前処理に関してコンパイラ
に指示を行う機能をプリプロセッサという
 ソースコードの特定の位置に指定されたファイルの内容を
挿入する，ソースコード内の特定の文字列を別の文字列に
置換するなど，いくつかの機能がある
 ファイルの取り込み
#include <stdio.h>
このプリプロセッサ指示は, 「ソースコードのこの位置に
stdio.h というファイルの内容を取り込め」という意味
を持つ
※ 指示文の行末にはセミコロン「；」はつけない
49
プリプロセッサとは
 文字列の置換・マクロ定義
#define NUM 12
このプリプロセッサ指示以降，ソースコード中の NUM
という文字列は「12」という文字列に変換される
#define MULT2(X) ((X)*(X))
defineプリプロセッサは引数をとることができる．
上のプリプロセッサ指示以降，例えば MULT2(12) と
書くと，((12)*(12)) に変換される
MULT2(X) X*X
X*X と定義してしま
※ 例えば #define MULT2(X)
うと，MULT2(a+b)*2 が a+b*a+b*2 と解釈されて
しまう → かっこが重要！(教科書 p.58など)
50
プリプロセッサの例
#include <stdio.h> ← ヘッダファイルの取り込み
#define N 10 ← この指示以降，「N」という文字は
「10」として解釈される
void main(void)
{
int a[N]; ← この宣言で確保される配列の
サイズは10となる
a[3] = 100;
}
51
1-1 漸化式
 例題1 nCr の計算
計算途中でのオーバーフローを防ぐために，計算方法 (ア
ルゴリズム) 自体を変更した例
 練習問題1 Hornerの方法
多項式の計算の効率性 (乗算・加算の回数の少なさ) のた
めに漸化式に書き換えてから計算した例
※ 係数の列を「係数の入った配列へのポインタ」として
関数に渡している点に注意！
※ 関数 fn()の引数において係数列へのポインタは
double a[] と書かれているが，これは double *a
と同じ意味．
52
1-3 順位付け
 例題3：素朴なやり口
個別の得点が全体で何位かを求める問題：他の点数を 1 つずつ調べ，
対象の点数より高得点の学生が何人いるかをカウントして，最後に 1
を足せばよい．
 人数が n 人の時，一人の順位を調べるのに n 回調べる手間がかか
り，全員について一人ひとりの順位を調べると総合で n2 回の手間
 練習問題 3-1：改良版
完全な発想の転換により効率化
取りうる点数ごとに，(その点数＋1) 点をとった人間の順位を記録す
る手順を踏んでおけば，人数と取りうる点数の数との和の手間ですむ
(2次ではなく1次のオーダ)
 練習問題 3-2 は飛ばす
53
1-6 ユークリッドの互除法
 既に説明した方法は以下の通り
m
n
36
8
36-8
28
8
28-8
20
8
20-8
12
8
12-8
4
8
4
4
36から繰り返し8を引きま
くるため，手間がかかる
どうせ4回も8を引くなら，
一気に引いてしまう
8-4
36%8 という演算で，
一気に4までもっていける
54
ユークリッドの互除法の効率化
 剰余の計算を使うとこうなる
計算の繰り返し回数が減少
do {
k = m % n;
m = n; n = k;
} while (k != 0);
効率性の高いアルゴリズム
m
n
k
m
n
k
36
8
4
8
36
8
8
4
0
36
8
4
4
0
8
4
0
4
0
55
1-7 エラトステネスのふるい
 …の前に，ソースコード上の注意がいくつかある
(次ページ以降)
 まず問題にするのは，教科書 p.41 のコード Rei7.c の中
の以下のコード
while (printf("data? "), scanf("%d",&n)!=EOF){
カンマ記号の意味
scanf() の返り値
56
式の値
 プログラミングでは何らかの演算を行う命令文をすべて
「式」と呼び，すべての式は値を伴う．
 代入文 x = 100：代入される 100 が式の値．
 条件式 a > b：真偽が式の値．C言語だと偽は 0，真は
「0以外の数」と決まっており，通常は真の場合 1．
 関数 printf(“a”)：これも一つの「式」であり，値
は関数の返値．
 if 文や while 文，for 文の中で行う条件判定は「式の値
が 0 か 0 以外か」を見ている．
57
カンマ演算子
 式をカンマ区切りでつなげる演算子
 a = 1; b = 2;  a = 1, b = 2;
 式の値としては，カンマ演算子でつながる式の右端の値が
採用される．
 メリット：複数の操作を一つの「式」として書ける．
 while文の条件判定部など，式を 1つしか書けない縛り
があるときに便利．
 while(printf(“data? “),scanf(“%d”,&n)!=EOF)
の場合，関数 scanf() が EOF を返すかどうかで判定
 for (i=0,j=0; i>=j; i++,j--) { … } とかも可能．
58
関数 scanf() の返値
 関数 scanf() は，以下の値を返す
 成功した場合：入力したデータの個数
 失敗した場合： EOF (end of file)
 EOF は stdio.h において定義された定数である：
 #define EOF (-1)
 具体的には…
 教科書のコードでは，起動すると “data?” という表示を
出した状態で入力待ち状態になる (カーソルが点滅)．こ
のとき数を入力すると，それが素数かどうかに応じて「素
数」とか「素数でない」と表示され，続いて再び “data?”
と表示されて入力待ちになる．
 「もういいよ」と思ったら…
59
関数 scanf() の返値
 scanf() が入力待ち状態の時に，Windows なら「Ctrl
キー＋ Z キー」，UNIX や Linux なら「Ctrl キー＋ D
キー」を同時に押すことで，scanf() に対して「もうこ
れ以上データはありませんよ」という信号を送ることがで
きる．
 このとき scanf() は，それを呼び出した関数に対して
EOF を返り値として返す (入力処理の失敗の報告)．
 while (scanf(……) != EOF) というコードは「Ctrl + Z
(あるいは D)」が入力されるまで入力を繰り返す」という
処理の定石
 ちなみに一般的に「Ctrl ＋ C」はプログラムの強制終了．
60
1-7 エラトステネスのふるい

61
インクリメントの順序
 練習問題7-1のソースコード Dr7_1 において，
prime[m++]=n;
というコードがある (m はそれまでに得られた素数の個
数，n は新しく見つかった素数)．ここで…
prime[m++]=n;
同義
prime[m]=n; m++;
prime[++m]=n;
同義
m++; prime[m]=n;
 つまり，インクリメント (1を足す操作) の順序が ++ の
位置によって異なる．
 なお，この例のように，見つけたものを順々に配列に格納
するような処理において，このやり方は簡潔で便利．
62
1-7 エラトステネスのふるい
 練習問題7-1は，まず最初に思いつくような素朴な方法
1
 しかし，これでは計算回数が n n 回かかってしまう
2
 練習問題7-2：エラトステネスのふるい
小さい素数から順にその倍数を「ふるい」から一括で落と
してしまうという根本的な発想の転換により，計算回数を
低減
※ 後述する「計算量のオーダ」では O(n log log n) となる (詳細は省略)
63
理解すべきこと
 以上，「ウォーミングアップ」としていくつかの事例に対
するアルゴリズム・データ構造を見てきた
 理解すべきことは以下の2点
 扱う問題ごとに，様々なアルゴリズムやデータ構造があり
得る
 それらの中で，プログラマは「良いプログラム」を目指
し，良いアルゴリズム・良いデータ構造を使わなくてはな
らない．そのための工夫の余地はいろいろある
 アルゴリズム論では，中でも効率性について重視する
効率をどう測るのか？：計算量 (computational complexity)
(同じ仕事をするにも，手順を n2 回繰り返す方法より n 回ですむ方がよい)
64
アルゴリズムの計算量
 繰り返し述べてきたとおり，アルゴリズム論ではアルゴリ
ズムの効率性，即ちどれだけ少ない繰り返し回数の手順で
問題を解けるかに着目する．
 これを定量的に扱ったものが計算量 (computational
complexity) である．
 問題のサイズ n が増加するとき，繰り返し回数 (これは処
理時間に比例する) がどのように増加するかを問題とす
る．すなわち，n2 に比例して2次関数的に増加するのか，
あるいは n logn に比例して増加するのか．
 細かい数字は気にせず，「何次式か」という，いわば桁の
ようなもの，オーダ (order) を評価する．
65
計算量評価の実例
 第3回課題の例で計算量のオーダを評価してみよう
 問題の「サイズ」とは，この例では点の数 n である．
 点が n 個あるとき，解答例のアルゴリズムでは，三角形
の面積を計算する回数は nC3 回であった．
1 3 1 2
1
n - n + n
n C 3 = n (n - 1)(n - 2) / 6 =
6
2
3
 「オーダ」を評価するとは，この式の「桁」のようなもの
を評価することである．
 実際の実行時間は CPU，OSなどによって変化しうるの
で，細かい数字を見ることは無意味である．
 それよりは，「何次式か？」を見る．
66
計算量評価の実例
 オーダを求めるには，以下の通りにする．
 最大次数以下の項は無視する．なぜなら，n が大きくなる
につれて，それらの項目は誤差の範囲となるから．
 定数の係数は無視する．定数倍程度の差異は CPU，OSの
違いにより生じるから．
1 3 1 2
1
n - n + n
6
2
3
O(n 3 )
ビッグ・オー表記
「n3 のオーダである」
→ n が非常に大きくなると
実用的時間では計算できない
67
最大次数に着目せよ！
 問題サイズ n に対して計算量が 20n + n n + 5n ln n とな
るアルゴリズムがあるとして，計算量のオーダはどの程度
になるか？
 n が大きくなっていくとき，第1項と第2項，第3項のいず
れが急激に大きくなるかによって決まる．
 グラフを見てみると…
68
最大次数に着目せよ！
(ここでの log は自然対数)
※ log の底は，底変換しても定数倍
になるので，オーダには無関係
69
最大次数に着目せよ！
70
最大次数に着目せよ！
71
最大次数に着目せよ！
x*sqrt(x) は急激に増加
それ以外の項は比率としては
小さくなっていく
72
最大次数に着目せよ！
 n log n よりも n n の方が，大きい n に対して増加率が大
きい．最大次数以外は誤差の範囲に落ちる．
 すなわち，20n + n n + 5n ln n に対して，そのオーダは
O(n n ) と評価しなくてはならないことが分かる．
全ての項のうち，どの項が最も急激に増加
するかを見極めよ！
73
要点
 計算の手間の大きさを定量的に評価するために，繰り返し
回数を問題サイズ n の関数として求める
 細かい数字を気にしても仕方がない  求まった n の関数
が，どういう種類の関数に分類できるかを問題とする
 多項式であればそれが何次式であるか，多項式でなければ
それがどういう関数か (指数関数 (ex) か，対数関数 (logn)
か，対数関数に1次式をかけたもの (nlogn) か，など) に
基づいて関数の形式を分類する
 代表的な例：
 バブル・ソート：O(n2)
 クイック・ソート：O(nlogn)
74
第2章：数値計算
 コンピュータ：電子計算機
 元来は数値計算を行う目的で開発された
例) 砲弾の着弾地点を予測する，戦術の決定を科学的・数
学的に行う (OR：オペレーションズリサーチ)
 コンピュータにおける計算は，常に近似的であるから，完
全に正確な計算はできず，常に誤差が存在する
 誤差には以下のものが存在する：
■ 丸め誤差 (桁数制限のために四捨五入する)
■ 打ち切り誤差 (有限回数で計算を打ち切る)
■ 桁落ち (近い値同士での引き算で生じる)
教科書 p.48-49
75
2-2 数値積分
 解析的に積分ができない場合，コンピュータで逐次的に足
し込むことで積分値を求める．
本来の積分値は
この面積
76
2-2 数値積分
 解析的に積分ができない場合，コンピュータで逐次的に足
し込むことで積分値を求める．
台形則
線分
台形則では，区間
ごとの台形の面積
を足していく
77
2-2 数値積分
 解析的に積分ができない場合，コンピュータで逐次的に足
し込むことで積分値を求める．
シンプソン則
放物線
シンプソン則では
区間の両端と中点
を通る放物線で近
似する
78
2-2 数値積分
 ソースコード上のちょっとした注意点
double 型への scanf()では，%f ではなく%lf とする．
printf()による表示では %f でOK．わけ分かんない．
 教科書の例では
y
y =
4 - x2
2
0 から 2 まで積分すると，
真の積分値は
p = 3.14159…
のはず
0
2 x
 結構大きな誤差
79
台形則と中点則の違い
 台形則では，凸関数や凹関数に対して，常に関数の下側あ
るいは上側を通るため，誤差が累積する．
積分：
グレー領域の
面積を加算
赤い領域は
誤差として蓄積
80
2-3 テイラー展開
打ち切り誤差について
 本来の意味は「繰り返し計算を途中で打ち切ることにより
計算結果と真の値の間に生じる差」のこと．
 教科書では
 打ち切り誤差：もう1回計算したときの増分
 相対打ち切り誤差：もう1回計算したときの増加率
としているが，本来の語義とは若干異なることに注意．
81
2-4 非線形方程式の解法
2分法について
 教科書では打ち切り条件を high - low / low < EPS として
いるが，方程式の解がちょうど x = 0 だった場合，分母・
分子がともに 0 に漸近するため，収束しない．
 本来は high - low の値，すなわち解の探索範囲の幅が
十分小さくなったときを打ち切り条件とする．
このとき，得られる解の最大誤差はこの幅となる．
Newton 法について
 一般的には Newton-Raphson 法と呼ばれる．
 縛りとして，導関数 f ¢(x ) が求まっている必要があるが，
実際上はこれは必ずしも成り立たない．
 この場合も打ち切り条件は x n - x n - 1 < EPS とすべき．
82
数値計算
 授業では扱わないが，教科書にある以下の例も重要：
 2-5 補間
 2-8 連立(一次)方程式の解法
 2-10 最小2乗法
 教科書にないが，微分方程式の数値解法も重要である．
(例：坪井研の研究では水などの流体の運動をシミュレー
トするなどを行うが，あらかじめ分かっているのは部分部
分の動き方の法則性と初期状態だけであり，運動法則は微
分方程式として与えられる)
 講義「数値シミュレーション」で学ぶ．
83

Download Report