- 情報コース
- ラジオ授業
- 鈴木一史先生（放送大学教授）
- 難易度 ★★★☆☆
- おすすめ度 ★★☆☆☆
主にC言語を使って、ソートやリストなど基本的なアルゴリズムを学ぶ。アルゴリズム入門というよりは、C言語入門と言った方がよい科目。授業の後半は印刷教材の各章末の演習問題の解説にあてられるため、印刷教材とweb補助教材（プログラムソースが長いため別枠）が手元にそろっていることが前提の科目で、ラジオ単体で聞くのは非常に苦しい。ラジオでは無理のある科目のためおすすめ度は低め。C言語を真面目に学びたい人向け。今の時代、pythonなど近代的なプログラミング言語を使った方がよい気がするが、pythonだと基本的なアルゴリズムは1行で書けてしまうので、あえてC言語にしたのかもしれない。
第1回
プログラムとは何か簡単に述べた後、C言語入門になった。私はC言語知ってるから、言葉を聞いても想像できないこともないけど、初めての人はラジオだと何もわからんと思う。コメントはこう書きますとか、sscanfの引数にアンパサンドがついてることに注意しましょうとか言われても初学者はわかるんだろうか。#includeも意味教えないでいきなりでてきてるし。印刷教材と共に聞くことが前提のようだけど、印刷教材があればラジオ授業いらんのでは。。
印刷教材の演習問題のヒントのコーナーがある。これ聞いてると、C言語ってunsigned longみたいな変数型とか、%lfが何を表してるかとか、とか些末な規則一つ一つが全部わかってないと、何にもできないんだなあと思った。
一応全部聞くけど、単体で聞くにはかなーり厳しい授業だと感じました。テレビにしてくれ。
第2回
条件分岐について。C言語のif文とswitch文、あとgoto文だけで、45分の講義を使った。やはり、細かい規則が多くそれで時間がかかる。しょうがない。
講義を聴いているのは年配のおじさんが多いという前提というところがびっくりした。みんな行番号付きのBASICに慣れてるでしょーって。
あとは三項演算子については、使うか使わないかが宗教的議論になるという話が面白かった。私は使う派です。
後1/3は第1回と同じく、演習問題の解答例とヒント。
第3回
forループ、whileループ、do while文の話。
主に、1000回printfを書くよりも、forループ一発の方が楽じゃんという話です。
do whileって使ったことないし、どういうケースで使えばいいかわからん。forでええやん。世界は複雑じゃない方がいいって形而上学でもやったよ。
GO言語はfor文しかないらしい。道理だなあ。それもそのはず、for-while-do whileは相互変換できるってさ。
web補助教材って面倒だな、分厚くてもいいからテキストに含んでほしい。お金の問題ならしょうがないけど。
演習問題もfor三重ループとか複雑になってきたなあ。
第4回
ループの応用でモンテカルロ法による円周率の演算。いきなり難しくなった。
ざっくり説明すると、正方形と内接円を用意して、乱数で正方形内に適当に点を打つ。点の位置が円の中にあるかないかで分けて、点の数の比と正方形・内接円の面積比（1：π/4）を比較する。すると円周率が出る。これをプログラムでやれということ。
テキストないけど、試しに聞いた知識だけでJavaScriptでやってみる。
//円の中、外のカウント
inTheCircle = 0;
outOfTheCircle = 0;
//繰り返す回数
n = 100000
for(i=0; i<n; i++)
{
//x,y に0～1の適当な数を代入
x = Math.random();
y = Math.random();
//ここでは(0,0)(0,1)(1,1)(1,0)の正方形と、(0,1)(1,0)の扇形で考える
//扇形の中にあればinTheCircleをインクリメント
//そうでなければoutOfTheCircleをインクリメント
if(x**2 + y**2 <= 1.0) inTheCircle++;
else outOfTheCircle++;
}
//面積は正方形が1、扇形がπ/4(円の1/4)。これとn : inTheCircleが等しい
pi = inTheCircle * 4.0 / n;
document.write(pi);
↑がこのプログラムの実行結果です。だいたい3.14になるので、まあまあの精度かな？ちなみに、nを10億にすると結構な時間がかかるらしい。その代わり、精度も高い。
あとはビッグオーの話。nlognだと全然増えないねーってことが分かった。nの2乗だと途端に遅くなる。ちなみに↑のプログラムのオーダーはnのはず。
第5回
関数について。関数便利ですよね。繰り返しが減るし、何度も使われると洗練されてバグも出にくくなるし。
再帰はパフォーマンスが減るってのはよく知らんかったな。確かにスタックに積んでったり崩したりするとコストがかかるかも。どういう場合に使うべきで、どういう場合に使わないべきかは、もう少し詳しく知りたいな。
C言語は参照渡しがないという話。たしかにポインタは値渡しだから、全部値渡しでできるね。あと昔は引数が31個までしか使えなかったらしい。私の会社の開発環境もそうかもしれないから気を付けよう。
演習問題に、インクリメントしているように見えるのに画面出力は数が減っていくという引っ掛け問題があるらしい。「これは試験にも出しやすい問題です」って2回も言ってたから試験に出るんだろう。試験難しそうね。
第6回
配列の話。これから3回配列らしい。そんなに話すことあるのかなって思ったけど多次元配列、ジャグ配列・スライス（この2つは言及するだけ）とかいろいろ配列ってやることあるよね。
ヒープとスタックの話が出てきたけど、これ私も実務で悩んだことがあって、古い環境でローカル変数で大きな配列を確保すると、原因不明のエラーが出るんですよ。これはnewするようにしたら解消したんで、スタックじゃなくてヒープに確保することが重要。実際、スタックって容量どのくらいなんだろうね。あと、当時の私はどうやって問題を解決したんだろう。謎。
文字列処理の話も、昔のC言語然としていて、不便な関数ばっか。pythonならこれ数文字で書けるのに。。！ってのいっぱいあるよね。
第7回
配列その2。線形探索と二分探索、計算量について。原理のところは計算の科学と手引きとまるかぶりで、新しいことはあまりないんだけど、一つ疑問が。二分探索のための整列済み配列って、整列するのにオーダーnのコストが必要なんだから、いくら二分探索がlognだからって、整列にコストかかっちゃって線形探索と変わらないんじゃ？整列済み配列をコストを低く作るための仕組みがあるのかな。ノード型の配列にすれば毎回二分探索してリンクを繋ぎ変えるだけでいいからコスト低いってこと？あとはDBMSみたいにインデックスを抜き出してそこだけソートするっていう風にするのかな。
構造体を並べ替えるのも一緒だよね。一部のメンバのみ比較するのなら、インデックスを取り出してソートしてるのと一緒。ただ、並べ替えのデータ量が非常に大きいから、やっぱノード的にやるしかない気がする。
第8回
配列その3。スタックとキューの話と、ライフゲームの話。スタックとキューは実装としてはあまり難しいことをやっているわけではないのだけど、有限な配列を使ってどうやって実装するのか、印刷教材のコードを見てみたい。
今回のメインはライフゲームの話。ライフゲームとは、二次元空間の点の集合に一定のルールを与えて、点が消えたり生まれたりする話。中学の時、ライフゲームの本を読んで感銘を受けたことを覚えている。
そうそうこれこれ。数学的な簡単な規則から、生命や宇宙が作れてしまうっていう話だったのでスケールが大きく感動したんだよね。
今ではライフゲームもいっぱい動画が出ている。
THE RECURSIVE COSMOS: Conway's Game of Life - PART 1 - YouTube
一度JavaScriptあたりで実装してみたいなー
第9回
ファイルについて。fopenとかfprintfとかは知ってるのでいいとして、後半戦ではNetbpmという知らない画像の形式を扱う話になった。
P3 # The P3 means colors are in ASCII, then 3 columns and 2 rows, then 255 for max color, then RGB triplets 3 2 255 255 0 0 0 255 0 0 0 255 255 255 0 255 255 255 0 0 0
PBM形式ではこんな風にフルカラーの画像を表すらしい。無圧縮のバイナリよりデータ量でかいじゃん。たしかにどんな環境でも、フルカラー画像を表すことはできるが、これは実用的のはデータ量でかすぎで難しいんじゃ。。
どうせならjpgとかpngとかを扱ってほしかった気持ちもある。
第10回
ソートについて。バブルソート、選択ソート、挿入ソートの解説をC言語で行っているのだけれどいかんせん音声ではなにもわからなかった。悲しい。印刷教材ちゃんと読もう。
第11回
クイックソートと基数ソート。相変わらず音声なんでなんもわからん。これで終わりでは悲しいので、JavaScriptでクイックソートとバブルソートを実装して、速度比較するコードを作った。コード全文は以下。
//クイックソート
function qsort(arr, left, right){
//範囲の真ん中の値をpivotに設定する
var pivot = arr[Math.floor((left + right)/2)];
//端っこをカーソルに入れる
var cur_l = left;
var cur_r = right;
//pivotより小さい値を左側へ、大きい値を右側へ分割する
while(true){
//左側はpivotより小さければOKなのでカーソルを一つ右へ移動する
while(arr[cur_l]<pivot){
cur_l++;
}
//右側はpivotより大きければOKなので、カーソルを一つ左へ移動する
while(pivot<arr[cur_r]){
cur_r--;
}
//カーソルがぶつかったら、そこでグループ分けの処理を止める。
if(cur_r <= cur_l){
break;
}
//カーソルがぶつかっていない場合、pivotを挟んだ大小が間違っているので、交換する
//交換後にカーソルは進める
var tmp =arr[cur_l];
arr[cur_l] =arr[cur_r];
arr[cur_r] =tmp;
cur_l++;
cur_r--;
}
//左側に分割できるデータがある場合、再帰的に処理を繰り返す。
if(left < cur_l-1){
qsort(arr, left, cur_l-1);
}
//右側に分割できるデータがある場合、再帰的に処理を繰り返す。
if(cur_r+1 < right){
qsort(arr, cur_r+1, right);
}
}
//バブルソート
function bsort(arr)
{
for(var i=0; i<arr.length; i++)
{
for(var j=i; j<arr.length; j++)
{
if(arr[j] < arr[i])
{
var tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
}
}
//ランダムな配列生成
function RandomArr(num)
{
//値を順に入れる
var arr = new Array(num);
for(var i=0; i<num; i++)
{
arr[i] = i+1;
}
//Fisher-Yates shuffle
var a = num;
while (a)
{
var j = Math.floor( Math.random() * a );
var t = arr[--a];
arr[a] = arr[j];
arr[j] = t;
}
return arr;
}
//配列の個数
var ARR_NUM = 10000;
document.write(ARR_NUM + "個の配列のソート ");
//バブルソートを行い、時間計測
var arr = RandomArr(ARR_NUM);
var start = Date.now();
bsort(arr);
var end = Date.now();
var end = Date.now();
document.write("バブルソート：" + (end-start) + "ms ");
//クイックソートを行い、時間計測
arr = RandomArr(ARR_NUM);
start = Date.now();
qsort(arr, 0, ARR_NUM-1);
end = Date.now();
document.write("クイックソート：" + (end-start) + "ms ");
実行結果
↓↓↓↓
↑↑↑↑
私の環境（デスクトップPC Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz 3.41 GHz）だと、
10000個の配列のソート バブルソート：200ms クイックソート：3ms
となった。あなたの環境ではどう表示されますか。
第12回
メモリの話。ヒープ、スタックのほかに、グローバル変数、ローカル変数など、それぞれメモリ上の位置が決まっているということを学んだ。C#なんかでもメモリレイアウトを調べる方法はあるのかな。
情報学の話じゃないけど、mallocの読み方とか、「宗教的な話」って言い方を良くするけど、宗教も、それなりに根拠をもってみんなやってるはずなんで、ちょっと宗教に失礼ではないか。
第13回
連結リスト。おそらくCArrayとかstd::vector、C#のListのような可変配列を実現するためのアルゴリズムと思われるが、印刷教材なしではコードが頭に入ってこず全く不明。
C++みたいにオブジェクトをnewしまくれば結構簡単に実装できそう。あとはいかにパフォーマンスを上げるかが問題になると思う。シーケンシャルアクセスしかできないから、例えば配列の5000番目をくださいって言った時に大変。メモリ管理を完璧にしておかないと、破綻しそう。値による探索が簡単なのもこの形式の利点か。
第14回
連結リストの応用、スタックとキューの実装や双方向連結リスト、環状連結リストなどについて。スタック、キューは連結リスト使わないと、配列に制限ができちゃってどうしようもないね。固定長で大きなバッファを取るわけにもいかんし。環状連結リストってのはどういう場面で使うのかが気になる。理論としてはわかるが、実践として使う状況あるのか？双方向連結リストは、普通に思いついて自分で実装してたことがある。一般的な思想は、知っておくに越したことはないね。
第15回
最終回はscratchについて。ゲストの松下先生、山本先生の共著の親子向けscratchの本がある。買おうかな。
scratchは、なんといってもシンタックスエラーが出ないことが最高に良い所。アルゴリズムに集中できる。うちも上の子（4歳）がscratchを喜んでやっているので、とっつきやすいのもよい。かといって本格的なプログラミングができないわけではない。ちょっと慣れが必要だが、バブルソートだってできるらしい（！）。鈴木先生も2時間くらいでだいたい操作に慣れたそうだ。
“放送大学全科目感想 009 アルゴリズムとプログラミング(’20)” への1件の返信