情報処理技術者試験対策のページ＞午前対策 目次

テクノロジ系 基礎理論 アルゴリズムとプログラミング

データ構造

1. スタック
   • 関数や手続を呼び出す際に、戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造
   • 配列を用いてスタックを実現する場合の構成要素として、最低限必要なもの
     スタックに最後に入った要素を示す添字の変数
2. キュー
   • データを先入れ先出しのリスト構造で保持するデータ構造
   • データ構造のキューを実現する方法において、片方向リンクに比べた場合の双方向リンクの特徴
     途中への挿入・取り外しが容易に行える
3. リスト
   • 単方向リスト
     • このリスト構造には、先頭ポインタとは別に、末尾データを指し示す末尾ポインタがある
     • ポインタを参照する回数が最も多いもの
       リストの末尾のデータを削除する
   • 単方向線形リスト
     • 先頭ポインタと末尾ポインタを持ち、多くのデータがポインタでつながった単方向の線形リスト
     • 先頭ポインタ、末尾ポインタ又は各データのポインタをたどる回数が最も多いもの
       末尾のデータを削除する処理(単方向のリストは先頭ポインタからつながっているものとし、追加するデータはポインタをたどらなくても参照できるものとする)
   • 双方向連結リスト
     双方向にリンクを自由にたどることができる連結リスト
   • 配列と比較した場合の連結リストの特徴
     要素を挿入する場合、数個のポインタを書き換えるだけなので、処理時間は短い
4. 配列
   • 配列は、添え字によってデータを任意の順序で読み出すことができる
5. 木構造
   • 階層の上位から下位に節点をたどることによって、データを取り出すことができる
   • 根付き木
     • 根と呼ばれる特別な接点から木の枝が分かれるように、幾つかの辺が伸び、その先の接点からさらに辺が伸びるということが繰り返されてできた構造
     • ３種類のポインタ
       ポインタが指す相手がいないときはNILが設定される
       ・接点ｖの親を指すポインタ
       ・接点ｖの第１子を指すポインタ
       ・接点ｖの兄弟を指すポインタ
   • B木
     • 索引部の各ノードのキー値を中心にして、小さい側のレコード数と大きい側のレコード数の比率が、ある範囲内に収まるように動的に再配置しながら格納する
     • 階層の深さが同じになるように、ノードの分割と併合を行う
   • 2分木
     • 葉以外の接点はすべて二つの子をもち、根から葉までの深さがすべて等しい木を考える。ここで、深さとは根から葉に至るまでの枝の個数を表すとき、葉の個数がｎならば、葉以外の接点の個数はn-1である
     • 2分探索木
       • データの個数が４倍になると、最大探索回数は２回増える
       • 要求量以上の大きさを持つ未使用領域のうちで最小のものを割り当てる最良適合（best-fit）アルゴリズムを用いる場合、未使用領域を管理するためのデータ構造として、メモリ割当て時の処理時間がもっとも短い
       • 8,12,5,3,10,7,6の順にデータを与えたときにできる2分探索木
         
     • 完全2分木
       • すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子をもつ要素数ｎの木
       • どの部分木をとっても左の子孫は親より小さく、右の子孫は親より大きいという関係が保たれている
       • 2分木で探索する場合、ある要素を探索するときの最大比較回数のオーダ：log2n
       • 深さとは根から葉に至るまでの枝の個数を表すとき、葉の個数がｎならば、葉以外の節点の個数はｎ−１である
       • 深さをｎとしたとき、葉の数は2^nとなる
   • ハッシュインデックス
     • インデックス方式のうち、キー値を基に算出して格納位置を求めるとき、異なったキー値でも同一の算出結果となる可能性がある
     • B木インデックスと比較して、不等号の条件検索が困難
     • ハッシュ表探索において、同一のハッシュ値となる確率が最も低くなるのは、ハッシュ値が一様分布で近似されるとき
   • 転置インデックス
     全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造
   • ビットマップインデックス
     • B+木インデックスとビットマップインデックスを比較した説明
       少数の異なる値をもつ列への検索はビットマップインデックスの方が有効である
     • "部品"表のメーカコード列に対し、B+木インデックスを作成した。これによって、検索の性能改善が最も期待できる操作
       ここで、部品及びメーカのデータ件数は十分に多く、メーカコードの値は均一に分散されているものとする。また、ごく少数の行には、メーカコード列にNULLが設定されている
       • 期待できる
         メーカコードの値が4001以上、4003以下の部品を検索する
       • あまり期待できない
         メーカコードの値が1001以外の部品を検索する
         メーカコードの値が1001でも4001でもない部品を検索する
         メーカコードの値がNULL以外の部品を検索する

