アルゴリズムとデータ構造1

アルゴリズムとデータ構造1
2009年6月18日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/index.html
プログラムとアルゴリズム
• 二分木と言った非線形なデータ構造と，こ
れを扱うアルゴリズム，特に再帰的なアル
ゴリズムについて学ぶ
• つぎにハッシュやソートと言った良く利用さ
れるデータ構造やアルゴリズムの概観を
得る．
Ｅｕｃｌｉｄの互除法（２ページ 1.1）
1. ｍをｎで割って、余りをｒとする。
2. ｒ＝０であれば、アルゴリズムは終了する。
このとき、ｎが最大公約数である。
3. ｍ←ｎとする（ｎの値をｍに代入する）。
次にｎ←ｒとして１に戻る。
ここでは、次の処理が使われている。
•除算
•０との比較・分岐処理
•変数への代入
•繰り返し（ループ）
/* C言語によるgcdの例1 */
int gcd(int m, int n)
{
int
r;
1: r = m % n;
if (r == 0) goto 2;
m = n;
n = r;
goto 1;
2: return n;
}
/* C言語によるgcdの例2 */
int gcd(int m, int n)
{
int
r;
while((r = m % n) != 0){
m = n;
n = r;
}
return n;
}
/* Java とほとんど同じ */
プログラムは、連接（文の並び順による評価）・条
件分岐（たとえばif文）・繰り返し（例えばwhile文）
だけで構成できるとされている。そもそも、gotoを
使わないで書いたほうがわかりやすいことも多い。
そのような背景で、Javaのようにgotoを使えないプ
ログラミング言語がある。
スタックフレーム
; アセンブリ言語によるgcd関数の例
.text
gcd:
mov.w
@(2,sp),r1
mov.w
@(4,sp),r0
1:
divxu.b r0l,r1
xor.b
r2h,r2h
mov.b
r1h,r2l
beq
2f
mov.w
r0,r1
mov.w
r2,r0
bra
1b
2:
rts
.end
ｓｐ＋４
; 引数 m
; 引数 n
;
;
;
;
;
;
引数ｎ
ｓｐ＋２
ｓｐ
引数ｍ
戻りアドレス
r = m % n
if(r == 0) goto 2
m = n
n = r
goto 1
return n
簡単なアルゴリズムであればアセンブリ言語
でも記述できる。ただし、アルゴリズムが必要
とする処理をプロセッサが知っていれば…
ちなみに、スタックというデータ構造は、Ｃ言
語では例のように、さりげなく使われている。
; アセンブリ言語によるgcd関数の例
.text
gcd:
mov.w @(2,sp),r0
mov.w
@(4,sp),r1
beq
1f
divxu.b r1l,r0
mov.b
r0h,r0l
xor
r0h,r0h
push
r0
push
r1
bsr
gcd
adds.w #2,sp
adds.w #2,sp
1:
rts
.end
スタックフレーム
ｓｐ＋４
; m
; n
; if (n == 0)
ｓｐ＋２
ｓｐ
引数ｎ
引数ｍ
戻りアドレス
; m % n
ｂｓｒ直後のスタック
; return m
レジスタ変数r2(変数r)が、不
要になっている。
再帰呼び出しでは、引数は新
しい領域に確保される。新し
い領域としては、スタックが使
われる。
ｓｐ＋１０
引数ｎ
ｓｐ＋８
引数ｍ
ｓｐ＋６
戻りアドレス
ｓｐ＋４
引数ｎ
ｓｐ＋２
引数ｍ
ｓｐ
戻りアドレス
学生実験に関するお話
• 大学では仮想化された抽象的な知識体系を講義する
– 実システムがどうなっているのかという、
体験に基づいた教育は不十分になりがち
• たとえばJ97のコンピュータアーキテクチャの講義では
– ハードウェアとソフトウェアのインターフェースに焦点
– コンパイラやＯＳなどの基本ソフトウェアとの関係にも言及
• 一方で実システムでは
– 物理的な大きさ・費用・量産性といった
現実的な制約の下で設計・製造
– 仮想化されたシステムとは、実装の相違・省略がある
– 集積技術の発達による構成要素のブラックボックス化
• 同様に、J97のプログラミング入門および
プログラミング言語論では、
– 手続き型言語によるプログラミングの概念から
プログラム言語の概念・機能を習得
• しかし、コンピュータアーキテクチャからＯＳまで
習得したとしても、
– 実システムでCPUをリセットした後で目的のプログラ
ムが実行されるまでにどのような過程をたどるのか、
プログラムはコンピュータシステムの何を制御すべ
きか、開発ツールの存在理由は何か、といったこと
を学習することはできない。
• 高知工科大学情報システム工学科のカリキュラム
コンピュータリテラシー（１Ｑ１）
早期より、ハードウェアとソフトウェアを
関連付けたい
情報科学１（１Ｑ２）
計算機言語１（１Ｑ３）
情報科学２（１Ｑ３）
情報科学３（１Ｑ４）
論理回路（１Ｑ４）
計算機言語２（２Ｑ１）
情報システム工学実験１（２Ｑ１－Ｑ２）
アルゴリズムとデータ構造（２Ｑ２）
情報システム工学実験２（２Ｑ３－Ｑ４）
情報システム工学実験３（３Ｑ１）
情報システム工学実験４（３Ｑ２）
計算機アーキテクチャ（３Ｑ１）
計算機システム（３Ｑ２）
ＯＳ（３Ｑ３）
大学院で開講する「組み込みシステム構成論」
（IT Spiral）など、といった講義にもつなげたい
ソフトウェア工学（３Ｑ３）
集積回路システム（３Ｑ４）
マイコン遊びをする学生が少ない
• たいていのコンパイラやアセンブラはfreeなのに
• マイコン（ＭＣＵ）などの入手にも困らないのに
– トラ技：２００７年８月（dsPIC）、２００７年１月
（MSP430）
– DigiKey, RS, MonotaROなどの品揃え豊富な部品屋
– Olimexなどの安い基板試作サービス
• 情報の入手にも困らないのに
– ネットで入手できるデータシート・アプリケーションノート
方針
• アセンブリ言語の利用
– 抽象的な知識と実システムの関連を認識
• C言語とアセンブリ言語の連携
– 手続き型言語の動作・仕組みを理解
• OSの機能を使わない
– 具体的なメモリや入出力ポートを意識した開発
• プログラムの動作が把握しやすいこと
– 単純なセンサとアクチュエータは必要
方針
• 思考力や想像力を鍛える
– OSや ICE (In-Circuit Emulator) を使わない
• デバグに使えるものを使う
– 最初はRCXをリセットだけのコード
– 以降は順に、モーターを回す、音階を鳴らす、LCDに表示す
る
• メモリ管理ユニット(MMU)が不要な部分まで
– ２年生の段階でできる
– ＯＳの講義を３年次にＷＳ室で行なう
組込みシステムを使う意義
• 講義時間内にアーキテクチャと動作の仕組みを把握
• 制御用のプログラムを開発することが可能
• 実システムとしてPCを扱うことは非現実的
– システムが階層的に構成されているとはいえ、複雑すぎる
• 講義時間程度(30回、120時間)では到底理解できない
– 高度に集積されたLSIで構成されている
• 構成要素を個別に見て取ることが困難
• 動作が高速すぎて動作を実感できない
• それならば、開発対象として周辺機器は？
– 小規模でも、独立したひとつのコンピュータがいい
– コンピュータシステム全体への理解を望みたい
学生実験の内容
• 学部２年生対象、前提となる知識は次のとおり
– Pascalの演習やJavaの実験を履修済み
– C言語やアセンブリ言語を使ったことはない
– 登録者数は85名、RCXを使った実験では80名参加
• 教員はメイン・サブが各１名、TAが３名
• 半年間で30回開講、1回4時間で計120時間
– 前半15回は個別に課題を解き、C言語を習得
– 後半はおおむね4人の1グループでRCXを使う
• グループ化後は、cvsによりソースやレポートを共有
学生実験課題（セルフ開発）
• C言語の講義・演習
– Cコンパイラ(gcc)と、gdb をつかったデバグ
• makeやcvsといったツールによる管理を導入
• グループ化後、LEGO Mindstorms RISを貸与
–
–
–
–
•
PCと RCXとの通信確立
RCXの生存確認、バージョン情報の取得
ダウンローダの作成、RCXへのダウンロード
S-recファイルの読み込み・送信
送り込むプログラム自体の作成はしない
学生実験課題（クロス開発１）
• 機械語水準から順にC言語水準までを講義
– 機械語命令（32bit減算、16bit乗算、ワード抽出）
– クロスアセンブラ・クロスコンパイラ
– ABI(Application Binary Interface)
• 基本となるプログラムを配布し・試行
– スピーカを鳴らすだけ
– LCDに表示させるだけ
• 受講生には配布プログラムを発展・改造
– 音階の調整、音楽を鳴らす
– LCDへの16進数表示、表示テストプログラム
学生実験課題（クロス開発２）
• メモリを意識したクロス開発の講義
• クロスリンカ
– ld script、ldによるアドレス計算・参照解決
• ハードウェアの定義
– モジュール定義(構造体変数へのアドレス付与)
• センサーの取り扱い
– センサからの入力・測定ルーチン作成
– ノイズ除去(IIRフィルタ、固定小数点演算
• アクチュエータの取り扱い
– モーターの制御、ライントレーサの走行制御
課題例
• アセンブリ言語でプログラムしてみる例
• 光センサー入力からのノイズをLPFにより除去
– C言語水準で光センサ操作、ADCから光強度入力
– LPFをIIRフィルタとして固定小数点演算により実装
– 受講生には叩き台となるプログラムを配布
• C関数のインターフェース、係数定義だけである
• アセンブリ言語でC関数iir_lpf()を記述
– デバグのためにLCDで戻り値を表示させる

Download Report