科目名 : 計算機ソフトウェア

科目コード 60370
配当学年 3年
開講期 前期
曜時限 火曜・2時限
講義室 電総大
単位数 2
履修者制限
講義形態 講義
言語
担当教員 黒橋禎夫

講義概要

計算機の各種プログラムの作成に不可欠な、基本的なデータ構造とそれらに関連する各種アルゴリズムについて学ぶ。

評価方法

講義中に出題する数回の課題と定期試験の成績を総合して評価する。

最終目標

計算機におけるデータ構造と各種アルゴリズム、プログラム技法を習得することにより、基本的な計算機プログラムの理解とデザインが健全に行えることを目標とする。

講義計画

項目 回数 内容説明
アルゴリズムと計算量 1 本講義の導入として、アルゴリズムとは何か、アルゴリズムの良さをどのように測るかについて説明する。
各種のデータ構造とアルゴリズム 3 基本的なデータ構造として、リストとヒープを取り上げ、それらの構造に対する基本的なアルゴリズムを学ぶ。
再帰呼出と分割統治 2-3 複雑な問題を、より単純な小問題に分割して解く方法について学ぶ。
グラフ探索 3 グラフ構造とその探索アルゴリズムについて学ぶ。
動的計画法 2-3 最適性の原理と動的計画法について学ぶ。
問題の難しさの測り方と難問対策・利用 3 問題自身の難しさを測る方法について説明する。また、難問の対策とそれを利用した公開鍵暗号系について学ぶ。最後に学習到達度の確認を行う。

教科書

杉原厚吉:データ構造とアルゴリズム(共立出版)

参考書

D.E.Knuth: The Art of Computer Programming, Addison-Wesley

予備知識

全学共通科目である基礎情報処理,基礎情報処理演習および,専門科目である電気電子プログラミング及演習(60620),計算機工学(60160)を修得しておくこと.

授業URL

http://nlp.ist.i.kyoto-u.ac.jp/member/kuro/lecture/CS14/

その他

当該年度の授業回数などに応じて一部省略,追加がありうる.