アルゴリズム

1. 整列 ( ソートアルゴリズム )
   • シェルソート
     • ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が１になるまでこれを繰り返す
     • 手順
       1. データ数÷３　→　Ｈとする
       2. データ列を互いにＨ要素分だけ離れた要素からなる部分列とし、それぞれの部分列を挿入法を用いて整列する
       3. Ｈ÷３　→　Ｈとする
       4. Ｈが０であればデータ列の整列は完了し、０でなければ２に戻る
   • クイックソート
     • 分割統治法を適用した整列（ソート）アルゴリズム
     • 中間的な基準値を決めて、それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける
     • 集合対象から基準となる要素を選び、これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことで、整列を行う
     • 手順
       1. 適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割する
       2. 同様にしてグループの中で基準値を選び、それぞれのグループを分割する
       3. この操作を繰り返していく方法
   • ヒープソート
     • 未整列の部分を順序木に構成し、そこから最大値又は最小値を取り出して既整列の部分に移す操作を繰り返して、未整列部分を縮めていく
   • バブルソート
     • 隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返して行う
   • 単純挿入法 /　挿入ソート
     • 対象集合から要素を順次取り出し、それまでに取り出した要素の集合に順序関係を保つように挿入して、整列を行う
     • ｎ個のデータを整列するとき、比較回数が最悪の場合でO（n^2)、最良の場合でO(n)となる
   • 選択ソート
     • 対象集合から最も小さい要素を順次取り出して、整列を行う
2. 併合
3. 探索
   • 線形探索法
     配列上に不規則に並んだ多数のデータの中から、特定のデータを探し出すのに適したアルゴリズム
4. 再帰
   • 再帰的プログラムの特徴
     実行中に自分自身を呼び出すことができる
   • 再帰呼出し
     関数の中で自分自身を用いた処理を行うこと
5. 文字列処理
6. 流れ図の理解
   • 制御構造
     ”前判定繰り返し”は、繰り返し処理の本体を1回も実行しないことがある
7. アルゴリズム設計
8. 近似値計算アルゴリズム
   • ニュートン法
     方程式 f ( x ) ＝ 0 の解の近似値を求めるアルゴリズム
     幾何学的には、 y ＝ f ( x ) の接線を利用して解の近似値を求めるもの
   • モンテカルロ法
     乱数を利用して、求める解や法則性の近似を得る手法

プログラミング

1. プログラミングの役割
   プログラム言語の文法に従って処理手順などを記述し、その処理手順などに誤りがないかを検証すること
2. プログラミング作法
   • プログラム言語における関数呼び出し時の引数の性質
     実引数から駆り引数に情報を渡す方法として、値呼び出し、参照呼出しなどがある
   • プログラムの局所参照性
     ループによる反復実行のように、短い時間にメモリの近接した場所を参照するプログラムの局所参照性は高くなる
   • 標準化
     プログラミングに関する規約を設けることによって、プログラマの犯しやすい誤りを未然に防止する効果がある
   • 値呼出し
     サブルーチンへの引数の渡し方のうち、変数を引数として渡しても、サブルーチンの実行後に変数の値が変更されないことが保証されている
   • 参照呼出し
     引数の記憶領域のアドレスが渡される
     メインルーチンとサブルーチンで、変数の記憶領域が共有されるため、サブルーチンでその変数に対して行った操作はメインルーチンでも有効となる
