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

科目基礎情報

学校 長岡工業高等専門学校 開講年度 令和02年度 (2020年度)
授業科目 アルゴリズムとデータ構造
科目番号 0091 科目区分 専門 / 選択
授業形態 講義 単位の種別と単位数 学修単位: 2
開設学科 電子制御工学科 対象学年 4
開設期 前期 週時間数 2
教科書/教材 紀平拓男・春日伸弥著、プログラミングの宝箱 アルゴリズムとデータ構造 第2版、ソフトバンク、2011
担当教員 竹部 啓輔

到達目標

(科目コード:31418,英語名:Data Structures and Algorithms)
この科目は長岡高専の教育目標の(D)と主体的に係わる。この科目の到達目標と、各到達目標と長岡高専の学習・教育到達目標との関連を、到達目標、評価の重み、学習・教育到達目標との関連の順で次に示す。
①ソーティング、データ探索などの代表的なアルゴリズムを理解する。35% (b2), (d1)、②代表的なデータ構造について理解する。35% (b2), (d1)、③代表的なアルゴリズムとデータ構造を実際のプログラム作成に役立てる。30% (b2), (d3)

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安最低限の到達レベルの目安未到達レベルの目安
評価項目1ソーティング、データ探索などの代表的なアルゴリズムを理解し、説明することができるソーティング、データ探索などの代表的なアルゴリズムを理解しているソーティング、データ探索などの代表的なアルゴリズムを概ね理解しているソーティング、データ探索などの代表的なアルゴリズムを理解していない
評価項目2代表的なデータ構造について理解し、説明することができる代表的なデータ構造について理解している代表的なデータ構造について概ね理解している代表的なデータ構造について理解していない
評価項目3代表的なアルゴリズムとデータ構造を実際のプログラム作成に効果的に役立てることができる代表的なアルゴリズムとデータ構造を実際のプログラム作成に役立てることができる代表的なアルゴリズムとデータ構造を実際のプログラム作成に概ね役立てることができる代表的なアルゴリズムとデータ構造を実際のプログラム作成に役立てることができない

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

教育方法等

概要:
本講義では、情報処理の対象を表現するためのデータ構造や、ソーティング、探索などの代表的な情報処理を実現するアルゴリズムについて学ぶ。
○関連する科目: 計算機システム(前年度履修)、情報処理Ⅱ(前年度履修)、離散数学(前期履修)、数値解析(後期履修)、コンピュータネットワーク(次年度履修)、ネットワークプログラミング(次年度履修)、プログラミング演習II(次年度履修)
授業の進め方・方法:
授業では、講義による説明の後に、C言語を利用したプログラミング演習を行う。
この科目は学修単位科目のため、事前・事後学習として、演習課題レポートなどを実施します。
注意点:
C言語プログラミングについての基本的知識(配列を利用したプログラミング程度)が必要である。演習問題は、ほとんどが基本的なものであり、自ら拡張を試みることを強く勧める。
本科目は本来、面接授業として実施を予定していたものであるが、新型コロナウイルス感染症の拡大による緊急事態において、必要に応じ遠隔授業として実施するものである。

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 授業内容の説明
アルゴリズムと計算量
アルゴリズムの概念を説明できる
計算量の概念を理解する
2週 ソーティング(1)クイックソート クイックソートのアルゴリズムを理解する
再帰呼出の動作について理解する
3週 ソーティング(2)マージソート マージソートのアルゴリズムを理解する
4週 データ探索(1)逐次探索、二分探索 逐次探索、二分探索のアルゴリズムを理解する
番兵について理解する
5週 データ探索(2)二分探索の改良 二分探索において、同値のデータがあった場合にその一番最初に現れる要素を効率よく見つけるアルゴリズムについて理解する
6週 線形リスト(1)リスト構造 予めデータ数が分からない場合の配列の扱い方について理解する
線形リストのデータ構造について理解する
7週 線形リスト(2)リスト構造を利用したプログラミング 線形リストのデータ構造について理解する
8週 ツリー構造 ツリー構造について理解する
2ndQ
9週 ハッシュ
スタック
ハッシュマップの基本事項について理解する
スタックについて理解する
10週 長桁計算 長桁計算の実現方法について理解する
円周率などの長桁計算の仕組みを理解する
11週 モンテカルロシミュレーション シミュレーションが必要とされる理由を理解する
モンテカルロシミュレーションの考え方を理解する
12週 高速フーリエ変換 高速フーリエ変換の仕組みを理解する
13週 バックトラック法、幅優先探索 バックトラック法について理解する
幅優先探索について理解する
14週 誤差について
コンピュータで計算を行うときに生じる誤差について理解する
15週 動的計画法 動的計画法の概念について理解する
16週 期末試験(R2年度:ここまでのまとめ) 試験時間:80分

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

