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

■ 目次

講義概要
お知らせ・連絡事項等
進度
講義スライド
過去の中間・期末試験
教科書のまちがい

■ 講義概要

対象: 知能システム工学科昼間コース 2年生，フレックスコース 3年生
期間: 2024年度後期
時間: 水曜日 2限目 (10:20～11:50)
授業形式: 対面講義
担当教員: 井上康介 (E2棟 8F 801号室, kousuke.inoue.dr (アットマーク) vc.ibaraki.ac.jp)
指定教科書 (必携): 河西朝雄, "C言語によるはじめてのアルゴリズム入門", 技術評論社

ページの先頭

■ お知らせ・連絡事項等

中間試験について：第8回講義時間 (11/27) に中間試験を実施します．
- 時間・場所：11/27 (水) 2限・10番教室
- 出題範囲：これまでに授業で扱った範囲
- 出題形式：過去問（Teamsに掲載) を踏襲
- 注意事項：
C言語の基礎に関して：この講義では「プログラミング演習 I」の内容は習得済みとし，更に高度なC言語の使い方をしていきます．プログラミング演習で教わっていない事項についてはこの講義でも適宜説明を加えますが，この講義において「プログラミング演習ですでに教わっているが理解できていない点」について対応することは時間的に不可能です．C言語的に困難を感じている学生の選択肢は２つあります：(1)「そろそろC言語的に理解が難しい」と感じたら，必要な予習・復習に時間をかける，(2) この講義の単位をあきらめ，今後も情報系にはできるだけ手を出さない．ただし，(2) の選択肢については，本学科の趣旨には反しているということを伝えておきたいと思います (この学科が旨とするのは「情報とメカの融合領域を取り扱うエンジニアの育成」です)．
質問について：安くない授業料を支払い，貴重な若い時間を消費して授業を受けている以上，理解できないところをそのままに残さないようにしましょう．授業中に手を挙げてもらってもよいし，授業後に教壇まで来てもらっても，私の部屋に来てもらっても，あるいはメールを下さっても結構です．分からないところを聞くことを躊躇したり，面倒臭がったりしないようにしてください．授業時間外の質問については，メールではなく，Teams 上の本講義チームに質問用のチャネルを用意してあるので，そこでのチャットをできるだけ利用してください．

ページの先頭

■ 進度

回数	日程	内容	課題
第1回	10/02	ガイダンス (スライド) データ型・プリプロセッサの復習 (スライド)	なし
第2回	10/09	1-1 漸化式 (p.12-15前半) 1-3 順位付け (p.23-26前半) 1-6 ユークリッドの互除法 (p.37-39) 1-7 エラトステネスのふるい (p.41-45前半)	問題： PDF, Word 出題ソース： Cソース補足： PPT 解答： PPT, PDF 解答ソース： Cソース昨年度の課題3：問題：PDF, PPT 解答：PDF, PPT 解説：HTML 解答ソース：Cソース解答ソース (発展版)： Cソース
第3回	10/16	2-0 数値計算とは (p.48-49) 2-2 数値積分 (p.57-63) 2-3 テイラー展開 (p.65-66前半, 70後半) 2-4 非線形方程式の解法 (p.71-74)	問題： PDF 補足： PPT 出題ソース：Cソース解答： PPT 解答ソース： Cソース
第4回	10/23	アルゴリズムの計算量 (スライド・資料) 3-0 ソートとサーチとは (p.118-120) 3-1 基本ソート (p.121-127)	なし
第5回	10/30	3-2 シェル・ソート (p.128-133前半) 3-3 逐次探索と番兵 (p.135-138前半) 3-4 2分探索 (p.141-142) 3-8 ハッシュ (p.157-163)	問題：PPT
第6回	11/06	4-0 再帰とは (p.166-167) 4-1 再帰の簡単な例 (p.168-171) 4-4 ハノイの塔 (p.188-193) 4-6 クイック・ソート (p.206-208)	問題： PPT 解答： PPT
第7回	11/20	5-0 データ構造とは (p.214-215) 5-1 スタック (p.216-218前半) 5-2 キュー (p.222-224)	なし
第8回	11/27	中間テスト問題：PDF 模範解答：PDF リストとは (スライド) 5-3 リストの作成 (p.228-235) (逆順リスト作成まで)
第9回	12/04	5-3 リストの作成 (p.228-235) 5-4 リストへの挿入 (p.236-240) 5-5 リストからの削除 (p.243-247) (途中まで)	問題：PDF 補足説明：PPT 出題ソース：Cソース

ページの先頭

■ 講義スライド

スライドのファイルは，PDF および PowerPoint の形式です．PDF版は，アニメーションが入っていませんので，ところによっては理解が難しいですが，印刷には適しています．
スライドのファイルを印刷する場合，「印刷」ウィンドウの「プロパティ」ボタンを押し，「用紙設定」などの項目にある「割付印刷」を選択して，紙 1ページあたりスライド 9ページで出すなどの工夫をすると，インク・紙の節約になります．
ここに置かれている講義スライドは現在のバージョンであり，今後多少の更新を行う予定です．
講義スライド 1： PowerPoint, PDF

イントロダクション
基礎的知識の導入
ウォーミングアップ
数値計算
アルゴリズムの計算量

講義スライド 2： PowerPoint, PDF

ソートとサーチ

講義スライド 3： PowerPoint, PDF

再帰

講義スライド 4： PowerPoint, PDF

スタック・キュー
リスト

講義スライド 5： PowerPoint, PDF

木
グラフ

ページの先頭

■ 過去の中間・期末試験

過去問を Teams の本講義チームの「一般」チャネルの「ファイル」タブにおいてあります．

ページの先頭

■ 教科書のまちがい

指定教科書の間違いを見つけたらお知らせください．

ハッシュ (オープンアドレス法) のソースコード (Dr25.c, p.160~161) において，データ・テーブルの empty フラグが初期化されていません．main関数の3行目 (変数宣言の直後) に以下のコードを追加してください："for (n = 0; n < TableSize; n++) dat[n].empty = 0;"
(改訂第4版) クイック・ソートのソースコード (Dr31.c) において，p.210ページとp.211ページの間に，軸とグループ境界のデータの交換のためのコードが抜けています．以下のコードを追加してください："a[left] = a[j]; a[j] = s;" (←勘違いでした)

ページの先頭

リンク：井上のページ，生物知能機械学研究室

■ 目 次

■ 講義概要

■ お知らせ・連絡事項等

■ 進 度

■ 講義スライド

■ 過去の中間・期末試験

■ 教科書のまちがい

■ 目次

■ 進度