めも

メモ.

応用情報技術者試験の対策時のメモ(約100日前)

試験日

2020年4月第三日曜日.

前回

メモ

基礎理論

待ち行列理論

かなり昔に(情報システム理論と待ち行列理論1:メモ - めも)学んだ記憶があるが, 応用情報では基本の簡単な式のみ覚えておけば問題ないと思われる.

  • ケンドールの記法:待ち行列モデルを表現するための記法.
    • A/B/c/K で表現
    • A: 到着間隔分布
    • B: サービス時間分布
    • c: 窓口数
    • K: 窓口+待合室(システム)の容量

A/B/C/K/N/Dの書き方もあるが, A/B/Cのみで十分.

  • Aの種類

    • M: マルコフ過程, 到着間隔は指数分布, ランダムな到着はポアソン過程を用いて表現.
    • MAP: マルコフ到着過程
    • Ek: 位数kのアーラン分布
  • システムのモデリング

  • キャパシティプランニング

数値誤差

IEEE 754(あいとりぷるいー754、IEEE Standard for Floating-Point Arithmetic: 直訳すると「浮動小数点算術標準」)は、浮動小数点数の計算で最も広く採用されている標準規格であり、多くのプロセッサなどのハードウェア、またソフトウェア(コンピュータ・プログラム)に実装されている。多くのコンピュータ・プログラミング言語ないしその処理系でも、浮動小数点数処理の一部または全部が IEEE 754 になっている。(IEEE754 - Wikipediaより引用)

  • 例外処理:IEEE754に基づいた計算で例外が発生しうるケース
    • 無効な演算(負の数にrootを取るなど)
    • 0除算
    • オーバーフロー・アンダーフロー
    • 不正確
  • 数値誤差の原因
    • 丸め誤差:切り捨てか四捨五入の二種類の丸め誤差が存在する
    • 桁落ち:上位が0になり有効桁数が少なくなる現象
    • 情報落ち:桁数の幅を超えた桁でしか表現できない小さい値が無視される現象
    • 打ち切り誤差:極限の計算を途中で打ち切ることで発生する理論値と実際の値の間に発生する差
  • マシンイプシロン
    • 最大相対誤差を用いて浮動小数点システムの精度を表現することができて, これをマシンイプシロンと呼ぶ
    • log_10_(1/マシンイプシロン) で桁数を求めることができる
    • 逆に 1+(1/2)q <= 1 となる q から 2(-q) とすればマシンイプシロンを逆算できる

計算量

  • 参考文献

  • 正当性

    • 完全正当性:プログラムを実行すると必ず停止することが要求されているとき
    • 部分正当性:返ってくる答えが正しいが、常に停止して答えを得られることは求めていない
  • カリー=ハワード同型対応

  • 計算量とO(オーダー)記法

    • 時間計算量:使用する時間量
    • 空間(領域)計算量:使用するメモリなどの記憶容量
  • 計算コストモデル
    • 全ての数を一つのデータとみなした一様コストモデルか表現ビットに依存して時間がかかるとする対数コストモデルかによって時間・空間計算量は変化する

Program Evaluation and Review Technique(PERT)

最早・最遅結合点時刻とクリティカルパスの意味を理解しておく. 日程短縮したければ最遅結合点時刻が早くなるように調整する、など.

コンパイラ・言語

  • 参考文献

  • コンパイラの構造

    • 字句解析:入力をトークン列にする
    • 構文解析:構文木を生成する
    • 意味解析:構文木を解析
    • コード生成:最適化を行いコード生成
  • プログラムの種類

    • 再帰:実行中の手続きそのものを呼び出す
    • 再使用可能:
      • 再入可能(リエントラント):同時に複数プログラムで使用可能
      • 逐次再使用可能:同時に使用は不可能
    • 再配置可能:主記憶の配置場所を変更可能
  • リエントラント

    • 静的変数やグローバル変数を保持しない
    • 自身のコードを書き換えない
    • リエントラントではないサブルーチンは呼び出さない

プログラム言語の分類

mynavi-creator.jp

  • 命令型
    • 手続き型:実行する必要がある一連の処理を記述
    • オブジェクト指向:データと手続きをカプセル化したオブジェクトの相互作用によって記述
  • 宣言型
    • 論理型:実行する結果を証明する形で記述
    • 関数型:関数定義と関数呼び出しで記述

第十二回-01 手続き型プログラミングとオブジェクト指向プログラミング/コンソールとGUI

www.slideshare.net