講義コード	9419J
講義名	アルゴリズム
(副題)
開講責任部署	全体
講義開講時期	秋学期
講義区分
基準単位数	2.00
時間	0
代表曜日	水曜日
代表時限	１時限
開講学科	情報処理学科
必選別	選択
履修セメスター	第2セメスター
その他	e-Learning履修可
担当教員
職種 氏名 所属 准教授 ◎ 宮川　幹平 （指定なし）

講義概要

コンピュータに対して、情報を処理し問題を解決させる指示・命令群をプログラム、プログラムを開発することをプログラミングと呼ぶ。本講義は、プログラミング技術を学ぶ上で不可欠となる「アルゴリズムとデータ構造」について学ぶ科目である。 　コンピュータは曖昧さを苦手とする。人間が柔軟に対処できることでも、明確な手順が指示されていなければ、コンピュータに仕事をさせることはできない。ここでいう“明確な手順”がアルゴリズムである。そしてもうひとつ、コンピュータに情報を扱わせる場合には、扱いたい情報をコンピュータ上でどのように表現するか、その構造（データ構造）も考えなければならない。プログラミングの実際においては、処理の内容や状況に応じて適切なアルゴリズムとデータ構造を検討する必要が生じる。つまり、「アルゴリズムとデータ構造」こそが、プログラムの両輪となるのである。 　本講義では、コンピュータにおける情報の処理方法についてその基本から学習し、いくつかの代表的なアルゴリズム・データ構造を例にあげながら、アルゴリズムの動きを検証・理解する方法、及びその性能評価法を学習することで、エンジニアとして必須の論理的な思考・構成能力を高める。

到達目標

アルゴリズムとデータ構造とは何かという根本を理解した上で、基本的な処理の流れを流れ図や擬似言語で表現できる。また他者のアルゴリズムをトレースすることで、そのアルゴリズムの動作と意味を理解できる。 　さらに、探索と整列の代表的なアルゴリズムについて、そのアイデアと特徴を理解し、アルゴリズムとして表現できる。また、配列・リンクトリスト・スタック・キュー・ヒープなどの代表的なデータ構造の特徴を説明でき、アルゴリズムに利用することができる。

履修のポイント及び留意事項

本授業は、情報処理技術者試験「基本情報技術者試験」における、アルゴリズム、プログラム設計、プログラム作成能力に関する内容に関係するほか、本学が実施する「基本情報技術者試験」午前試験免除認定講座の一部である。 　また、e-Learningとして履修する場合は、担当教員に事前に申し出るとともに、教材の閲覧や課題の提出だけでなく、定期的なメンタリング指導を受けることが求められることに留意すること。授業の一部をe-Learningで履修することも可能であるので、担当教員と相談すること。

講義日程

週 テーマ 内容 第1週 入門：アルゴリズムとデータ構造 プログラミングの流れとアルゴリズム・データ構造の重要性について学ぶ。その他、信頼性や計算量など、アルゴリズムの評価指標について理解を深める。 第2週 アルゴリズムの基本と構造化定理 変数の概念を理解し、入力・計算と代入・出力の基本的な処理単位を組み合わせた単純なアルゴリズムを表現する。また、アルゴリズムのトレース手法について理解を深める。 その他、アルゴリズムの基本構造（順次・選択・繰り返し）と構造化定理について理解する。 第3週 選択構造による条件分岐の表現 比較演算・論理式の意味とあわせ、選択構造を用いた条件分岐（二分岐・多分岐）の表現方法を学ぶ。 第4週 繰り返し構造と配列 繰り返し構造の表現方法を学ぶ。また、１次元配列の概念を学ぶとともに、配列の初期化や配列要素の合計など、繰り返し構造を活用したアルゴリズムについて理解を深める。 第5週 多重ループとループ制御 多重ループの表現方法とその活用について、二次元配列などを例として理解を深める。 第6週 演習：基本的なアルゴリズムの表現 これまでの内容について演習問題を通じて理解度を確認する 第7週 データ構造(1) リスト構造（連結リスト・双方向リスト・順序付きリストなど）の仕組みと特徴、基本操作について学ぶ 第8週 データ構造(2) スタックとキュー、グラフやツリーなどの問題解決向きデータ構造について、その特徴と基本操作を学ぶ 第9週 探索(1) 探索アルゴリズムとして線形探索法と二分探索法のアイデアとアルゴリズムを理解する 第10週 探索(2) 効率的な探索を可能とするデータ構造（二分木・B木など）について理解を深める 第11週 整列(1) 整列の基本概念（整列キー、安定整列など）とともに、基本的な整列アルゴリズムとして「基本選択法」「基本交換法」について学ぶ。 第12週 整列(2) 「基本挿入法」と「シェルソート」について学ぶ。 第13週 モジュールと再帰 処理をモジュール化することの利点について再確認するとともに、再帰の概念・特徴を学ぶ。また、再帰を活用したアルゴリズム表現を演習する。 第14週 その他のアルゴリズム その他の整列アルゴリズム（クイックソート・マージソート・ヒープソート・基数ソート）や有用なトピックを紹介する。 第15週 定期試験 上記授業内容に関して、記述式の筆記試験を実施し、その内容理解度を測る。

他の授業科目との関連

本授業で学んだアルゴリズムとデータ構造を、各プログラミング言語で実際に実現（実装）することは、内容理解の上で非常に重要である。ゆえに、プログラミング関係の授業「プログラミング基礎」「プログラミング1」「プログラミング2」を受講することを強く推奨する。 　また、「情報基礎」「コンピュータシステム」「コンピュータネットワーク」「データベース」によって、現代のコンピュータシステムの技術的な仕組みについて知ることは、さらにプログラミングの理解を深めることに繋がる。 　そのほか、ソフトウェア開発プロセス全体について学ぶ「システムマネジメント」を履修すれば、システム開発におけるプログラミングの位置づけが明確になることが期待される。

評価方法

平常点（出席・課題等）30%＋定期試験結果70%を基本点として、授業への取り組み姿勢を勘案した総合評価を行う。

教科書

明解C言語によるアルゴリズムとデータ構造（ソフトバンククリエイティブ）

ISBN番号

978-4797348439

参考図書

平成23年度イメージ＆クレバー方式でよくわかる栢木先生の基本情報技術者教室 （技術評論社） アルゴリズムC(新版) 著者：R.セジウィック （近代科学社） 基本情報技術者　大滝みや子先生のかんたんアルゴリズム解法　〜流れ図と擬似言語〜（技術評論社）

オフィスアワー(授業相談)

随時、宮川の研究室に直接訪問して良い。また、Web教材における質問相談フォーラムを活用することを推奨する。

学生へのメッセージ

プログラミング関係の授業にも関わらず「コンピュータを触らない」ことに違和感を感じるかもしれない。闇雲にコンピュータの前に座ってキーボードを叩いているだけでは、良いプログラムを作成することはできないということを、この授業を通じて理解して欲しい。 　プログラマやシステムエンジニア、もしくは情報工学分野への進学を検討している学生には受講を強く推奨する。

授業用E-mail

miyakawa@ftokai-u.ac.jp