情報科学A(11月11日分) ソフトウェアシステム 　　　　　　　　　　　　　　　　　　　　　　　　佐藤尚

主要なソフトウェア

• OS(Operating System)：基本ソフトウェア •  ハードウェアを管理し、アプリケーションを実行させるため

• アプリケーション(Application)：応用ソフトウェア •  特定の作業を行うことを目的としたソフトウェア

• 商用のソフトウェア •  商品として売ること目的 •  ソースコード（内部の動作）は不明（公開されていない）

• オープンソース •  ソースコードが公開されている •  売ることを考えていない •  GPLライセンス、BSDライセンス

OS

•  1950年頃はOSとアプリケーションに違いはなかった • 初期のコンピュータでは、操作員がアプリケーションの読み込みや実行のコントロールをおこなっていた

• これをプログラム化したものがOS •  面倒なことはコンピュータに作業させる •  人間はポカミスをするもの

• ハードウェアの進化にともなって、OSも高機能化 •  UNIX verison6:9000行程度(1975年頃)−＞色々な拡張が行われる •  Linux:1000万行程度？、kernel.org •  Windows7:1億行程度？

• ある時期までは、OSはハードウェアを製作した会社が提供するものということが常識であった •  UNIXの登場がこの常識を崩していく

最近のコンピュータシステム

• CPU、メモリ、ディスク、ディスプレイ、ネットワークインターフェースなどを管理する必要がある

• 複数のプログラムを同時に実行させる • 面倒なことはコンピュータにやらせる：OSの役割 • さまざなOS

•  Windows：色々な種類がある、XP,98,7,8など •  UNIX系

•  MacOSX:Mac •  iOS:iPhone,iPad •  Linux:PCむけ、Android、Kindleなど •  大型機向け

•  その他

OSの役割

• コンピュータ上の資源割り当て • CPU

•  スケジューラ • メモリ

•  メモリ保護機能(ハードウェアの機能？) •  バーチャルメモリ（仮想記憶） •  スワッピング

• ファイル •  ファイルシステム

• ウインドウシステムorグラフィックス • ネットワーク • カーネル：OSの中核的な機能

ファイルシステム

• フォルダ（ディレクトリ）の管理 • CDやハードディスクないのファイルをフォルダの階層として見えるように管理

• 読み書きなどのアクセスを管理 • ディスクファイルシステム

•  ブロックで管理 •  ファイルの削除

http://itpro.nikkeibp.co.jp/article/lecture/20061220/257410/より

A:トラック B:セクタ C：トラックセクタ D:クラスタ

仮想OS

• OSの上で別なOSを動かすための仕組み • VMWare • Paralles • Xen

•  オープンソースとして開発されている

• 仮想マシン •  コンピュータのハードウェアをそっくりまねするソフトウェア •  ゲーム機のエミュレータは仮想マシン •  WebブラウザにはJavascriptやJavaプログラムを実行する仮想マシン

が内蔵されている

OSの動作

• ブート •  コンピュータの電源がONとなったときの動作 •  OSをコンピュータ内に読み込み、実行をさせる

• OSの動作 •  発生したイベントに応じて、必要な処理を行う

• システムコール •  ハードウェアとOS以外のソフトウェアとのインターフェース

• デバイスドライバ •  OSと特定のハードウェアとの仲介役として動作するソフトウェア

アプリケーション

• OSを土台として、何らかの作業をこなすソフトウェア

ソフトウェアの階層

• ソフトウェアシステムは階層構造で構成されている • 階層構造で複雑さに対応

アルゴリズム

• 問題を解くための手順 • 目的を達成出来ること • 処理が停止すること

• 焼きそばを作る手順 1. キャベツや肉などの具を適当な大きさに切る 2. キャベツや肉などの具をフライパンで炒める 3. プライパンからいったん具を取り出す 4. 麺をフライパンで炒める 5. 具を麺のはいっているフライパンに戻す 6. 焼きそばソースを加えてさらに炒める

ATMを使う手順（アルゴリズム） • 処理の種類（入金、引き出し、送金、残高確認）を選ぶ

• カードを入れる • 暗証番号を入力 • 選択した処理を実施

