アルゴリズムとデータ構造
講義スライド 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
授業で用いる資料
 指定教科書:必携 (講義に必ず持ってきてください)
C言語によるはじめてのアルゴリズム
入門 改訂第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
ダウンロード

第12回:木構造