3. プログラム構造
   • 動的結合
     オブジェクト指向プログラムにおいて、実行時にメッセージとメソッドを関連付けること
   • 並列処理プログラミング
     複数の処理装置を用いて、一つのプログラムで行う処理内容を複数に分けて、それぞれの処理装置で実行する。各処理装置で得られた結果は、最終的に一つの結果にまとめる。単一の処理装置だけでは実現できない高速な処理を実現する
   • オブジェクト指向プログラミング
     オブジェクトが相互にメッセージを送ることによって、協調して動作し、プログラム全体の機能を実現する
   • 構造化プログラミング
     プログラム設計では、構造化設計技法を用いて業務システムを機能分割する必要がある
   • 多重プログラミング
     • あるプログラムの実行中に、入出力などのために処理装置が待ち状態になったとき、処理装置をほかのプログラムの実行に割り当てることによって有効に利用する方式
       タスクの実行中に、入出力などを行ったために生じるCPUの空き時間を利用して、別タスクを並列に実行する
   • デザインパターン
     • GoFのデザインパターン
       オブジェクト指向開発のためのパターンとして生成、構造、振舞いの3カテゴリから構成される
   • 動的リンキング
     プログラムを構成するモジュールの結合を、プログラムの実行時に行う方式
     プログラムの実行中に、必要になったモジュールを共用ライブラリやシステムライブラリからロードする
4. データ型
5. 文法の表記法

モジュール管理

1. モジュール強度（結束性）（1強・・・7弱）
   • モジュール強度の概念は、モジュール強度の強弱を意識して、設計者がモジュールを作成したり利用したりできるようにするために導入する
   • 強度の種類
     • 機能的強度
       • 全要素が1つの機能を実行するために関連性を持っている
       • 例
         • ある木構造データを扱う機能をデータとともに一つにまとめ、木構造データをモジュールの外から見えないようにした
         • 単一の機能を実行するモジュール
     • 情報的強度
       • 特定のデータを扱う複数の機能がまとまっており、機能ごとに別の入り口点を持つ
       • 同一の情報を扱う複数の機能を、一つのモジュールにまとめている。モジュール内に各処理の入口点を設けているので、制御の結びつきがなく、これ以上のモジュール分割は不要である
     • 連絡的強度
       • 手順的強度の性格を持つことに加えて、各機能が同一データを扱っている
     • 手順的強度
       • ある手続きを実現するために複数の逐次的処理がまとまっている
       • モジュール内でデータの受渡し又は参照を行いながら、複数の機能を逐次的に実行している。再度見直しを図り、必要に応じて更にモジュール分割を行ったほうがよい
       • 例）二つの機能A，Bは必ずA，Bの順に実行され、しかもAで計算した結果をBで使うことがあるので、一つのモジュールにまとめた
     • 時間的強度
       • 初期設定処理、終了処理など、同じタイミングで実行される複数の逐次的処理がまとまっている
       • 例）複数の機能のそれぞれに必要な初期設定の操作が、ある時点で一括して実行できるので、一つのモジュールにまとめた
     • 論理的強度
       • 関連のある複数の機能を含み、どの機能を実行するかを選択できる
       • 例）二つの機能A，Bのコードは重複する部分が多いので、A，Bを一つのモジュールとし、A，Bの機能を使い分けるための引数をもうけた
     • 暗号的強度
       • 関連のない複数の機能を含み、特定の機能を定義していない
       • モジュール内の機能感に特別な関係はなく、むしろ他のモジュールとの強い関係性を持つ可能性が高いので、モジュール分割をやり直したほうがよい