• 入金の場合 • お金を入れる • 入金額の確認

• 引き出しの場合 • 引き下ろし額を入力 • お金を取り出す

• 終了

難しい問題はどのように解く

• 計算量の理論 • 難しい＝解答を見つけるのに時間がかかる • NP問題

•  組合せ最適化問題 •  巡回セールスマン問題 •  ナップザック問題

• 問題（入力データ）の特殊性を利用する • 近似解で我慢する

•  確率的な方法もある

SUICA,PASMOの鉄道料金 • 計算で料金を求めている • かなり複雑な計算になる

•  定期券の併用 •  経由駅の関係

• 自動改札機の運賃計算プログラムはいかにデバッグされているのか？ 10の40乗という運賃パターンのテスト方法を開発者が解説（前編） •  http://www.publickey1.jp/blog/12/_1040.html

プログラムを作る

• 分割統治法、再帰法（落語：頭山） • 与えられた問題をいくつかのできるだけ独立な副問題に分割する •  これらの副問題が解けると仮定できれば、最初の問題に対する概要が得られる

• 副問題に一つ一つあたって別々に解く •  簡単なら、最終解を書く •  難しければ、副問題にさらに副問題に分割する

• あとに残った副問題がすべて簡単なものばかりになるまで、この作業を繰り返す

• 副問題の最終解をすべて組み合わせれば、最初の問題に対する答が完成!!

プログラムを作る

• 自然言語（例えば、日本語）による文章化を行う • 詳細化された文章に対応するプログラミング言語の命令文で置き換える

•  すべての操作は、一連の操作か、反復か、あるいは選択の組み合わせで書ける（構造化定理）

プログラミング言語

• 自然言語とプログラミング言語の違い • 文法がきちんと決まっている • バグ（bug）：プログラムのミス

•  文法のエラー •  実行時のエラー •  論理のエラー

• デバッグ

機械語

• 一番原始的 • コンピュータの中では、全ての情報が数字（２進数）で表されている。 •  当然、プログラムも数字で表される

• 例えば、 •  +:70 •  -:75 •  *:85 •  データを読み込む:72

機械語

主記憶

番地 内容

1 5

2 8

3 40

1番地にある数字と2番地にある数字のかけ算を行い、3番地にしまう。

85 1 2 3

プログラミング言語とは

• なるべく簡単にコンピュータに命令を出せるように • コンピュータが理解出来るような命令を作るために、人工的に作られた言語

アセンブリ言語

•  85(*)の代わりに、mul(multiplyの略)などと書けたら便利 • データを記憶している場所も名前で書けたら便利

mul tanka suryo kingaku

もう少し人間にわかりやすく書けないか？

•  Fortranが開発 •  1954年にJ. W. Backusが開発 •  Kingaku = tanka * suryoなどと書ける

• これをきっかけに色々なプログラミング言語が作られる

Fortran

•  Fortran = Formula Translator •  1972年にISOがFORTRAN66を規格として制定。その後も、改訂が繰り返される。

• 科学技術計算に向いているとされている

sum=0 Do 10 I = 1,100 sum = sum + I 10 continue

1から100までの和を計算する

Cobol • Common Business Oriented Language • CODASYL • 英文に近い形でプログラムが書ける • 事務計算向けとされている

perform varifying i from 1 by 1 until i>100 compute summ = summ+I End-perform

1から100までの和を計算する

Pascal

•  1971年にN. Wirthにより開発される • プログラムをわかりやすくするための工夫（構造化プログラミング）が取り入れられている

sum:=0 For i:=1 to 100 begin sum := sum+i end

1から100までの和を計算する

BASIC

•  1964年にJ.G.Kemenyらによって開発 • Beginner’s All-purpose Symbolic Instruction Code

10 let sum=0 20 for i=1 to 100 30  sum = sum+i 40 next i

1から100までの和を計算する

C

•  1973年頃にD. Ritchieらが開発 • UNIXというOSを開発するために作られた • 色々な機種で利用できる（移植性が高い）、プログラムが簡潔に書けるという特徴がある

• C言語を拡張した拡張したC++,Objective-Cも利用されている

