基本情報

学部 IT総合学部
科目 アルゴリズムとデータ構造
教員名 松本 幸子
年度 / 学期 2019年度春学期
開講期間 2019/4/4  ~  2019/8/8
科目履修区分 専門講義(選択)/専門基礎(選択)/専門基礎(必修)/専門基礎科目
単位 2
科目レベル 3

ページの先頭へ戻る

科目概要

コンピュータのプログラムは問題を解くための具体的な処理を定式化した「アルゴリズム」と、その処理に必要なデータを管理する「データ構造」から構成される。アルゴリズムとはプログラミング言語に依存しない処理の本質であり、アルゴリズムを理解することは様々なプログラムを設計する上で重要である。本科目では代表的なアルゴリズムとデータ構造を学び、C言語で記述したプログラムを例に挙げ、具体的な学習を進める。また、アルゴリズムで重要視される効率性の評価基準となる計算量についても学習し、様々なアルゴリズムの特徴や性能について考察する。

ページの先頭へ戻る

科目目標

①データの探索アルゴリズムについて理解する
②データの並べ替えアルゴリズムについて理解する
③文字列の検索アルゴリズムについて理解する
④様々なデータ構造(配列、リスト、スタック、キュー、ツリー、ハッシュ)とその利用法について理解する
⑤再帰アルゴリズムについて理解する
⑥C言語への理解を深める

ページの先頭へ戻る

履修前提条件

・Cプログラミング演習(旧:アルゴリズム論演習)
・情報処理のための基礎知識
の単位を修得していることが望ましい

※この科目ではプログラミング学習専用のシステムを利用するため、「実習環境利用料」として授業料とは別に4,800円が徴収されます。専用システムのライセンスを発行しますので、追加履修登録終了後の受講取消は受け付けられません。

この科目はテキスト形式の授業コンテンツを含んでいます。この点をよく理解した上で、履修登録を行ってください。

ページの先頭へ戻る

授業教材

教科書 ※購入必須

なし

ツール

ツール名 発売元 バージョン 必要PCスペック 備考
ツール名
goorm IDE (演習環境で利用します)
発売元
バージョン
必要PCスペック
最新のブラウザ
備考
詳細は第1回授業でご案内します。

参考資料 ※購入任意

なし

その他の資料

なし

ページの先頭へ戻る

期末試験実施方法について

Webテスト形式

ページの先頭へ戻る

授業時間外の学修と評価について

【授業時間外の学修について】
▪受講後にも、授業で扱ったプログラムを実際に演習環境で動かし、学んだアルゴリズムをさまざまな問題に適用することによって、アルゴリズムの特徴や性能について理解を深めてください。
▪️発展的学習として、授業で扱ったアルゴリズム以外でも、気になったアルゴリズムについて、さまざまな書籍やインターネット・サイトを活用して調べ理解を深めてください。


ページの先頭へ戻る

評価配分

ディベート レポート 小テスト 期末試験 その他 合計
0 % 0 % 50 % 50 % 0 % 100 %
 0 %   0 %   50 %   50 %   0 %   100 % 

ページの先頭へ戻る

各回の授業内容

授業内容および目次 小テスト他 備考(教科書、参考資料等)
第1回 1)タイトル:
オリエンテーション

2)学習目標:
・アルゴリズムとは何かを理解する
・演習環境の使い方を理解する
・C言語によるプログラム作成の流れを理解する

3)目次:
第1章 講義概要
第2章 C言語の復習1
第3章 C言語の復習2
第4章 演習:乱数データの作成

この回の課題
・小テスト
 
第2回 1)タイトル:
データの探索1~線形探索~

2)学習目標:
・線形探索(リニアサーチ)のアルゴリズムを理解する
・番人による効率化の工夫を理解する
・表の検索の仕組みを理解する
・線形探索アルゴリズムによる検索を体験する

3)目次:
第1章 線形探索
第2章 番人の利用
第3章 表の探索
第4章 演習:線形探索プログラム

この回の課題
・小テスト
 
第3回 1)タイトル:
データの探索2~二分探索~

2)学習目標:
・二分探索(バイナリサーチ)のアルゴリズムを理解し実装する
・アルゴリズムの性能を表す計算量を理解する
・二分探索アルゴリズムによる検索を体験し、探索アルゴリズムそれぞれの特徴と性能の違いを理解する

3)目次:
第1章 二分探索
第2章 アルゴリズムの性能
第3章 探索アルゴリズムの比較
第4章 演習:二分探索プログラム

この回の課題
・小テスト
 
第4回 1)タイトル:
単純な並べ替え1~交換ソート~

2)学習目標:
・バブルソ―トのアルゴリズムを理解する
・コムソートのアルゴリズムを理解する
・上記アルゴリズムによる並べ替えを体験し、それぞれのアルゴリズムの特徴と性能について理解する

3)目次:
第1章 バブルソート
第2章 コムソート
第3章 交換ソートの性能
第4章 演習:交換ソートのプログラム