2. モジュール結合（強度：1強・・・6弱　独立性：1低・・・6高）
   • 一般的に弱い方が良いとされる
   • モジュールの変更による影響を少なくするためには、モジュール間の関連性をできるだけ少なくして独立性を高くすることが重要
   • モジュールの独立性を高めるには、一つのモジュールは一つの機能に限定し、モジュール結合度を弱くする必要がある
   • 結合の種類
     • 内容結合
       他のモジュールの内部を直接参照したり、一部を共有する
     • 共通結合
       共通域に定義したデータを、関係するモジュールが参照する
       大域的なデータを参照するモジュール間の関係
     • 外部結合
       必要なデータだけを外部宣言して共有する
     • 制御結合
       制御パラメータを引数として渡し、モジュールの実行順序を制御する
     • スタンプ結合
       構造体のポインタを引数にして渡すが、相手のモジュールに不要なデータも混在する
     • データ結合
       二つのモジュール間で必要なデータ項目だけをモジュール間の引数として渡す
       呼び出す側と呼び出される側のモジュール間のデータの受け渡しは、引数としてデータ項目を列挙する
       単一のデータ項目を引数で受け渡すモジュール
       入出力に必要なデータ項目だけをモジュール間の引数として渡す
3. モジュール分割法
   • データの流れに注目
     • STS分割
       • プログラムをデータの流れに着目して分割する技法
       • 入力データの処理、入力から出力への変換および出力データの処理の三つの部分で構成することで、モジュールの独立性が高まる
       • ソフトウェア開発への応用
         データの流れに着目してシステム分析を行い、再利用可能なモジュールを抽出することによってソフトウェアの生産性を向上させることを目的としている
     • TR分割
       • プログラムをデータの流れに着目して分割する技法
       • 入力データにいくつかの種類があり、その種類ごとに処理内容が異なる場合に、その種類ごとにモジュールを分割する
     • 共通機能分割
       • プログラムを機能に着目して分割する技法
       • 共通の機能があれば、それを1つにまとめ、別モジュールに分割する
   • データの構造に注目
     • ジャクソン法
       • プログラムをデータの構造に着目して分割する技法
       • 入力データ構造と出力データ構造の写像関係からプログラムの構造を決定する
       • 分割手順
         1. 入力データと出力データを分解し、定義する
         2. 各入力データと各出力データを、1対1に対応させる
            1対1にならない場合は、1対1になるように中間的なデータを定義する
         3. 1対1になった入力データと出力データを変換する処理を中心に、モジュール分割をする
     • ワーニエ法
       入力データ、データの出現回数に注目して分割する
   • モジュール設計
     モジュールを構造化する場合は、下位の階層モジュールの変更が上位の階層モジュールに影響しないようにする
   • モジュール設計書を基にモジュール強度を評価したときの適切な評価
     
     [モジュール設計書(抜粋)]
     上位モジュールから渡される処理コードに対応した処理をする。
     処理コードが"I"のときは挿入処理、処理コードが"U"のときは更新処理、
     処理コードは"D"のときは削除処理である。
     
     これは"論理的強度"のモジュールである。
     関連した幾つかの機能を含み、パラメタによっていずれかの機能を選択して実行している。
     現状では大きな問題となっていないとしても、
     仕様変更に伴うパラメタの変更による影響を最小限に抑えるために、機能ごとにモジュールを分割するか入り口点を設ける方がよい。

プログラム言語

1. インタプリタ方式
   原始プログラムを1命令ずつ解釈して実行するプログラム
   プログラムの部分的な翻訳と実行を反復して行うことが容易
   コンパイラ方式に比べ、プログラムの実行速度は遅い
2. コンパイラ方式
   コンパイラで変換されるプログラムは、最終的には機械語に変換されてから実行される
3. プログラムを翻訳して実行するまでの流れ
   
