ガイダンス 2

Transcription

1 データ構造とアルゴリズム (a) 科目区分 : 専門科目電子物性工学コース ( 自由選択 ) 電気通信システム工学コース ( 自由選択 ) 時間割番号 :G2209 ソフトウェア工学 旧課程 科目区分 : 専門科目電子物性 エネルギー工学コース ( 選択 ) システム制御 通信工学コース ( 限選 ) 時間割番号 :33310 ( 第 1 週 ) ガイダンス ソフトウェアの基本概念とプログラミング言語

2 ガイダンス 2

3 目標 以下の項目について説明できること. また, 関連する基礎的なプログラムを作成できること. 関連授業 プログラミング基礎 (1 年生 ), 情報処理基礎 (1 年生 ), 学生実験 II III(3 年生 ), など ソフトウェアの基本概念とプログラミング言語ハードウェア,CPU,ALU, レジスタ, バス, メモリ,I/O, ソフトウェア,C 言語, 機械語, アセンブリ言語, など アルゴリズムとデータ構造アルゴリズム, 計算量,O 記法, データ構造, プログラム, 配列, リスト, ポインタ, グラフ, 集合,2 分木, ヒープ, 探索アルゴリズム, 整列アルゴリズム, など 3

4 授業方法 講義 13 回と演習 2 回 ( 期末試験 レポート課題あり ) 講義教科書と参考資料を用いて講義を行います. 教科書 : 茨木著 C によるアルゴリズムとデータ構造 ( オーム社 ) 演習教科書の各章終了後, プログラミング演習を行います. ( 共用講義棟情報処理演習室にて ) 4

5 評価方法 期末試験 (8 割 ), レポート課題 (2 割 ) 期末試験筆記試験にて目標の達成度を確認致します. レポート課題 (3 回 ) 教科書等の演習問題を含む課題 (1 回 ) プログラミング課題 (2 回 ). 5

6 評価方法補足 ( 念のため ) 欠席率 : 1/3 以内 ( 欠席 4 回以下 ) 福井大学工学部規定によって, 欠席が 5 回以上になると, 試験が受けられません. 6

7 資料等について 上記のページからレポート課題や授業資料がダウンロードできます. また,WebClass からでも資料のダウンロードができるようにしておきます. ( 注 ) お知らせ等あるときも, 上記のページに掲載致します. 7

8 ソフトウェアの基本概念とプログラミング言語 8

9 コンピュータ制御の利点 : 高性能, 高機能, 省エネ, 安全性, など 家電製品や自動車, 列車, 航空機など様々な工業製品は, コンピュータによる制御によって機能性の向上などが計られている

10 コンピュータの種類 : マイコン, ワンチップマイコン, スマートフォン, PC, ゲーム機, ワークステーション, スパコン, ワークステーション, サーバ, など マイコン (Microcomputer / Microprocessor) CPU やメモリを 1 つの LSI チップに集積した回路. 超小型のコンピュータを意味する マイクロコンピュータ の略称. 最近では家電製品などの制御に用いられる組み込み用小型コンピュータをマイコンと呼ぶこともある ワンチップマイコン (One-Chip Microcomputer / Microcontroller) マイコンの一種で ひとつの IC チップ上に CPU,RAM,ROM, 各種入出力装置などを搭載し, 電子機器の制御用に最適化されている. 家電製品や自動車の制御システムや, マウスやキーボードにおける入力情報の制御などにも用いられている. ワンチップマイコンやワンチップコンピュータとも言う

11 ハードウェア (Hardware) コンピュータを構成する物理的実態. 利点 : 処理速度. 欠点 : 変更の困難さ. hardware hard( 固い ),ware( 製品 ) ソフトウェア (Software) コンピュータを動作させるための手順 命令を ( それ自体は形を持たないプログラムやデータなど ) を記したもの. 利点 : 変更容易. 欠点 : 処理速度 Software Soft( 柔らかい ),ware( 製品 ) 書き換え可能なハードウェア PLD(Programmable Logic Device) はユーザが自前でプログラムを書き換えられる IC である. 大容量の FPGA と中小容量の CPLD の 2 つに大別される. 11

12 コンピュータのシステムはハードウェアとソフトウェアで構成される ハードウェア ソフトウェア OS(Operating System), ブラウザソフト, ワープロソフト, メールソフト, 表計算ソフト, ゲームソフト, 音楽ソフト, など

13 CPU(Central Processing Unit: 中央処理装置 ) コンピュータにおいて演算や制御を行う装置. プログラムを実行するために記憶装置からデータを取り出し その命令を解読して他の装置の制御や演算などの処理を実行するコンピュータの主要部分. 前者を制御装置, 後者を演算装置と呼ぶ. CPU が一度に処理できるデータ量はビット数で表される. ( 例 ) 4bitCPU,32bit CPU,64bitCPU, など CPU の動作周波数をクロック周波数とも呼ぶ.CPU の動作基準となる時間の単位であり, このクロックの整数倍の時間で命令が実行される. ( 例 )8MHz,450MHz,4GHz, など 13

14 CPU の内部構成演算装置 :ALU, アキュムレータ, フラグレジスタ, 汎用レジスタ制御装置 : プログラムカウンタ, 命令デコーダ, など ALU:Arithmetic and Logic Unit( 算術論理演算装置 ) の略称. アキュムレータ : 演算結果の出力先として主に使用される. フラグレジスタ : 演算結果 ( ゼロ, 正負, オーバーフローなど ) の状態を表す. 汎用レジスタ : 演算するデータを一時的に格納. フラグレジスタやプログラムカウンタなどの特定用途に用いられるレジスタに対して, 汎用レジスタは用途を限定せず, 様々な演算に用いられる. プログラムカウンタ : 次にフェッチ ( 読出 ) して解読 実行する命令のアドレス を格納. 命令デコーダ : 命令レジスタのデータを解読して, 制御信号を生成. 14