この回の課題
・小テスト
 
第5回 1)タイトル:
単純な並べ替え2~挿入ソート~

2)学習目標:
・基本挿入法のアルゴリズムを理解する
・シェルソートのアルゴリズムを理解する
・上記アルゴリズムによる並べ替えを体験し、それぞれのアルゴリズムの特徴と性能について理解する

3)目次:
第1章 基本挿入法
第2章 シェルソート
第3章 挿入ソートの性能
第4章 演習:挿入ソートのプログラム

この回の課題
・小テスト
 
第6回 1)タイトル:
単純な並べ替え3~選択ソート~

2)学習目標:
・基本選択法のアルゴリズムを理解する
・上記アルゴリズムによる並べ替えを体験し、それぞれのアルゴリズムの特徴と性能について理解する
・さまざまなアルゴリズムによるレコードの並べ替えを体験し、理解を深める

3)目次:
第1章 基本選択法
第2章 基本選択法の性能
第3章 レコードの並べ替え
第4章 演習:選択ソートのプログラム

この回の課題
・小テスト
 
第7回 1)タイトル:
文字列の検索1~単純検索法~

2)学習目標:
・単純検索法のアルゴリズムを理解する
・KMP法のアルゴリズムの概要を理解する
・上記アルゴリズムによる文字列検索を体験し、それぞれのアルゴリズムの特徴と性能について理解する

3)目次:
第1章 単純検索法
第2章 KMP法
第3章 複数箇所の検索
第4章 演習:単純検索法のプログラム

この回の課題
・小テスト
 
第8回 1)タイトル:
文字列の検索2~ボイヤー・ムーア法~

2)学習目標:
・ボイヤー・ムーア法のアルゴリズムを理解する
・ボイヤー・ムーア法による文字列検索を体験し、アルゴリズムの特徴と性能について理解する

3)目次:
第1章 ボイヤー・ムーア法1
第2章 ボイヤー・ムーア法2
第3章 文字列検索アルゴリズムの比較
第4章 演習:ボイヤー・ムーア法のプログラム

この回の課題
・小テスト
 
第9回 1)タイトル:
再帰アルゴリズム

2)学習目標:
・再帰呼び出しの仕組みを理解する
・再帰呼び出しを利用したプログラム作成を体験し、再帰アルゴリズムについて理解を深める

3)目次:
第1章 再帰呼び出し
第2章 ユークリッドの互除法
第3章 ハノイの塔
第4章 演習:再帰を利用したプログラム

この回の課題
・小テスト
 
第10回 1)タイトル:
高度な並べ替え1~クイックソート~

2)学習目標:
・クイックソートのアルゴリズムを理解する
・クイックソートによる並べ替えを体験し、クイックソートの特徴と性能について理解する

3)目次:
第1章 クイックソート1
第2章 クイックソート2
第3章 クイックソートの性能
第4章 演習:クイックソートのプログラム

この回の課題
・小テスト
 
第11回 1)タイトル:
高度な並べ替え2~マージソート~

2)学習目標:
・マージソートのアルゴリズムを理解する
・マージソートによる並べ替えを体験し、マ―ジソートの特徴と性能について理解する

3)目次:
第1章 マージソート1
第2章 マージソート2
第3章 マージソートの性能
第4章 演習:マージソートのプログラム

この回の課題
・小テスト
 
第12回 1)タイトル:
データ構造1~リスト~

2)学習目標:
・リスト構造について理解する
・リストを利用したプログラム作成を体験し、リストについての理解を深める

3)目次:
第1章 動的メモリ確保
第2章 リスト
第3章 リストの応用
第4章 演習:リストを利用したプログラム

この回の課題
・小テスト
 
第13回 1)タイトル:
データ構造2~スタックとキュー~

2)学習目標:
・スタックについて理解する
・キューについて理解する
・スタックとキューを利用したプログラム作成を体験し、これらについて理解を深める

3)目次:
第1章 スタック
第2章 キュー
第3章 リストによる実装
第4章 演習:スタックとキューを利用したプログラム

この回の課題
・小テスト
 
第14回 1)タイトル:
データ構造3~ツリー~

2)学習目標:
・ツリーについて理解する
・ツリーを利用したプログラム作成を体験し、理解を深める

3)目次:
第1章 木構造
第2章 二分探索木
第3章 木の巡回法
第4章 演習:ツリーを利用したプログラム

この回の課題
・小テスト
 
第15回 1)タイトル:
データ構造4~ハッシュ~

2)学習目標:
・ハッシュについて理解する
・ハッシュを用いたプログラム作成を体験し、理解を深める

3)目次:
第1章 ハッシュ法の概要
第2章 ハッシュ法の実装
第3章 学習の振り返り
第4章 演習:ハッシュを利用したプログラム

この回の課題
・小テスト
 

ページの先頭へ戻る

open

Now Loading