4. Java
   • インターネットや分散システム環境で利用されている、オブジェクト指向のプログラム言語
   • コンピュータの機種やOSに依存しないソフトウェアが開発できる、オブジェクト指向型の言語
   • Javaコンパイラがソースコードをバイトコードに変換し、Java仮想マシンがバイトコードを実行する
   • Javaコンパイラで翻訳したコードは、Java固有のバイトコードである
   • 多重継承はできない（単一継承）
   • マルチスレッド機能が含まれている
   • プリプロセッサを持たない
   • メモリ管理は自動的に行われ、メモリのガーベジコレクションの機能が働く
   • JavaBeans
     Javaのプログラムにおいて、よく使われる機能などを部品化し、再利用できるようにコンポーネント化するための仕様
   • EJB（Enterprise Java Beans）
     • オブジェクト指向によるシステムで利用される分析から設計、実装、テストまでを統一した表記法
     • サーバでの実行を前提とした基幹業務を意識したオブジェクト指向開発によるコンポーネントソフトウェアをJavaで構築するためのコンポーネント規約の仕様
   • Javaアプリケーション
     Java VMが稼働している環境だけがあれば、WebブラウザやWebサーバがなくても動作するプログラム
   • JSP ( Java Server Pages )
     • プログラミング言語Javaで処理を記述する
     • サーバサイドでServletのコードに翻訳されて実行される
     • HTML文書にコードを記述する
   • JDBC
     Javaのアプリケーションプログラムがデータベースにアクセスするための標準的なAPI
   • ブラウザで動作するアプレットなどを作成できる
     • Javaアプレット
       • Javaで作成されたプログラムであって、Webサーバからダウンロードされ、ブラウザ上で実行されるもの
       • サーバからダウンロードしてクライアントで実行する
       • 仮想マシンを実装した環境上であれば、どこでも実行できる
     • Javaサーブレット ( Java Servlet )
       • J2EE(Java2 Platform,Enterprise Edition)の構成技術の一つ
       • Web環境での動的処理を実現するプログラムであって、Webサーバ上だけで動作する
       • 一度ロードされるとサーバに常駐し、スレッドとして実行されるWebコンポーネント
     • JavaScript
       • HTMLファイル内に直接プログラムを記述し、ブラウザで実行する
       • HTMLだけでは実現できない入力データの検査がブラウザ側で実現可能になる
5. C言語（プログラム言語C）
   • 高水準言語であるが、システムの細部までを記述でき、その成り立ちからシステム記述言語として位置づけられることが多い
   • MISRA-C
     車載システムの品質向上を目的に制定された、C言語実装法のガイドライン
6. C++
   • 多重継承が可能
   • マルチスレッド機能が含まれていない
   • プリプロセッサを持つ
7. Prolog
   • 述語論理を基盤とする言語
   • ユニフィケーションとバックトラックを使ってデータベースを探索する
8. BASIC
   初心者向きの対話型汎用言語
9. Lisp
   • 対話型言語の性格を持った関数型言語
   • 集合演算や行列演算に特徴があるので、普及当初は科学技術計算向きとされた
10. PostScript言語
    主にプリンタ用に使用されるページ記述言語
11. CGI
    Webサーバにおいて、クライアントからの要求に応じてアプリケーションプログラムを実行して、その結果をブラウザに返すなどのインタラクティブなページを実現するために、Webサーバと外部プログラムを連携させる仕組み
12. Ajax
    • JavaScriptの非同期通信の機能を使うことによって、画面遷移が起こらない動的なユーザインタフェースを実現する技術
    • ブラウザとWebサーバとがXML形式のデータを用いて非同期の通信をし、動的に画面を再描画する仕組み
    • JavaScriptの非同期通信の機能を使うことによって、動的なユーザインタフェースを画面遷移を伴わずに実現する技術
    • JavaScriptなどのスクリプト言語を使って、Webブラウザに組み込まれているサーバとの非同期通信機能を利用する技術であり、地図の拘束なスクロールや、キーボード入力に合わせた検索候補の逐次表示などを実現するもの
13. アセンブラ言語
14. COBOL
15. Java4
16. Perl
17. PHP
18. Python
19. Ruby
20. ECMAScript
21. 共通言語基盤(CLI)

その他の言語

