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

科目基礎情報

学校 東京工業高等専門学校 開講年度 令和02年度 (2020年度)
授業科目 アルゴリズムとデータ構造Ⅱ
科目番号 0093 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 1
開設学科 情報工学科 対象学年 3
開設期 後期 週時間数 2
教科書/教材 Web教材使用
担当教員 北越 大輔,坂井 良広

到達目標

アルゴリズムの概念を理解し,与えられた問題に対してプログラムを作ることができる.
同じ問題に対して複数のアルゴリズムが存在することを理解し,計算量によってそれらを比較することができる.
基本的なデータ構造を理解し説明できる.またそれらのデータ構造を用いた基本的なプログラムを作ることができる.

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
アルゴリズムの概念を理解し,与えられた問題に対してプログラムを作ることができるアルゴリズムの概念を理解し,自ら工夫してプログラムを作りあげることができる.アルゴリズムの概念を理解し,具体的に手順を示すとプログラムを作ることができるアルゴリズムの概念を理解していない.または,簡単なアルゴリズムを実現するプログラムが自力で書くことができない.
同じ問題に対して複数のアルゴリズムが存在することを理解し,計算量によってそれらを比較することができるアルゴリズムの計算量を数式で理論的に展開し,複数のアルゴリズムの比較を行うことができる.幾つかのアルゴリズムに関して計算量の議論を理解し,それによってアルゴリズムの比較が可能であることを理解している.計算量の概念が理解できない.または,計算量の議論の内容を理解することができない.
基本的なデータ構造を理解し説明できる.またそれらのデータ構造を用いた基本的なプログラムを作ることができる.様々なデータ構造を自ら理解し,それらのデータ構造を用いた簡単なプログラムを自力で作ることができる.与えられたデータ構造を理解し,それらを用いた簡単なプログラムを詳細な解説を見ながら作ることができる.与えられたデータ構造を理解することができない.または,基本的なデータ構造を用いた簡単なプログラムを作ることができない.

学科の到達目標項目との関係

教育方法等

概要:
基礎事項として,ポインタおよび再帰について学習する。次にデータの表現方法や効率の良いアルゴリズムの実装能力を身につけるため,基本的かつ代表的なアルゴリズムとデータ構造について学習する.
授業の進め方・方法:
原則として,毎回の授業で課題の説明を行い,残りの時間はプログラムを作成する演習時間とする.ただし,計算量の解説などの一部の項目では,座学中心の授業を行う.
注意点:
原則として授業の後半でC言語によるプログラミング演習を行なう.課題が授業時間内に終わらないことも予想されるので,自宅にプログラム開発環境を構築することが望ましい.また本科目の単位を修得するためには,全ての課題を期限内に提出することが必要条件となるので注意すること.

授業計画

授業内容 週ごとの到達目標
後期
3rdQ
1週 線形探索と二分探索
計算時間の比較と考察
線形・二分探索のアルゴリズムを理解・実装し,適切な条件下で各手法の計算時間を測定・比較できる.
2週 文字列検索(1)
力まかせ法とKMP法
力まかせ法・KMP法のアルゴリズムを理解し実装できる.
3週 文字列検索(2)
BM法
BM法のアルゴリズムを理解し実装できる.
4週 ポインタを用いた文字列処理 C言語におけるポインタの概念を理解し,文字列処理に応用することができる.
5週 ポインタを用いた線形リストの実現 線形リストの概念を理解しリスト構造を応用した簡単なデータ処理機能を実装できる.
6週 ハッシュ関数を利用した検索 ハッシュ法のアルゴリズムを理解し実装できる.
7週 木構造の表現法
木構造を用いた検索
木構造の概念を理解し木構造を応用した簡単なデータ処理機能を実装できる.
8週 中間試験
4thQ
9週 グラフ構造を用いた経路探索(1)
深さ優先探索
深さ優先探索のアルゴリズムを理解し実装できる.
10週 グラフ構造を用いた経路探索(2)
幅優先探索
幅優先探索のアルゴリズムを理解し実装できる.
11週 グラフ構造を用いた経路探索(3)
ダイクストラ法
ダイクストラ法のアルゴリズムを理解し実装できる.
12週 グラフ構造を用いた経路探索(4)
フロイド法
フロイド法のアルゴリズムを理解し実装できる.
13週 動的計画法 動的計画法のアルゴリズムを理解し実装できる.
14週 基本情報技術者試験・応用情報技術者試験における「アルゴリズムとデータ構造」 基本・応用情報技術者試験の内容および各試験における出題と当該演習との関連性を理解できる.
15週 後期課題の総まとめ 後期すべての課題について復習し未提出課題の提出を完了する.
16週 期末試験

モデルコアカリキュラムの学習内容と到達目標

分類分野学習内容学習内容の到達目標到達レベル授業週
基礎的能力工学基礎技術者倫理(知的財産、法令順守、持続可能性を含む)および技術史技術者倫理(知的財産、法令順守、持続可能性を含む)および技術史技術者倫理が必要とされる社会的背景や重要性を認識している。3
説明責任、製造物責任、リスクマネジメントなど、技術者の行動に関する基本的な責任事項を説明できる。3
社会における技術者の役割と責任を説明できる。3
現代社会の具体的な諸問題を題材に、自ら専門とする工学分野に関連させ、技術者倫理観に基づいて、取るべきふさわしい行動を説明できる。3
情報技術の進展が社会に及ぼす影響、個人情報保護法、著作権などの法律について説明できる。3
高度情報通信ネットワーク社会の中核にある情報通信技術と倫理との関わりを説明できる。3
環境問題の現状についての基本的な事項について把握し、科学技術が地球環境や社会に及ぼす影響を説明できる。3
環境問題を考慮して、技術者としてふさわしい行動とは何かを説明できる。3
国際社会における技術者としてふさわしい行動とは何かを説明できる。3
過疎化、少子化など地方が抱える問題について認識し、地域社会に貢献するために科学技術が果たせる役割について説明できる。3
知的財産の社会的意義や重要性の観点から、知的財産に関する基本的な事項を説明できる。3
知的財産の獲得などで必要な新規アイデアを生み出す技法などについて説明できる。3
技術者の社会的責任、社会規範や法令を守ること、企業内の法令順守(コンプライアンス)の重要性について説明できる。3
技術者を目指す者として、諸外国の文化・慣習などを尊重し、それぞれの国や地域に適用される関係法令を守ることの重要性を把握している。3
全ての人々が将来にわたって安心して暮らせる持続可能な開発を実現するために、自らの専門分野から配慮すべきことが何かを説明できる。3
技術者を目指す者として、平和の構築、異文化理解の推進、自然資源の維持、災害の防止などの課題に力を合わせて取り組んでいくことの重要性を認識している。3

評価割合

試験課題相互評価態度ポートフォリオその他合計
総合評価割合70300000100
基礎的能力205000025
専門的能力5025000075
分野横断的能力0000000