酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2010年6月18日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/index.html.

Presentation on theme: "酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2010年6月18日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/index.html."— Presentation transcript:

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2010年6月18日

2 プログラムとアルゴリズム 二分木と言った非線形なデータ構造と，これを扱うアルゴリズム，特に再帰的なアルゴリズムについて学ぶ
つぎにハッシュやソートと言った良く利用されるデータ構造やアルゴリズムの概観を得る．

3 Ｅｕｃｌｉｄの互除法（２ページ 1.1） ｍをｎで割って、余りをｒとする。
ｒ＝０であれば、アルゴリズムは終了する。 このとき、ｎが最大公約数である。 ｍ←ｎとする（ｎの値をｍに代入する）。 次にｎ←ｒとして１に戻る。 ここでは、次の処理が使われている。 除算 ０との比較・分岐処理 変数への代入 繰り返し（ループ）

4 /* 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を使えないプログラミング言語がある。

5 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば…
　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r ; 引数 m mov.w @(4,sp),r ; 引数 n 1: divxu.b r0l,r1 xor.b r2h,r2h mov.b r1h,r2l ; r = m % n beq 2f ; if(r == 0) goto 2 mov.w r0,r ; m = n mov.w r2,r ; n = r bra 1b ; goto 1 2: rts ; return n .end 戻りアドレス 引数ｎ 引数ｍ 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… ちなみに、スタックというデータ構造は、Ｃ言語では例のように、さりげなく使われている。

6 レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。
　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r ; m mov.w @(4,sp),r ; n beq 1f ; if (n == 0) divxu.b r1l,r0 mov.b r0h,r0l xor r0h,r0h ; m % n push r0 push r1 bsr gcd adds.w #2,sp 1: rts ; return m .end 戻りアドレス 引数ｎ 引数ｍ 　ｂｓｒ直後のスタック ｓｐ＋１０ 　ｓｐ＋８ 　ｓｐ＋６ 　ｓｐ＋４ 　ｓｐ＋２ 　　　　ｓｐ 戻りアドレス 引数ｎ 引数ｍ 戻りアドレス 引数ｎ 引数ｍ レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。

7 学生実験に関するお話 大学では仮想化された抽象的な知識体系を講義する たとえばJ97のコンピュータアーキテクチャの講義では
実システムがどうなっているのかという、 体験に基づいた教育は不十分になりがち たとえばJ97のコンピュータアーキテクチャの講義では ハードウェアとソフトウェアのインターフェースに焦点 コンパイラやＯＳなどの基本ソフトウェアとの関係にも言及 一方で実システムでは 物理的な大きさ・費用・量産性といった 現実的な制約の下で設計・製造 仮想化されたシステムとは、実装の相違・省略がある 集積技術の発達による構成要素のブラックボックス化

8 同様に、J97のプログラミング入門および プログラミング言語論では、
手続き型言語によるプログラミングの概念から プログラム言語の概念・機能を習得 しかし、コンピュータアーキテクチャからＯＳまで習得したとしても、 実システムでCPUをリセットした後で目的のプログラムが実行されるまでにどのような過程をたどるのか、プログラムはコンピュータシステムの何を制御すべきか、開発ツールの存在理由は何か、といったことを学習することはできない。

9 高知工科大学情報システム工学科のカリキュラム
コンピュータリテラシー（１Ｑ１） 早期より、ハードウェアとソフトウェアを 関連付けたい 情報科学１（１Ｑ２） 計算機言語１（１Ｑ３） 情報科学２（１Ｑ３） 情報科学３（１Ｑ４） 論理回路（１Ｑ４） 計算機言語２（２Ｑ１） 情報システム工学実験１（２Ｑ１－Ｑ２） アルゴリズムとデータ構造（２Ｑ２） 情報システム工学実験２（２Ｑ３－Ｑ４） 計算機アーキテクチャ（３Ｑ１） 情報システム工学実験３（３Ｑ１） 計算機システム（３Ｑ２） 情報システム工学実験４（３Ｑ２） ＯＳ（３Ｑ３） ソフトウェア工学（３Ｑ３） 大学院で開講する「組み込みシステム構成論」 （IT Spiral）など、といった講義にもつなげたい 集積回路システム（３Ｑ４）

10 マイコン遊びをする学生が少ない たいていのコンパイラやアセンブラはfreeなのに マイコン（ＭＣＵ）などの入手にも困らないのに
トラ技：２００７年８月（dsPIC）、２００７年１月（MSP430） DigiKey, RS, MonotaROなどの品揃え豊富な部品屋 Olimexなどの安い基板試作サービス 情報の入手にも困らないのに ネットで入手できるデータシート・アプリケーションノート

11 方針 アセンブリ言語の利用 C言語とアセンブリ言語の連携 OSの機能を使わない プログラムの動作が把握しやすいこと
抽象的な知識と実システムの関連を認識 C言語とアセンブリ言語の連携 手続き型言語の動作・仕組みを理解 OSの機能を使わない 具体的なメモリや入出力ポートを意識した開発 プログラムの動作が把握しやすいこと 単純なセンサとアクチュエータは必要

12 方針 思考力や想像力を鍛える メモリ管理ユニット(MMU)が不要な部分まで
OSや ICE (In-Circuit Emulator) を使わない デバグに使えるものを使う 最初はRCXをリセットだけのコード 以降は順に、モーターを回す、音階を鳴らす、LCDに表示する メモリ管理ユニット(MMU)が不要な部分まで ２年生の段階でできる ＯＳの講義を３年次にＷＳ室で行なう

13 組込みシステムを使う意義 講義時間内にアーキテクチャと動作の仕組みを把握 制御用のプログラムを開発することが可能
実システムとしてPCを扱うことは非現実的 システムが階層的に構成されているとはいえ、複雑すぎる 講義時間程度(30回、120時間)では到底理解できない 高度に集積されたLSIで構成されている 構成要素を個別に見て取ることが困難 動作が高速すぎて動作を実感できない それならば、開発対象として周辺機器は？ 小規模でも、独立したひとつのコンピュータがいい コンピュータシステム全体への理解を望みたい

14 学生実験の内容 学部２年生対象、前提となる知識は次のとおり 教員はメイン・サブが各１名、TAが３名
Pascalの演習やJavaの実験を履修済み C言語やアセンブリ言語を使ったことはない 登録者数は85名、RCXを使った実験では80名参加 教員はメイン・サブが各１名、TAが３名 半年間で30回開講、1回4時間で計120時間 前半15回は個別に課題を解き、C言語を習得 後半はおおむね4人の1グループでRCXを使う グループ化後は、cvsによりソースやレポートを共有

15 学生実験課題（セルフ開発） C言語の講義・演習 makeやcvsといったツールによる管理を導入
Cコンパイラ(gcc)と、gdb をつかったデバグ makeやcvsといったツールによる管理を導入 グループ化後、LEGO Mindstorms RISを貸与 PCと RCXとの通信確立 RCXの生存確認、バージョン情報の取得 ダウンローダの作成、RCXへのダウンロード S-recファイルの読み込み・送信 送り込むプログラム自体の作成はしない

16 学生実験課題（クロス開発１） 機械語水準から順にC言語水準までを講義 基本となるプログラムを配布し・試行
機械語命令（32bit減算、16bit乗算、ワード抽出） クロスアセンブラ・クロスコンパイラ ABI(Application Binary Interface) 基本となるプログラムを配布し・試行 スピーカを鳴らすだけ LCDに表示させるだけ 受講生には配布プログラムを発展・改造 音階の調整、音楽を鳴らす LCDへの16進数表示、表示テストプログラム

17 学生実験課題（クロス開発２） メモリを意識したクロス開発の講義 クロスリンカ ハードウェアの定義 センサーの取り扱い
ld script、ldによるアドレス計算・参照解決 ハードウェアの定義 モジュール定義(構造体変数へのアドレス付与) センサーの取り扱い センサからの入力・測定ルーチン作成 ノイズ除去(IIRフィルタ、固定小数点演算 アクチュエータの取り扱い モーターの制御、ライントレーサの走行制御

18 課題例 アセンブリ言語でプログラムしてみる例 光センサー入力からのノイズをLPFにより除去 アセンブリ言語でC関数iir_lpf()を記述
C言語水準で光センサ操作、ADCから光強度入力 LPFをIIRフィルタとして固定小数点演算により実装 受講生には叩き台となるプログラムを配布 C関数のインターフェース、係数定義だけである アセンブリ言語でC関数iir_lpf()を記述 デバグのためにLCDで戻り値を表示させる