「情報教育の研究」5回目の講義の概要は以下のとおり。
先週の引き続き。
1) CPUのふるまい その２
先週は、あまりうまく説明できなかった人が多かったので、再度、挑戦。
一般に、CPUは、どのように動作するのか、CPUを主語にして、CPUの振る舞いについて、各自(自分の言葉で)説明を試みる。
2) プログラムとは
「プログラムとは、コンピュータへの命令ではなく、コンピュータに
何をしてほしいか、人に説明することだ。」
ドナルド・E・クヌース (スタンフォード大学名誉教授)
3) アルゴリズムとデータ構造 その2
多くのプログラムは，アルゴリズムの記述とデータ構造の記述から
構成される．
アルゴリズム： 問題の解き方、操作や処理の手順
最初は、自然言語の文章で考え、記述される。
次に、擬似言語のプログラム等で記述される。
次に、プログラミング言語で記述される。
データ構造： 問題の対象となるモノの定義
最初は、何らかの等のモデルの形で記述される。
次に、抽象化したデータの集まりとして記述される。
次に、プログラミング言語のデータ定義として記述される。
4) アルゴリズムとデータ構造の簡単な例
三角形の面積を求める方法
アルゴリズム： 問題の解き方、操作や処理の手順
底辺 x 高さ を計算し、それを、1/2 する。
menseki = ( teihen * takasa ) / 2
menseki = ( teihen * takasa ) * 0.5 多くの場合こちらが速い
データ構造： 問題の対象となるモノの定義
底辺は、整数で、cm で表す。高さは、整数で、cm で表す。
面積は、整数で、cm2で表す。
int teihen, takasa, menseki;
5) アルゴリズムと計算量
問題の性質によっては、解法、解答が得られるとは限らない。
解き方が判らない。
定式化されたアルゴリズムが知られていない。
発見的方法でしか解くことができない。
NP-完全問題
解き方は判るが、手持ちの資源では計算できない。
実用にならないほど、計算時間が長い場合。
メモリ等が不足する場合。
6) データ構造
考え方
抽象化して考える
問題を構成する要素
問題の対象となるモノ
問題の対象となるモノの属性
同じ属性をもつモノは同種のデータとして扱える
オブジェクト (object)
動作や処理の対象
データを「生き物」のようにとらえる
オブジェクトは自律的に動く
オブジェクトは自分の処理の仕方を知っている
=> データの中に、そのデータの処理方法が含まれる
プログラミング言語の上では
データの属性 => データの入れ物
データの入れもの並べ方
例) 配列
データの入れ物のグループ化
例) 構造体
データの入れ物のグループの並べ方
例) 構造体の配列
[宿題]
以下の内容について、レポートする。
コンピュータ・ソフトウェアの構造について、知らべ、以下の3つの項目を含む形で、
アルゴリズムおよび制御構造
データ構造
モジュール構造
解説する。
800-1600文字程度レポート(A4ワープロ横書き)にまとめ、
次回、講義開始時に提出すること。
レポートのスタイルは以下のとおり。
学籍番号 学年 学科 氏名 提出年月日
まえがき
本文
ソフトウェアの構造
まとめ
参考文献
[参考書]
「アルゴリズム」を基本にすえてまとめられた、コンピュータサイエンスの古典的な入門書。アルゴリズムとOSやCPUのアーキテクチャの関係についても言及。
アルゴリズムとデータ構造についての古典的名著。プログラミングの実用的参考書でもある。職業的ソフトウェア技術者を目指す人には必読の参考書。
翻訳は版元品切れだが、古書をさがして購入する価値のある名著。
pascal言語開発者によるアルゴリズムとデータ構造についての古典的名著。プログラミング学習者必読の一冊。
日本語で書き下ろされたアルゴリズムと計算量についての入門書の定番。
国産ファイルアーカイブソフト LHAのアルゴリズム開発者による、アルゴリズム事典。
情報科学の基礎で現れるアルゴリズムをRubyで解説してる。(一部Javaのプログラムもあり。）Rubyの2冊目、3冊目の参考書としても読める。
先週の引き続き。
1) CPUのふるまい その２
先週は、あまりうまく説明できなかった人が多かったので、再度、挑戦。
一般に、CPUは、どのように動作するのか、CPUを主語にして、CPUの振る舞いについて、各自(自分の言葉で)説明を試みる。
2) プログラムとは
「プログラムとは、コンピュータへの命令ではなく、コンピュータに
何をしてほしいか、人に説明することだ。」
ドナルド・E・クヌース (スタンフォード大学名誉教授)
3) アルゴリズムとデータ構造 その2
多くのプログラムは，アルゴリズムの記述とデータ構造の記述から
構成される．
アルゴリズム： 問題の解き方、操作や処理の手順
最初は、自然言語の文章で考え、記述される。
次に、擬似言語のプログラム等で記述される。
次に、プログラミング言語で記述される。
データ構造： 問題の対象となるモノの定義
最初は、何らかの等のモデルの形で記述される。
次に、抽象化したデータの集まりとして記述される。
次に、プログラミング言語のデータ定義として記述される。
4) アルゴリズムとデータ構造の簡単な例
三角形の面積を求める方法
アルゴリズム： 問題の解き方、操作や処理の手順
底辺 x 高さ を計算し、それを、1/2 する。
menseki = ( teihen * takasa ) / 2
menseki = ( teihen * takasa ) * 0.5 多くの場合こちらが速い
データ構造： 問題の対象となるモノの定義
底辺は、整数で、cm で表す。高さは、整数で、cm で表す。
面積は、整数で、cm2で表す。
int teihen, takasa, menseki;
5) アルゴリズムと計算量
問題の性質によっては、解法、解答が得られるとは限らない。
解き方が判らない。
定式化されたアルゴリズムが知られていない。
発見的方法でしか解くことができない。
NP-完全問題
解き方は判るが、手持ちの資源では計算できない。
実用にならないほど、計算時間が長い場合。
メモリ等が不足する場合。
6) データ構造
考え方
抽象化して考える
問題を構成する要素
問題の対象となるモノ
問題の対象となるモノの属性
同じ属性をもつモノは同種のデータとして扱える
オブジェクト (object)
動作や処理の対象
データを「生き物」のようにとらえる
オブジェクトは自律的に動く
オブジェクトは自分の処理の仕方を知っている
=> データの中に、そのデータの処理方法が含まれる
プログラミング言語の上では
データの属性 => データの入れ物
データの入れもの並べ方
例) 配列
データの入れ物のグループ化
例) 構造体
データの入れ物のグループの並べ方
例) 構造体の配列
[宿題]
以下の内容について、レポートする。
コンピュータ・ソフトウェアの構造について、知らべ、以下の3つの項目を含む形で、
アルゴリズムおよび制御構造
データ構造
モジュール構造
解説する。
800-1600文字程度レポート(A4ワープロ横書き)にまとめ、
次回、講義開始時に提出すること。
レポートのスタイルは以下のとおり。
学籍番号 学年 学科 氏名 提出年月日
まえがき
本文
ソフトウェアの構造
まとめ
参考文献
[参考書]
「アルゴリズム」を基本にすえてまとめられた、コンピュータサイエンスの古典的な入門書。アルゴリズムとOSやCPUのアーキテクチャの関係についても言及。
 | 計算機科学入門 |