分類分野学習内容学習内容の到達目標到達レベル授業週
基礎的能力数学数学数学解の公式等を利用して、2次方程式を解くことができる。3
人文・社会科学国語国語論理的な文章(論説や評論)に表された考えに対して、その論拠の妥当性の判断を踏まえて自分の意見を述べることができる。3前16
専門の分野に関する用語を思考や表現に活用できる。3前16
実用的な文章(手紙・メール)を、相手や目的に応じた体裁や語句を用いて作成できる。3
報告・論文の目的に応じて、印刷物、インターネットから適切な情報を収集できる。3
収集した情報を分析し、目的に応じて整理できる。3
報告・論文を、整理した情報を基にして、主張が効果的に伝わるように論理の構成や展開を工夫し、作成することができる。3
課題に応じ、根拠に基づいて議論できる。3前1,前2,前3,前4,前5,前6,前7,前8,前9,前10,前11,前12,前13,前14
英語英語運用の基礎となる知識中学で既習の語彙の定着を図り、高等学校学習指導要領に準じた新出語彙、及び専門教育に必要となる英語専門用語を習得して適切な運用ができる。3
英語運用能力向上のための学習関心のあるトピックや自分の専門分野に関する論文やマニュアルなどの概要を把握し、必要な情報を読み取ることができる。3
工学基礎情報リテラシー情報リテラシー情報を適切に収集・処理・発信するための基礎的な知識を活用できる。3
論理演算と進数変換の仕組みを用いて基本的な演算ができる。3
コンピュータのハードウェアに関する基礎的な知識を活用できる。3
情報伝達システムやインターネットの基本的な仕組みを把握している。3
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。4前2
与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。4前2
任意のプログラミング言語を用いて、構築したアルゴリズムを実装できる。4前2,前3,前4,前5
専門的能力分野別の専門工学機械系分野情報処理プログラムを実行するための手順を理解し、操作できる。4前1
定数と変数を説明できる。4前1
整数型、実数型、文字型などのデータ型を説明できる。4前1
演算子の種類と優先順位を理解し、適用できる。4前1
算術演算および比較演算のプログラムを作成できる。4前1
データを入力し、結果を出力するプログラムを作成できる。4前1
条件判断プログラムを作成できる。4前1
繰り返し処理プログラムを作成できる。4前1
一次元配列を使ったプログラムを作成できる。4前1,前2,前3,前4,前5,前8
情報系分野プログラミング代入や演算子の概念を理解し、式を記述できる。4前1,前2,前3,前4
プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。4前1,前2,前3,前4
変数の概念を説明できる。4
データ型の概念を説明できる。4
制御構造の概念を理解し、条件分岐を記述できる。4
制御構造の概念を理解し、反復処理を記述できる。4
与えられた問題に対して、それを解決するためのソースプログラムを記述できる。4前1,前2,前3,前4
ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。4前1,前2,前3,前4
与えられたソースプログラムを解析し、プログラムの動作を予測することができる。4
主要な言語処理プロセッサの種類と特徴を説明できる。2
ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。3
要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。3前1,前2,前3,前4,前5,前6,前7,前8,前10
要求仕様に従って、いずれかの手法により動作するプログラムを設計することができる。3前2,前3
要求仕様に従って、いずれかの手法により動作するプログラムを実装することができる。3前2,前3
要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを実装できる。3前2,前3
ソフトウェアアルゴリズムの概念を説明できる。3前1,前2,前3,前4
与えられたアルゴリズムが問題を解決していく過程を説明できる。3前1,前2,前3,前4
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。3前1,前2,前3,前4
整列、探索など、基本的なアルゴリズムについて説明できる。3前2,前3,前4,前5
時間計算量によってアルゴリズムを比較・評価できることを説明できる。4
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。4
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。3前3,前4,前6,前7,前8
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。3前4,前6,前7
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。3前6,前7,前8,前9
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。4前6,前7,前8
ソフトウェアを中心としたシステム開発のプロセスを説明できる。3
ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。3前2,前3
同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。3前3
計算機工学整数・小数をコンピュータのメモリ上でディジタル表現する方法を説明できる。4前14
基数が異なる数の間で相互に変換できる。4前14
整数を2進数、10進数、16進数で表現できる。4
小数を2進数、10進数、16進数で表現できる。4
基本的な論理演算を行うことができる。4前13
基本的な論理演算を組合わせて、論理関数を論理式として表現できる。4前13
コンピュータを構成する基本的な要素の役割とこれらの間でのデータの流れを説明できる。4
システムプログラムコンピュータシステムにおけるオペレーティングシステムの位置づけを説明できる。3
コンパイラの役割と仕組みについて説明できる。3
情報数学・情報理論コンピュータ上での数値の表現方法が誤差に関係することを説明できる。3前14
コンピュータ上で数値計算を行う際に発生する誤差の影響を説明できる。3前14
コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる。3前15
その他の学習内容少なくとも一つの具体的なコンピュータシステムについて、起動・終了やファイル操作など、基本的操作が行える。3前1
少なくとも一つの具体的なオフィススイート等を使って、文書作成や図表作成ができ、報告書やプレゼンテーション資料を作成できる。3前1
少なくとも一つのメールツールとWebブラウザを使って、メールの送受信とWebブラウジングを行うことができる。3前1
分野別の工学実験・実習能力情報系分野【実験・実習能力】情報系【実験・実習】与えられた問題に対してそれを解決するためのソースプログラムを、標準的な開発ツールや開発環境を利用して記述できる。4前1,前2,前3,前4,前5,前6,前7
ソフトウェア生成に利用される標準的なツールや環境を使い、ソースプログラムをロードモジュールに変換して実行できる。4前1,前2,前3,前4,前5,前6,前7
ソフトウェア開発の現場において標準的とされるツールを使い、生成したロードモジュールの動作を確認できる。4前1,前2,前3,前4,前5,前6,前7
フローチャートなどを用いて、作成するプログラムの設計図を作成することができる。4
問題を解決するために、与えられたアルゴリズムを用いてソースプログラムを記述し、得られた実行結果を確認できる。4
標準的な開発ツールを用いてプログラミングするための開発環境構築ができる。3
要求仕様にあったソフトウェア(アプリケーション)を構築するために必要なツールや開発環境を構築することができる。3
要求仕様に従って標準的な手法によりプログラムを設計し、適切な実行結果を得ることができる。3
分野横断的能力汎用的技能汎用的技能汎用的技能日本語と特定の外国語の文章を読み、その内容を把握できる。3
他者とコミュニケーションをとるために日本語や特定の外国語で正しい文章を記述できる。3
他者が話す日本語や特定の外国語の内容を把握できる。3
日本語や特定の外国語で、会話の目標を理解して会話を成立させることができる。3
課題の解決は直感や常識にとらわれず、論理的な手順で考えなければならないことを知っている。3
事実をもとに論理や考察を展開できる。3
結論への過程の論理性を言葉、文章、図表などを用いて表現できる。3
態度・志向性(人間力)態度・志向性態度・志向性周囲の状況と自身の立場に照らし、必要な行動をとることができる。3
自らの考えで責任を持ってものごとに取り組むことができる。3
目標の実現に向けて計画ができる。3
目標の実現に向けて自らを律して行動できる。3
日常の生活における時間管理、健康管理、金銭管理などができる。3
高専で学んだ専門分野・一般科目の知識が、企業や大学等でどのように活用・応用されるかを説明できる。3
企業活動には品質、コスト、効率、納期などの視点が重要であることを認識している。3

評価割合

試験レポートその他合計
総合評価割合70300100
基礎的能力1010020
専門的能力6020080
分野横断的能力0000