1. マークアップ言語の種類と特徴
   • マークアップ言語
     文書中にタグを挿入することによって、文書の構造を記述できる言語
   • HTML
     • Webページを記述するための言語であり、タグによって文書の論理構造などを表現する
     • ハイパテキスト
       リンクをクリックすることによって、指定されたテキストに移動できる
     • DHTML(Dynamic HTML)
       • 「入力データの検査」のようなHTMLだけでは実現できない動的なWebコンテンツを開発するためにHTMLを拡張したもの
       • HTMLに対して、DOM、スクリプト、スタイルシートが追加された
   • SGML
     • タグを使って文書の論理構造や属性を記述する方法を定めた国際規格で、電子的な文書の管理や交換を容易に行うための標準文書記述言語
     • HTMLやXMLの基となったもので、図や表を含む文書データを取り扱うことができるISO標準の言語
     • 論理構造をもった文書の作成に用いられる
     • 文書を、宣言、文書型定義および文書実現値の3部の構成で記述する
   • XML ( eXtensible Markup Language )
     • データの構造や意味をタグを用いて利用者が目的に応じて定義し、表現する言語
     • タグ
       "<"と">"に囲まれた文書の構造などに関する指定
     • 文章の論理構造を記述する方法
       文章や節などをタグで囲む
     • 利用者独自のタグを使って、文書の属性情報や論理構造を定義することができる
     • XMLでは、ネットワークを介した情報システム間のデータ交換を容易にするために、任意のタグを定義することができる
     • インターネットを利用した企業間取引において、取引データをそのまま起票したり社内文書に変換したりするなど、 ネットワークを介した情報システム間のデータ交換を容易にするために、任意のタグを定義することができる
     • HTMLでは要素によっては終了タグを省略できるが、XMLでは開始タグと終了タグで内容を囲むか、空要素の形式で記述する必要がある
     • インターネットとの親和性が高い双方向リンク可能なハイパテキスト記述言語であり、文書の構造をDTDとして記述することで、ユーザ独自のタグが定義でき、文書中の文字列に属性を与えたり、文書中の文字列のデータ処理などが可能
     • 整形式(well-formed)のXML文書が妥当(valid)なXML文書である条件
       DTDに適合している
     • XSLT
       XML文書を、別の文書形式を持つXML文書やHTML文書などに変換するための仕様
     • 要素の定義方法
       • データを開始タグと終了タグで囲んで構成する
       • 要素の中に子要素を持つことができる
       • データがないこともある
     • W3C XML Schemaの用途
       XMLで記述される文書の構造を定義する
     • DTD ( Document Type Definition )
       妥当なXML文書であるかを判定する
     • W3C XML Schema
       XMLで記述される文書の構造を定義する
     • XMLパーサ
       XMLの構文解析を行う
     • XSLT ( eXtensible Stylesheet Language Transformation )
       • XML文書を別の文書構造を持つXML文書やHTML文書などに変換するための仕様
       • XMLのデータ構造を変換・加工する
     • Xlink ( XML Linking Language )
       • XML文書中のオブジェクト間のハイパーリンク機構を提供する標準書式
       • HTMLとほぼ同様の機能を持つ単純リンク機能と、双方向の複数リンクを指定することで有機的にファイルが利用できる拡張リンク機能がある
   • SMIL
     動画や音声などのマルチメディアコンテンツのレイアウトや再生のタイミングをXMLフォーマットで記述するためのW3C勧告
   • SVG ( Scalable Vector Graphics )
     • W3Cで仕様が定義され、矩形や円、直線、文字列などの図形オブジェクトをXML形式で記述し、Webページでの図形描画にも使うことができる画像フォーマット
     • XMLによって記述されたベクターグラフィック言語
   • XHTML
     HTMLをXMLの規格に合うように修正し定義したもの
   • CSS ( Cascading Style Sheets )
     • HTMLやXMLの要素をどのように表示するかを指示する仕様
     • HTML文書の文字の大きさ、文字の色、行間などの視覚表現の情報を扱う標準仕様
     • Webページのスタイルを定義する仕組み
     • HTMLやXMLの要素をどのように表示するかを指示する場合に用いられ、表示クライアント側で処理されるもの
2. データ記述言語(DDL)
   • 仕様記述言語SDL（ Specification and Description Language ）
     ソフトウェアや通信プロトコルを設計する際に、その使用を記述する言語
     • アーキテクチャ記述言語ADL（ Architecture Description Language ）
       ソフトウェアアーキテクチャやシステムアーキテクチャを記述するための言語 ソフトウェアアーキテクチャやシステムアーキテクチャを記述するための言語