15 CPU の内部バスの種類アドレス バス, データ バス, コントロールバス アドレス バス : メインメモリや入出力装置に割り当てられたアドレスを指定してアクセスするための信号線. データ バス : メインメモリや入出力装置とデータをやり取りするために用いられる信号線. コントロール バス : メインメモリや入出力装置を制御したり, 外部から CPU を制御できるようにするための信号線

16 主記憶装置 ( メインメモリ ) 一般に,ROM と RAM の 2 種類の半導体メモリが使用されている ROM:Read Only Memory の頭文字. 変更する必要が無く また電源を切っても消えては困る常用のルーチンやデータを記憶するための読み出し専用のメモリ RAM:Random Access Memoryの頭文字. 随時に記憶データの読み出しや書き換えを行えるメモリ. パソコンでは, 交換や増設が可能なようにメモリスロットが取り付けられている. ( 例 ) メモリ空間 (1024バイト) 上の場所を指定するアドレス アドレス 内容 0H 1バイトのデータ 1H 1バイトのデータ 1フロアに1バイト (8ビット) の 2H 1バイトのデータデータが格納された1024 階 : : 建てのビルディング 3FEH 1バイトのデータ 3FFH 1バイトのデータ 16

17 情報量の単位 bit( ビット ), Byte( バイト ),Octet( オクテット ),nibble( ニブル ), および, 接頭辞 kb と kib との違いについて バイト ( 情報 ) 17

18 進数の対応表ハードウェアとソフトウェア 数値の表現方法 2 進数,16 進数, など 2 進数 8 進数 10 進数 16 進数 A B C D E F 18

19 ソフトウェアの起動と終了 1. アプリケーションソフトの起動 2. データファイルの読み込み 3. ソフトの作業 4. データファイルの保存 (Save) 5. ソフトの終了 バスライン CPU 中央演算処理装置 ソフト ソフト データデータ データデータ 外部メモリ ( ハードディスク ) メインメモリ (RAM) 19

20 プログラム言語低水準プログラミング言語と高水準プログラミング言語 ハードウェア ( コンピュータ ) を利用するためには. ソフトウェア ( プログラム ) が必要不可欠 ハードウェアは2 進数しか理解してくれない 人間は,2 進数だけでは理解しにくい ( 機械語 ) 2 進数 ハードウェアが理解可能 低水準プログラミング言語 アセンブリ言語 高水準プログラム言語 人間が容易に理解可能 20

21 機械語 ( マシン語,Machine Language) コンピュータが直接解読して作動することができる命令を用いた言語 機械語の命令は 2 進符号の組み合わせで構成される. 機械語を用いたプログラムをオブジェクトプログラムと呼ぶ. 以下のような命令が定義されている. ロードストア ロードアドレス命令 算術 論理演算命令 比較演算命令 シフト演算命令など C 言語サンプルファイル 21

22 アセンブリ言語 (Assembly Language) 機械語の命令を人間が容易に理解できる記号で表現した言語 一般に,CPU 種類によって機械語が異なるため, 機種間の互換性が保たれない. 高水準言語と比較して, プログラムサイズが小さい, 実行速度が速いとう長所があるが, 開発効率や保守性, 移植性に難点がある. 22

23 アセンブリ言語 (Assembly Language) 機械語の命令を人間が容易に理解できる記号で表現した言語 コンピュータに対する命令 2 進数 ( 機械語ともいう ) 例えば AとBを足しなさい と命令 ( コマンド実行 ) ,1の羅列で表現 もう少し分かりやすい表現 : アセンブリ言語 例えば AとBを足しなさい add A, B つまりアセンブリ言語とは 2 進数を直接書くよりは人間に分かりやすい コンピュータに対する命令 1 個について 1 行のアセンブリ言語が対応 23

24 高水準プログラミング言語人間の言語 概念に近づけて設計されたプログラム言語 アセンブリ言語でも分かりにくい より人間が理解しやすいほうがいい 例えば 高水準プログラミング言語 (high-level programming language) 2 進数 アセンブリ言語 = = add A,B 高水準言語 A+B 24

25 高水準プログラミング言語人間の言語 概念に近づけて設計されたプログラム言語 高水準プログラミング言語の例 言語名用途 ( 得意分野 ) C, C++ システム記述 COBOL Fortran Java 事務処理 科学技術計算 分散協調処理 LISP Perl, Ruby 記号処理 文字 ( テキスト ) 処理 25

26 高水準プログラミング言語人間の言語 概念に近づけて設計されたプログラム言語 プログラムは最終的には 2 進数 ( 機械語 ) に変換 アセンブラ (assembler) アセンブリ言語を 2 進数に コンパイラ (compiler) 高水準プログラミング言語をアセンブリ言語 or2 進数に アコセン 2 進数ンアセンブリパ高水準 ( 機械語 ) ブイララ 注意 : 高水準プログラミング言語から直接 2 進数に変換するコンパイラも存在する 26

27 高水準プログラミング言語人間の言語 概念に近づけて設計されたプログラム言語 C 言語 コンパイラ型高級言語 1970 年代後半 トンプソン & リッチーにより開発 BCPL( リチャーズ ) B( トンプソン ) C( リッチー ) UNIX 開発中に C 言語開発 C で UNIX を記述 移植性が高い言語 (ISO/IEC:1990 年 JIS:1993 年 ) 27

28 関連授業電気 電子工学実験 Ⅱ,Ⅲ 実験指導書参照 参考資料 28

29 関連授業 電気 電子工学実験 Ⅱ,Ⅲ 表面 CPU(NEC, mpd753108) 裏面 29