岡山県立大学：シラバス

授業科目名（和文）［Course］	データ構造とアルゴリズム
授業科目名（英文）［Course］	Data Structures and Algorithms
学部（研究科）［Faculty］	情報工学部
学科（専攻）［Department］	情報システム工学科
担当教員（○：代表教員） [Principle Instructor(○) and Instructors]	○菊井　玄一郎　　自室番号（2606）、電子メール（kikuicse.oka-pu.ac.jp） ※利用の際は, を @に置き換えてください
単位数［Point(Credit)］	前期　2単位
対象学生［Eligible students］	2年次生
授業概略と目標［Course description and Objects］	プログラムの骨格をなす，データ構造，および，アルゴリズムの基礎を習得する．データ構造としては構造体，リスト，スタック，木構造，アルゴリズムに関してはリストの探索，整列，文字列探索，経路探索をカバーする．この内容はプログラムを作成する上で必須のものである．
到達目標［Learning Goal］	１）計算量，計算の複雑さの考え方を理解する２）基本データ構造（配列，連結リスト，スタックなど）を理解する３）配列や文字列の探索，整列，経路探索の手法と計算量を理解する
履修上の注意［Notes］	１年次でプログラミング言語，ソフトウエア演習等のソフトウエア基礎に関する講義・演習を履修していることが望ましい．与えられた項目について必ず予習をしてくること．授業では理解内容の確認を行う．
授業計画とスケジュール［Course schedule］	1 概論：アルゴリズムとは?　・配列の探索を例にアルゴリズムの概念とデータ構造と密接に関係することを学ぶ． 2 配列の探索(1)：線形探索と二分探索・線形探索（復習），番兵，二分探索のアルゴリズムを理解する． 3 計算量の概念：・時間計算量と空間計算量の概念，それを表す「オーダー記法」について理解する 4 データ構造：・ポインタを利用する連結リストと木構造を理解する（ポインタについて復習しておくこと） 5 配列の探索(2)：ハッシュ法１・ハッシュ法の基本概念であるハッシュ関数と衝突，チェイン法による実装について理解する 6 配列の探索(3)：ハッシュ法２・オープンアドレス法について説明する． 7 ミニテスト，整列(1)：バブルソート，挿入ソート・整列アルゴリズムのうち，最もシンプルな２つの技法について理解する． 8 整列(2)クイックソート・高速な整列アルゴリズムとして知られているクイックソートについて理解する． 9 整列(3)：マージソート・マージソートは分割統治法の最も分かりやすい例である．整列手法だけでなく分割統治法の考え方も併せて理解したい 10 整列(4)：ヒープソート・ヒープの概念を説明したのち，ヒープソートについて説明する 11 復習（整列） 12 経路探索：Dijkstra法・経路探索の基本となるDijkstra法を理解する． 13 文字列の探索：Boyer-Moore法 14 アルゴリズムの限界：P,NP ・効率的なアルゴリズムが見つかっていない問題やそもそもアルゴリズムで解けない問題とはどういうものかを学ぶ． 15 まとめ(練習問題解説・質問コーナー)
成績評価方法と基準［Grading policy (Evaluation)］	定期試験(60%)，および，授業態度（積極性）(40%)により総合的に評価する
教科書［Textbook］	教科書：なし．資料を配布する．　参考書：書名に「アルゴリズムとデータ構造」（あるいは「データ構造とアルゴリズム」）ということばを含むものなら何でもよい．自分の好みに合ったものを見つけて学習して欲しい．少し変わったものとして，・結城浩，”数学ガール（乱択アルゴリズム）”，ソフトバンククリエイティブ，2011 は対話調でアルゴリズムや計算量の考え方が丁寧に書かれている（やさしく書かれているがレベルは高い）．本講義と関連深いのは特に1-3,6章．昨年度の教科書も良書である：近藤嘉之，「定本　Ｃプログラマのためのアルゴリズムとデータ構造」ソフトバンククリエイティブ．
自主学習ガイド及びキーワード［Self learning］	・予習に必要な資料等は　http://iis.cse.oka-pu.ac.jp/courses/dsa/　で公開する（学外からのアクセス制限あり）・指示された予習を行うこと．
開講年度［Year of the course］	28
資格等に関する事項	基本情報技術者，応用情報技術者のアルゴリズム部分の内容を含む