sum=0 for(i=1;i<=100;i++){ sum += i; }

1から100までの和を計算する

Java

•  1995年にSun社(Oracle)から発表されたオブジェクト指向型プログラミング言語で、Cに似ている

• Webブラウザ上で動かすappletというプログラムを作成できることが注目される

• 様々な機械で動く（移植性が高い）、仮想機械 • Androidで使われている

sum=0 for(i=1;i<=100;i++){ sum += i; }

1から100までの和を計算する

Javascirpt • 主にWebブラウザに実装され、動的なウェブサイト構築や、リッチインターネットアプリケーションなど高度なユーザインタフェースの開発に用いられることが多い。

•  1995年頃開発され、当初はLiveScriptと呼ばれていた。 • AJAX:ウェブブラウザ内で非同期通信とインターフェイスの構築などを行う技術の総称

• HTML5+JAVASCRIPTが最近のはやり •  Flashは消えつつある？

PHP

• 動的にHTMLデータを生成することによって、動的なウェブページを実現することを主な目的としたプログラミング言語

• Webサーバ上で動作し（サーバサイド）、そのPHPスクリプトが実行され、結果をウェブブラウザに対して送信する。

• 文法は簡単だと言われている •  イディオム（？）が多い？

• 大規模な開発にも用いられることが多い

Lisp

•  List Processor •  1950年代後半に開発された関数型言語 • 人工知能向きと言われている

(defun sum (n) (if (zerop n) 0 (+ n (sum (- n 1))))) (sum 100)

1から100までの和を計算する

Prolog

•  Programming in Logic •  1973年にColmerauerらによって、自然言語処理のために開発された論理型言語

• 人工知能向きと言われている

sum(0,0). sum(I,S) :- I1 is I-1, sum(I1,S1), S is S1+I. sum(100,S).

1から100までの和を計算する

Prolog

• 事実と規則から推論を行えるのが特徴

on(oyagame,kogame). on(kogame,magogame). on(magogame,himagogame).

above(X,Y) :- on(X,Y). above(X,Y) :- on(X,Y), above(Y,Z).

?- above(oyagame,himagogame). Yes ?- above(X,Y). X = oyagame,Y=kogame. X = kogame,Y = magogame X = magogame,Y = himagogame X = oyagame,Y=magogame X = kogame,Y = himagogame X = oyagame,Y = himagogame

プログラミング言語の分類

•  1980年の時点で200種類上のプログラミング言語が利用されているといわれている

• 水準 • 高水準：Fortran,C,Javaなど • 低水準：機械語、アセンブリ言語

• 処理形態 • 手続き型言語:Fortran,Cobol,C,C++,Java • 関数型言語:Lisp,Haskel • 論理型言語:Prolog • オブジェクト指向型言語:C++,Java,smalltalk

Forth系言語

• すべてのコマンド(WORD)は辞書で管理する • 新たなコマンド(WORD)を自己定義して、これを辞書に登録して、機能を追加する

• 逆ポーランド記法 •  10 + 20 •  10 20 + •  10に 20を　足す

日本語によるプログラム例

午前？とは　　　　　　　　　　　　　　　　　 　　　　

時刻を得て　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　

時が １２より 小さいこと。　

←「午前？」の定義　

メインとは

午前？

ならば　「おはよう」を

さもなければ

「こんにちは」を

つぎに

表示し　改行すること。　

←「午前？」の引用

プログラミング処理系

• アセンブラ •  アセンブリ言語を機械語に翻訳

• コンパイラ •  高水準言語を機械語に翻訳

• インタプリタ •  プログラミング言語を逐次翻訳をしながら実行

プログラミングの学習

• プログラムを作ることは難しい •  個人差が大きい？ •  The camel has two humps：

www.eis.mdx.ac.uk/research/PhDArea/saeed/paper1.pdf

• 色々な工夫がされている •  Codespell:https://sites.google.com/a/eng.ucsd.edu/codespells/ •  前田ブロック：http://junk.wise9.jp/maedaj/

• ゲーミフィケーション •  ゲームデザインの技術やメカニズムを利用して学習などを行う