試験日
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のアーラン分布
システムのモデリング
- M/M/m: ランダムな到着に対してm個の窓口で対応
- M/M/1: 窓口が1
- サービス利用率＝単位時間あたりの平均到着率/単位時間あたりの平均処理率 が成り立つ
- サービス利用率ρはトラヒック密度とも呼ぶ
- 待ち行列理論（M/M/1モデル）の定理とその証明 | 高校数学の美しい物語
- 利用率が大きくなると平均待ち時間が急増するので, 利用率は低く抑える
- キャパシティプランニング
- キャパシティ・プランニング
- 性能要件を決め, サイジングを通じて評価とチューニングを行う
数値誤差
参考文献
実数は符号・指数部・仮数部で表現する
IEEE 754（あいとりぷるいー754、IEEE Standard for Floating-Point Arithmetic: 直訳すると「浮動小数点算術標準」）は、浮動小数点数の計算で最も広く採用されている標準規格であり、多くのプロセッサなどのハードウェア、またソフトウェア（コンピュータ・プログラム）に実装されている。多くのコンピュータ・プログラミング言語ないしその処理系でも、浮動小数点数処理の一部または全部が IEEE 754 になっている。(IEEE754 - Wikipediaより引用)
- 例外処理：IEEE754に基づいた計算で例外が発生しうるケース
- 無効な演算（負の数にrootを取るなど）
- ０除算
- オーバーフロー・アンダーフロー
- 不正確
- 数値誤差の原因
- 丸め誤差：切り捨てか四捨五入の二種類の丸め誤差が存在する
- 桁落ち：上位が０になり有効桁数が少なくなる現象
- 情報落ち：桁数の幅を超えた桁でしか表現できない小さい値が無視される現象
- 打ち切り誤差：極限の計算を途中で打ち切ることで発生する理論値と実際の値の間に発生する差
- マシンイプシロン
- 最大相対誤差を用いて浮動小数点システムの精度を表現することができて, これをマシンイプシロンと呼ぶ
- log_10_(1/マシンイプシロン) で桁数を求めることができる
- 逆に 1+(1/2)q <= 1 となる q から 2(-q) とすればマシンイプシロンを逆算できる
計算量
参考文献
- 正当性 (計算機科学) - Wikipedia
- Kida's HP --- Lecturesの第二回講義資料より. 他の資料も参考になります.
正当性
- 完全正当性：プログラムを実行すると必ず停止することが要求されているとき
- 部分正当性：返ってくる答えが正しいが、常に停止して答えを得られることは求めていない
カリー＝ハワード同型対応
計算量とO(オーダー)記法
- 時間計算量：使用する時間量
- 空間（領域）計算量：使用するメモリなどの記憶容量
- 計算コストモデル
- 全ての数を一つのデータとみなした一様コストモデルか表現ビットに依存して時間がかかるとする対数コストモデルかによって時間・空間計算量は変化する
Program Evaluation and Review Technique(PERT)
最早・最遅結合点時刻とクリティカルパスの意味を理解しておく. 日程短縮したければ最遅結合点時刻が早くなるように調整する、など.
コンパイラ・言語
参考文献
- コンパイラ - 京都大学OCW>講義ノートより各回の講義資料を閲覧できます
- リエントラント（再入可能）とは - IT用語辞典 e-Words
- 位置独立コード - Wikipedia
コンパイラの構造
- 字句解析：入力をトークン列にする
- 構文解析：構文木を生成する
- 意味解析：構文木を解析
- コード生成：最適化を行いコード生成
プログラムの種類
- 再帰：実行中の手続きそのものを呼び出す
- 再使用可能：
- 再入可能（リエントラント）：同時に複数プログラムで使用可能
- 逐次再使用可能：同時に使用は不可能
- 再配置可能：主記憶の配置場所を変更可能
リエントラント
- 静的変数やグローバル変数を保持しない
- 自身のコードを書き換えない
- リエントラントではないサブルーチンは呼び出さない
プログラム言語の分類
参考文献
インタプリタとコンパイラ
- インタプリタ：ソースコードを変換せずに直接実行する
- コンパイラ：元のコードをコンパイラを通じてオブジェクトコードに変換し, 最適化をした上で実行する
- リンク：実行に必要な外部のモジュールやライブラリを結合する作業
- 高級言語と低級言語
- 実行のレイヤー視点で見たときの高低
- マシン語やアセンブリ言語は低級言語になる
- コンパイラを通じて低級言語が実行可能なプログラムを作成したとき, 作成されたプログラムはオブジェクトコードと呼ぶ.
- 実行時にオブジェクトコードに変換する作業を同時に行うとき, それをインタプリタと呼ぶ
- マークアップ言語
- SGML：SGML（Standard Generalized Markup Language）とは - IT用語辞典 e-Words
- XML
- HTML
- XHTML
- 命令型
- 手続き型：実行する必要がある一連の処理を記述
- オブジェクト指向：データと手続きをカプセル化したオブジェクトの相互作用によって記述
- 宣言型
- 論理型：実行する結果を証明する形で記述
- 関数型：関数定義と関数呼び出しで記述
第十二回-01 手続き型プログラミングとオブジェクト指向プログラミング／コンソールとGUI
www.slideshare.net