授業科目名（和文）［Course］	データ構造とアルゴリズム
授業科目名（英文）［Course］	Data Structures and Algorithms
学部（研究科）［Faculty］	情報工学部
学科（専攻）［Department］	情報システム工学科
担当教員（○：代表教員） [Principle Instructor(○) and Instructors]	○菊井　玄一郎　　自室番号（2606）、電子メール（kikuicse.oka-pu.ac.jp） ※利用の際は, を @に置き換えてください
単位数［Point(Credit)］	前期　2単位
対象学生［Eligible students］	2年次生
授業概略と目標［Course description and Objects］	プログラムの骨格をなす，データ構造，および，アルゴリズムの基礎を習得する．データ構造としては構造体，リスト，スタック，木構造，アルゴリズムに関してはリストの探索，整列，文字列探索，経路探索をカバーする．この内容はプログラムを作成する上で必須のものである．
到達目標［Learning Goal］	１）計算量，計算の複雑さの考え方を理解する２）基本データ構造（配列，連結リスト，スタックなど）を理解する３）配列や文字列の探索，整列，経路探索の手法と計算量を理解する
履修上の注意［Notes］	１年次でプログラミング言語，ソフトウエア演習等のソフトウエア基礎に関する講義・演習を履修していることが望ましい．与えられた項目について必ず予習をしてくること．授業では理解内容の確認を行う．
授業計画とスケジュール［Course schedule］	1 概論：アルゴリズムとは?　・配列の探索を例にアルゴリズムの概念とデータ構造と密接に関係することを学ぶ． 2 配列の探索(1)：線形探索と二分探索・線形探索（復習），番兵，二分探索のアルゴリズムを理解する． 3 計算量の概念：・時間計算量と空間計算量の概念，それを表す「オーダー記法」について理解する 4 データ構造：・ポインタを利用する連結リストと木構造を理解する（ポインタについて復習しておくこと） 5 配列の探索(2)：ハッシュ法１・ハッシュ法の基本概念であるハッシュ関数と衝突，チェイン法による実装について理解する 6 配列の探索(3)：ハッシュ法２・オープンアドレス法について説明する． 7 ミニテスト，整列(1)：バブルソート，挿入ソート・整列アルゴリズムのうち，最もシンプルな２つの技法について理解する． 8 整列(2)クイックソート・高速な整列アルゴリズムとして知られているクイックソートについて理解する． 9 整列(3)：マージソート・マージソートは分割統治法の最も分かりやすい例である．整列手法だけでなく分割統治法の考え方も併せて理解したい 10 整列(4)：ヒープソート・ヒープの概念を説明したのち，ヒープソートについて説明する 11 復習（整列） 12 経路探索：Dijkstra法・経路探索の基本となるDijkstra法を理解する． 13 文字列の探索：Boyer-Moore法 14 アルゴリズムの限界：P,NP ・効率的なアルゴリズムが見つかっていない問題やそもそもアルゴリズムで解けない問題とはどういうものかを学ぶ． 15 まとめ(練習問題解説・質問コーナー)
成績評価方法と基準［Grading policy (Evaluation)］	定期試験(60%)，および，授業態度（積極性）(40%)により総合的に評価する
教科書［Textbook］	教科書：なし．資料を配布する．　参考書：書名に「アルゴリズムとデータ構造」（あるいは「データ構造とアルゴリズム」）ということばを含むものなら何でもよい．自分の好みに合ったものを見つけて学習して欲しい．少し変わったものとして，・結城浩，”数学ガール（乱択アルゴリズム）”，ソフトバンククリエイティブ，2011 は対話調でアルゴリズムや計算量の考え方が丁寧に書かれている（やさしく書かれているがレベルは高い）．本講義と関連深いのは特に1-3,6章．昨年度の教科書も良書である：近藤嘉之，「定本　Ｃプログラマのためのアルゴリズムとデータ構造」ソフトバンククリエイティブ．
自主学習ガイド及びキーワード［Self learning］	・予習に必要な資料等は　http://iis.cse.oka-pu.ac.jp/courses/dsa/　で公開する（学外からのアクセス制限あり）・指示された予習を行うこと．
開講年度［Year of the course］	28
資格等に関する事項	基本情報技術者，応用情報技術者のアルゴリズム部分の内容を含む