南山大学

 
指定
期間
秋学期
単位
年次
3
担当者
横森 励士
他の科目との関連
他学科履修
副題
授業概要 コンピュータ上で問題を解くための基礎的な知識として、基本的なデータ構造とアルゴリズムについて、その概念や考え方について学ぶ。授業では、計算モデルやアルゴリズムの評価法などの基本事項を解説し、代表的なアルゴリズムやデータ構造を示しながらそれらの手法の評価を行う。また、分割統治法や動的計画法などのアルゴリズムの基本的な設計技法を学ぶことで、コンピュータ上で問題を効率よく解く素養を身につける。
学修目標 1.計算量の議論において用いられる概念を説明できる。
2.基本的なアルゴリズムやデータ構造の概要やその計算量について知っている。
3.様々なソーティングアルゴリズムの原理を理解し、どのように動作するかを知っている。
4.様々なソーティングアルゴリズムの違いを理解し、長所や短所を説明できる。
5.様々なデータ構造の仕組みを理解し、どのように動作するかを説明できる。
6.分割統治法や動的計画法などのアルゴリズムの設計技法について知っている。
授業計画 第1週 導入(アルゴリズムとは)
第2週 アルゴリズムの計算量
第3〜6週 ソーティングアルゴリズム
      バブルソート、基数ソート、クイックソート、マージソートなど
第7〜8週 基本的なデータ構造と木:リスト、スタック、キュー、木、二分木
第9〜11週 データの探索を利用したアルゴリズム
      二分探索木、平行二分探索木、ハッシュ、ヒープとヒープソート
第12〜14週 アルゴリズムの設計技法:貪欲法、分割統治法、動的計画法
第15週 定期試験
評価方法 授業毎に小テストを行う。小テスト35%、定期試験65%で評価する。
テキスト 茨木 俊秀(著)、Cによるアルゴリズムとデータ構造、昭晃堂、1999。
ただし、次の本も認める。
茨木 俊秀(著)、アルゴリズムとデータ構造、昭晃堂、1989。

【その他】この科目は、次のJABEE対応コース「情報技術専修コース(情報通信学科・情報システム数理学科)」の学習・教育目標に対応する。(D)
その他