| L. ゴールドシュレーガー,A. リスター | |
| 近代科学社 |
アルゴリズムとデータ構造についての古典的名著。プログラミングの実用的参考書でもある。職業的ソフトウェア技術者を目指す人には必読の参考書。
翻訳は版元品切れだが、古書をさがして購入する価値のある名著。
| [表紙画像なし] | データ構造とアルゴリズム (情報処理シリーズ) |
| A.V. エイホ,J.D. ウルマン,J.E. ホップクロフト | |
| 培風館 |
pascal言語開発者によるアルゴリズムとデータ構造についての古典的名著。プログラミング学習者必読の一冊。
 | アルゴリズムとデータ構造 |
| N. ヴィルト,Niklaus Wirth | |
| 近代科学社 |
日本語で書き下ろされたアルゴリズムと計算量についての入門書の定番。
 | アルゴリズムと計算量 (計算機科学・ソフトウェア技術講座) |
| 野崎 昭弘 | |
| 共立出版 |
国産ファイルアーカイブソフト LHAのアルゴリズム開発者による、アルゴリズム事典。
 | C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー) |
| 奥村 晴彦 | |
| 技術評論社 |
情報科学の基礎で現れるアルゴリズムをRubyで解説してる。(一部Javaのプログラムもあり。）Rubyの2冊目、3冊目の参考書としても読める。
 | Rubyによる情報科学入門 |
| 久野 靖 | |
| 近代科学社 |
