勉強その1

基本情報技術者試験を受けることにしたので、気が変わらないうちに早速今日勉強したことを書いてみる。
ちなみに教材はこれ

基本情報「午前」完全合格教本〈2007年度版〉 (情報処理技術者試験)

結構前に買ってあった本だけど、2007年度版だし、そんなに古くなってるとは思わないから採用した。

コンピュータの機能

・ハードウェアとソフトウェア
ハードウェア―物理的な装置。簡単に言えばコンピュータの機械の部分のこと。
ソフトウェア―ハードウェアを動かすためのプログラムのこと。設計書やマニュアルなども含む。

・コンピュータの特徴
１．高速性―超高速演算ができる
２．正確性―常に安定した結果を出す
３．記憶性―大量にデータを管理できる
４．汎用性―活用分野が広い
汎用性があるおかげで、一台のパソコンでワープロが打てたりゲームができたりインターネットができたりするわけ。

コンピュータの利用

コンピュータで行う仕事を処理という。

・利用形態の分類
１．定型処理―決められた手順で繰り返し行う処理のこと。文字通りに「型で定まった処理(を繰り返す)」と考えてみるとちょっと覚えやすい気がする。
２．非定型処理―毎回異なる手順で行う処理のこと。ワープロでの文書作成などがその例。

・企業の情報処理システム
１．オフィス・オートメーション(OA)―事務処理の自動化
２．ファクトリ・オートメーション(FA)―工場の自動化
３．EUC(End User Computing)―エンドユーザ(利用者)が自らコンピュータを活用する
４．EUD(End User Development)―エンドユーザが情報処理システムを開発する

・ネットワークで広がる利用価値
１．集中処理型のネットワーク―1台のホストコンピュータが集中制御する。たとえば銀行のオンラインシステムなど。
２．分散処理型のネットワーク―複数のコンピュータが互いに協調制御する。たとえばインターネットなど。

・身近な情報処理システムの例
銀行のCDやATM、電子商取引などなどいっぱいある。

今日はここまで。試験は4月だからあとおよそ4ヶ月ある。まあまだ時間はあるけど。直前にあせって徹夜で勉強するってのは嫌だからちょっとづつ勉強を進めていこうと思う。

勉強その2

毎日少しずつ勉強。継続が肝心だ(｀・ω・´)

コンピュータの種類

１．マイクロコンピュータ(マイコン)
・1個から数個のLSI(大規模集積回路)で構成される処理装置を家電製品や自動車などに組み込み、制御に用いる小さなコンピュータ。
２．パーソナルコンピュータ(パソコン)
・マイクロコンピュータを組み込んで、個人利用をおおな目的として開発されたコンピュータ。
３．ワークステーション(WS)
・高解像度ディスプレイを備え、パソコンよりも高速な処理能力を持ち、通常ネットワーク携帯で利用される業務目的の個人用コンピュータ。
・LAN(Local Area Network)やインターネット環境では、サーバとして利用されることも多い。
・研究やプログラム開発など、主として技術者(エンジニア)が使うものを、エンジニアリング・ワークステーション(EWS)と呼ぶ。
４．汎用コンピュータ(メインフレーム)
・事務計算から科学技術計算まで、幅広い分野で利用できる高度な処理能力を持つコンピュータ。
・ホストコンピュータとして、複数の端末装置を接続して共同利用する。
５．スーパーコンピュータ
・原子力発電所や気象予測など、膨大な科学技術計算を極めて短時間で行える、超高速な汎用コンピュータ。

特殊目的コンピュータ

１．オフィスコンピュータ(オフコン)・オフィスでの事務処理を、簡単に行えるようにしたコンピュータ。
２．制御用コンピュータ(プロセスコンピュータ、プロコン)
・工場の生産ラインの監視や制御などを行うコンピュータ。
・汎用コンピュータよりも小型のミニコンピュータ(ミニコン)などが用いられることが多い。

コンピュータの構成

コンピュータの五大装置
１．制御装置―主記憶装置上の命令に従って、各装置を制御する。
２．演算装置―各種演算を行い、結果を主記憶装置に格納する。
３．主記憶装置(main storageまたはメインメモリ(main memory))―データやプログラムを記憶する。
４．入力装置―データやプログラムを主記憶装置に読み込む。
５．出力装置―主記憶装置上のデータを外部に送り出す。

・処理装置とは、制御装置と演算装置、あるいは主記憶装置までを含めた総称。
・周辺装置とは、入力装置、出力装置、補助記憶装置の総称。
・パソコンでは、制御装置と演算装置の機能が1つのLSIに組み込まれており、このLSIをMPU(Micro Processing Unit)、あるいはCPU(Central Processing Unit)と呼ぶ。
・主記憶装置の情報は電源を切ると消えてしまうので、データを保存するのにハードディスクなどの補助記憶装置を用いる。補助記憶装置は、データを読み書きする速度は遅いが、主記憶装置よりも大きな記憶容量を持つ。

今日はここまで。目標は毎日継続だ。

アルゴリズムの正しさ

　プログラムの勉強をしていると必ずぶつかるのがアルゴリズムという言葉。このアルゴリズムとは一体何なのかというと、問題を解くための手順を定めたものだ。この手順をきちんと定めればコンピュータに問題を解かせることができる(もちろんアルゴリズムはコンピュータに限った話ではないけど)。

ここで、どういうアルゴリズムが正しいアルゴリズムなのかということを知らなくちゃいけない。正しいアルゴリズムの条件とは次のようなものだ

(1)どんな入力データに対しても間違った答を与えないこと、言い換えると、答を与える場合にはその答が正しいこと。
(2)どんな入力データに対しても有限の時間で答を与えること、すなわち、計算を完了すること。

つまり、アルゴリズムが出す答は正しくなければならず、かつそれが本当に答を出すことを保証していなければならない。

アルゴリズムの証明の方法

　プログラムの中の特定の場所で変数の値の間に成立する条件式を表明(assertion)、ループの中で回るたびに常に成立している表明のことをループ不変条件(loop invariant)という。アルゴリズムの正しさを証明する基本的な手法は、ループ不変条件の成立を示すことだ。

例)ユークリッドの互除法
ステップ1：mをnで割って、余りをrとする。
ステップ2：r=0であれば、アルゴリズムは終了する。このときnが最大公約数である。
ステップ3：m<--nとする。次にn<--rとして、ステップ1に戻る。

たとえば、36と14の最大公約数をユークリッドの互除法を用いて求めると下のようになる。これは上のステップを繰り返し適用して求めたものだが、繰り返しの手順を経ても、最大公約数は変化しない。これがループ不変条件。

m    n    商   r
































-















36 / 14 = 2 … 8   <--36と14の最大公約数は2

14 / 8  = 1 … 6   <--14と8の最大公約数は2

8  / 6  = 1 … 2   <--8と6　　　〃

6  / 2  = 3 … 0   <--6と2      〃 

ループ不変条件が成立することを証明するには、次の2つのことを確認する。

(1)繰り返しが始まる直前にこの条件が成立していること。
(2)この条件が成立している時に繰り返しを1回進めると、再び条件が成立すること。

これはちょうど数学的帰納法による証明と同じである。

・・・と、いまアルゴリズムについて勉強しているので書いてみた。

参考文献：

アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3)