授業科目名				担当教員
アルゴリズムとデータ構造III				鈴木 良弥
時間割番号	単位数	コース	履修年次	期別	曜日	時限
263216	2	F	2	後期	木	II
［概要］
アルゴリズムとデータ構造I，IIやオートマトンと言語で学習した事柄の発展的な内容を扱う．また，事例を通じて今まで学んだ事柄が実際のアプリケーションでどのように利用されているかを学ぶ．
［具体的な達成目標］
１．計算論の基礎を理解する．<BR>２．構文解析などで使用されるアルゴリズムとデータ構造を理解する．<BR>３．検索エンジンで使用されるアルゴリズムとデータ構造を理解する．<BR>４．パターンマッチングで使用されるアルゴリズムとデータ構造を理解する．<BR>５．データ圧縮で使用されるアルゴリズムとデータ構造を理解する．
［必要知識・準備］
情報数学基礎，アルゴリズムとデータ構造I・II，オートマトンと言語
［評価方法・評価基準］
No 評価項目 割合 評価の観点 1 試験：期末期  50  % 授業理解力  2 試験：中間期  40  % 授業理解力  3 小テスト／レポート  10  % 自発的勉学
［教科書］
(未登録)
［参考書］
小倉久和, 形式言語と有限オートマトン入門, コロナ社, ISBN:4339023396, (オートマトンと言語の教科書) 北研二，津田和彦，獅々堀正幹, 情報検索アルゴリズム, 共立出版, ISBN:4320120361 亀山渉，金子格，渡辺裕, オーディオ・ビデオ圧縮入門, インプレスR＆D, ISBN:9784844323914 A.K.DEWDNEY, The New Turing Omnibus, Henry Holt, ISBN:9780805071665 湯田幸八，伊原充博, アルゴリズムとデータ構造, コロナ社, ISBN:4339011983
［講義項目］
１．スタック<BR>　２．文脈自由文法<BR>　３．構文解析　CKY法<BR>　４．構文解析　CKY法<BR>　５．構文解析　CKY法<BR>　６．動的計画法，ダイクストラ法<BR>　７．DPマッチング<BR>　８．A＊アルゴリズム<BR>　９．前半のまとめ，および中間試験<BR>１０．全文検索アルゴリズム（simple search, KMP）<BR>１１．全文検索アルゴリズム（BM）<BR>１２．全文検索アルゴリズム（Aho-Corasick）<BR>１３．暗号，符号化，エントロピー<BR>１４．テキスト圧縮，音声圧縮，画像圧縮<BR>１５．まとめ，および期末試験
［教育方法］
スライドと黒板を併用する．<BR>講義中に毎回簡単な演習を行う．<BR>授業資料をWebで公開する．<BR>小テストの解答例をWebで公開する．<BR>中間試験，期末試験の解答例をWebで公開する．<BR>なるべく他の授業との関連を説明する．<BR>プログラム作成のレポートを課す．
［JABEEプログラムの学習・教育目標との対応］
《コンピュータ・メディア工学科 コンピュータサイエンスコース》 (B)種々の型と構造をもつ情報の表現手法及び処理手法についての基本的な知識と技術を習得する． ◎ (C)問題を形式的にモデル化し，そのモデルを基に問題解決する知識と技術を習得する． ◎ (D)ソフトウェアの実現に必要な各種の道具や手法を習得・理解し，これらを組み合わせて問題解決を行える知識と技術，およびその自発的・継続的学習法を習得する． ○
［その他］
(未登録)