応用情報　学習備忘録　DB、通信

  • データベース設計

概念設計：E-R図、UMLクラス図

論理設計：階層モデル、網モデル、関係モデル

物理設計

 

データベースの変更によるアプリケーションへの影響をなくす

外部スキーマ：ビュー定義、ユーザから見たデータの記述

概念スキーマ：論理データモデル、論理的構造

内部スキーマ：物理設計

 

  • 関係モデル

行はタプル（組）、列はアトリビュート（属性）。

ドメイン：属性の定義域

スーパキー：行を一意に識別できるキーの組

候補キー：余計なものがないスーパキー

主キー：候補キーの中のどれか１つ。残りは代理キー

 

  • 関数従属

部分関数従属：複数のｘの真部分集合によってｙが一意に決まる

完全関数従属：どの真部分集合に関しても関数従属でない

推移的関数従属

 

  • 正規化

第一正規化：繰り返しをなくす

第二正規化：部分関数従属をなくす

第三正規化：推移的関数従属をなくす

 

  • 表への操作

選択：行を抜き出す、誰かを選ぶ的な

射影：列を抜き出す

ビュー：表から必要な行、列を取り出した仮想表

カーソル処理：表から複数行取り出す

 

原子性：更新が正常終了したときのみデータベースに反映する

一貫性：データに矛盾がない

隔離性：同時に実行しても順番に実行しても結果が同じ

耐久性：正常終了したトランザクションの処理結果が消失しない

 

  • 同時実行制御

2相ロック方式：使うデータを一気にロックする

木規約：データをロックする順番を機構造で定める

多版同時実行制御：MVCC、ロック中のデータを参照しようとしたとき待たされるのではなく、更新前の情報が与えられる

 

Write Ahead Log。更新データより先にログを書き込む。

 

  • システム障害からの回復

undo：COMMIT済みじゃないトランザクションの更新前情報で回復

redo：COMMIT済みのトランザクションの更新後情報で回復

 

SQLの問い合わせの処理の最適化

 

  • 分散データベースの更新

レプリケーション：非同期型更新、マスターデータベースの内容を複写

二層コミットメント制御：同期型更新、セキュア状態

三層コミットメント制御：プリコミットメント

 

  • ETL

Extract（抽出）、Transform（変換）、Load（データウェアハウスへのロード）によりデータウェアハウスを構築

 

  • OLAP

多次元データを様々な視点から分析すること

 

決定木分析：予測、データ分類など

ニューラルネットワーク：数値予測

 

  • NoSQL

Not Only SQL。大規模データや分散データベースの処理

 

  • CAP定理

一貫性、可用性、分断耐性のうち同時に満たせるのは2つまで

 

  • RIP

ディスタンスベクタ型ルーティングプロトコル。経由するルータの数を最小にする

  • OSFP

リンクステート型ルーティングプロトコル。コスト最小の経路を選ぶ

 

  • メディアアクセス制御

CSMA/CD：イーサネット、衝突したらランダム時間待つ

CSMA/CA：無線LAN、使われていないことを確かめてから送る

トークンパッシング方式：フリートークン、再送の必要がない

TDMA：時分割多重アクセス、通信できる時間帯がノードごとに決まっている

RTS/CTS方式：通信リクエストとそれに対する返答

ARP：IPアドレスからMACアドレスを得る ⇔ RARP

PPP：二点間をポイントツーポイントで接続

NAT：グローバルIPアドレスとプライベートIPアドレスを相互変換

ICMP：IP通信のエラーを送るためのプロトコル

 

  • WebSocket

クライアントとWebサーバ間の双方向通信、リアルタイム性

 

ネットワーク上の機器の監視、管理

 

  • 伝送制御

ベーシック手順：キャラクタ同期方式

HDLC手順：フラグ同期方式、CRCによる誤り検出

応用情報　1~5章　過去問659問

応用情報の過去問を解いた時のメモ

 

  • ディスプレイ

有機EL：電圧、発光素子

ブラウン管：電子ビーム

液晶：透過する光

プラズマディスプレイ：放電、紫外線、蛍光体

 

  • 略語（言語）

DDL：Data Definition Language。データベースの定義に使われるSQL。

HDL：Hardware Description Language。デジタル回路の構成を文章で記述。FPGA、直接論理構成

UML：Unified Modeling Language。オブジェクト指向開発。

XML：eXtended Markup Language。システム間のデータ交換。利用者が自由に定義。

 

  • DisplayPort

音声、映像信号をパケット化して伝送できる。

 

フェールオーバーの場合はMTTRはフェールオーバーに要する時間に等しい。

 

  • JIS X 9303-1:2006(ユーザーシステムインタフェース及びシンボル－アイコン及び機能－アイコン一般)

習得性：理解された後に容易に思い出せる

判読性：容易に区別できる

認識性：以前の経験に基づいて容易に識別できる

識別性：近いアイコンから見つけやすい

 

  • データの利用

ディープラーニング：人間の脳の神経回路

データマイニング：例外事項を取り除きながら分析を繰り返す。様々な手法を組み合わせた高度な分析手法

エキスパートシステム：知識がルールに従って表現。演繹。

 

  • スタック領域とヒープ領域

スタック領域：LILO方式。サブルーチンの戻り番地、局所変数。

ヒープ領域：双方向リスト。

 

物理的要因

ラッチアップ：寄生サイリスタの導通

ESD破壊：静電気放電

過電流

 

  • 近似的解法

オイラー法：刻み幅、ｈ

ガウスの消去法：掃き出し法、行列

シンプソン法：三点を通る二次関数。台形公式（二点）より高精度

ニュートン法：接線とｘ軸の交点

モンテカルロ法：円の面積、乱数、点

 

Dhrystone：整数演算性能

FLOPS：ベクトルコンピュータ、浮動小数点演算

MIPS

SPECint：整数演算

Linpack：浮動小数点

TPC-C：オンライントランザクション、システム全体

 

  • 仮想サーバ

ライブマイグレーション：OSやソフトウェアを停止することなく移し替え

ストレージ自動階層化：適したストレージに自動的に配置

 

  • 光ディスク

CD-R：有機色素、ピット

CD-RW：結晶構造、書き換え可能

DVD-RAM：アモルファス金属、相変化メモリ、書き換え可能

DVD-ROM：マスター基盤、プレス、張り合わせ

 

  • Script系

ECMAScript：JSの標準化、動的型付け

JavaScript：動的型付け

TypeScript：静的型付け、クラス定義、JSの上位互換

VBScript：マイクロソフト、動的型付け

 

  • 二値分類モデル

ROC曲線：真陽性率と偽陽性率

PR曲線：真陽性率と適合率

 

大規模なデータ、分散処理

 

  • JavaBeans

プログラムの再利用、コンポーネント

Webサーバ、Webコンポーネント、サーバに常駐

 

再頒布自由（制限付く場合あり）、有料販売、派生物の再配布

Apache：HTTPサーバ（Webサーバ）

BIND：DNSサーバ

Postfix：メールサーバ

 

  • コード

デシマルコード：10個のグループに分けることを繰り返す

ニモニックコード：コードから対象物が連想できる

 

  • パイプラインハザード

データハザード：データの依存関係。直前の命令の実行結果

構造ハザード：ハードウェア資源の競合

制御ハザード：分岐命令、割り込み

 

 

  • CDN（Contents Delivery Network）

音声、動画など大容量データを安定して配信

 

  • USB

プラグアンドプレイ、ホットプラグ、バスパワー方式、On-The-Go

 

排他制御、セマフォ変数の値は利用可能者数を表すイメージ

P操作：利用可能者数が0じゃないなら実行可能状態に、0なら待っててもらう

V操作：利用可能者数を1増やす(ついでに待ってる人を誘導する)。誰かが使い終わったときとか

セマフォとは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

P操作とは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

 

  • ３D映像

アクティブシャッタ方式：右目、左目用の映像、交互

パララックスバリア方式：右目、左目用の映像、同時

アナグリフ方式：赤青のカラーフィルター

偏光フィルタ方式：偏光眼鏡

 

  • 共有ライブラリ

静的ライブラリに比べ、実行ファイル小、メモリ使用効率良、再コンパイル不要、リンク時のオーバーヘッド大

 

オープンソースライセンス。GPLを一部使ったコードは無条件にGPLになる

 

  • 誤り制御

水平パリティ：1ビットの誤り検出

垂直水平パリティ：1ビットの誤り訂正

チェックサム：合計値、誤り検出

チェックディジット：誤り検出

ハミング符号：情報ビットに検査ビットを付加。2ビット誤り検出と1ビット誤り訂正

 

  • コンピュータシステム

密結合マルチプロセッサ：複数のCPUがメモリを共有

デュアルブート：1台のコンピュータに複数のOS

デュアルシステム：照合機で二台の結果を比較

 

整形式：エラーが出ない

妥当：！Doctypeを含む

 

  • ヒープ

親より子の方が大きい

 

リアルタイム×、タイムシェアリングシステム〇

 

  • PLC

ラダー図、シーケンスプログラム

 

  • SAN

Storage Area Network。LANとかは用いずに独立の回線でデータ転送などできる。ファイバチャネル。

 

周辺機器をファイルとして扱える。

デーモン：バックグラウンドで動作するプログラム

パイプ：コマンド間のデータの受け渡し

特殊ファイル：入出力装置

通常ファイル：データを格納

ディレクトリファイル：ファイルと実体の関連付け

 

  • ユニファイドメモリ方式

CPUとGPUの使うメモリが同じ。主記憶の一部を表示領域として使用。

 

  • スーパースカラ

複数パイプライン。複数の演算器。

 

  • ウェアレベリング

フラッシュメモリなどにおいて書き込み回数が均等になるようにする。

 

パワーゲーティング：電源供給遮断

クロックゲーティング：クロックを停止

マルチVdd：異なる電圧値の電源

 

  • フェールバック

フェールオーバーから元に戻す

  • フォールバック

縮退運転

  • インタロック

フールプルーフ、特定の条件下じゃないと動作しないようにする

 

2ビット誤り検出と1ビット訂正。ハミング符号。高信頼性。

 

  • SoC

複数のチップ、LSI。

  • システムLSI

複数のLSIを1つのチップに

 

  • 単純選択法と単純挿入法

単純選択法：最小の要素を選び、先頭と入れ替える。安定でない。O(n^2)

単純挿入法：未整列の先頭を整列済みの正しい位置に挿入。安定。最良はO(n)

 

  • IaC（Infrastructure as Code）

サーバ、ネットワーク、OSなどの設定をコードとして管理することでセットアップを自動化。

 

Digital Signal Processor。積和演算に強い。

 

JavaScriptの非同期通信、画面遷移の起こらない動的なインターフェース、Webブラウザのみ、検索候補

 

モデル層：業務処理

ビュー層：表示

コントローラー層：モデル層、ビュー層への処理依頼

 

  • DHTML

DOM、スタイルシート、スクリプト

 

可変長、ASCIIの上位互換

 

  • アクセス透過性

遠隔地

 

平均位置決め時間＋平均回転待ち時間＋データ転送時間

 

Near Field Communication。10㎝、ピアツーピア、非接触型

 

仮想化、サーバの台数を減らす、維持管理コスト削減

 

  • ディスパッチ

タスクの切り替え

 

  • コード

順番コード：少ない桁数、発生順なら追加が容易、分類がわからない

区分コード：少ない桁数でのグループ分け、追加大変

桁別コード：桁数多くなりやすい、分類がわかりやすい

 

NAND：ページ単位、安価に大容量化

NOR：バイト単位、読出しは早い、高信頼性

 

1クロック、固定長の命令、レジスタ間の演算のみ、ワイヤードロジック、パイプライン化

 

  • パイプラインの深さ

命令を何分割するか

 

低速、低消費電力、短距離、センサーネットワーク

 

  • シンプロビジョニング

実際の使用量に応じて記憶領域を割り当て

 

  • ヘテロジニアスマルチコアプロセッサ

異なる種類のCPUコアを持つプロセッサ。スマホなど

⇔ホモジニアスマルチコアプロセッサ

 

 

応用情報　学習備忘録　仮想記憶

メモリ管理ユニット。仮想アドレスから実アドレスへの変換を行う。

 

ページングが多発すること

 

  • 言語プロセッサ

インタプリタ：１命令ずつ翻訳し、実行する

プリプロセッサ：ある高水準言語をほかの高水準言語に変換

 

  • 動的テストツール

トレーサ：実行直後のレジスタやメモリの内容を得る

アサーションチェッカ：プログラムの正当性を検証する

テストがバレージツール：ホワイトボックステストでの網羅率をチェック

プロファイラ：性能分析

ICE（インサーキットエミュレータ）：ソフトウェアやハードウェアのデバック

 

応用情報　学習備忘録　待ち行列＋α

  • 平均到着率

単位時間に到着するトランザクション数λ

  • 平均到着間隔

平均到着率の逆数

 

  • 平均サービス率

単位時間あたりにサービス可能なトランザクション数μ

  • 平均サービス時間

平均サービス率の逆数

 

  • 利用率

ρ＝　平均到着率 / 平均サービス率　＝　λ/μ

 

  • 待ち時間

平均応答時間：サービスの時間も含む

　　　　　　　ρ/(1-ρ) × 1/μ + 1/μ

平均待ち時間：サービスの時間は含まない

　　　　　　　ρ/(1-ρ) × 1/μ

 

  • 行列の長さ

平均滞留数：サービス中のものも含む

平均待ち行列長：サービス中のものは含まない

 

  • M/M/Sモデル

窓口がS個ある。

利用率：λ/μ × 1/s

 

Reliability：MTBFが大きい。故障しにくさ。

Availability：稼働率

Serviceability：修理しやすさ。MTTRが小さい。

Intergrity：データの完全性

Security：障害、犯罪に対する耐性

 

  • プリエンプション

割込みなどによってCPUの使用権を奪うこと

 

  • TCB

タスク管理に必要な情報が保持される。

 

  • タスク切り替え

イベントドリブン方式：割込みによって切り替え

タイムスライス方式：一定周期で切り替え

 

  • スケジューリング

到着順方式：実行可能になった順

優先順位方式：動的と静的がある

ラウンドロビン方式：到着順でやるけどタイムクウォンタム内で終わらなければ後回しにする

応用情報　学習備忘録

応用情報の勉強で得た知識のアウトプット用です。

 

  • MIMD

Multiple Instruction Multiple Dataの略。異なるデータに異なる命令を実行する。

ex）MPP（Massively Parallel Processor）：超並列コンピュータ

 

複数のプロセッサが主記憶を共有している。単一のOSによる制御を行っており、プロセッサの数が多すぎると競合が発生しやすくなる。

 

各プロセッサに主記憶とOSが割り当てられる。競合が起きにくい反面、構成が複雑になりやすい。

 

高速化率Eは以下の式で決まり、ある一定以上の値にはならない。

E＝1/{1-r+(r/n)}　n:プロセッサ数、r:並列化可能割合

 

  • 命令実行時間

クロックサイクル時間　×　CPI

 

Synchronous DRAM。バスクロックと同期している。

 

Double Data Rate SDRAM。クロックの立ち上がりと立下りでデータを読み出す。DDR2はDDRの二倍。

 

NOR型より書き込みが速く、ページ単位で行う。集積度が高い。

 

書き込みは遅いが読み出しは早い。バイト単位。集積度低い。

 

  • FeRAM

強誘電体メモリ。分極を用いている。

 

  • ライトスルー方式

キャッシュに書き込むと同時に主記憶にも書き込む。

 

  • ライトバック方式

キャッシュからデータが追い出されるときに主記憶に書き込む。

 

  • スヌープ方式

マルチプロセッサで主記憶を共有しているとき、あるキャッシュから主記憶にデータを書き込むことで別のキャッシュと主記憶の間でデータの不一致が起こることを防ぐためパススヌープによってデータの更新を監視する。

 

  • メモリインタリーブ

主記憶に並列にアクセス。

 

  • 入出力制御

プログラム制御方式：CPUによって制御

DMA制御方式：CPUを介さず外部装置から直接やり取り。

チャネル制御方式：DMAの拡張。入出力専用の装置（チャネル）を介する。CCW,CAW

 

ホストが多くの処理を行うため、端末の機能が最低限になっている。

 

  • 分散処理

水平機能分散：業務の種類によって分散

水平負荷分散：負荷の状況に応じて分散

垂直機能分散：処理を階層で分ける

 

  • クライアントサーバシステム

サービスを要求するクライアントと提供するサーバに機能を分ける。

二層クライアントサーバシステム：サーバはデータベースの管理と要求されたアクセスのみを実行し、その他の処理はクライアントが行う。

三層クライアントサーバシステム：プレゼンテーション層、ファンクション層、データベースアクセス層の三つに分ける。

Web三層構造：Webシステムを三層クライアントサーバシステムで実装。軽い処理はWebサーバ、重い処理はアプリケーションサーバで行う。

 

  • ストアドプロシージャ

字実行可能なSQL命令をデータベースに格納したもので呼び出すだけで処理を実行できる。通信回数の減少、操作の標準化、セキュリティ向上などのメリットがある。

 

  • RPC

他のコンピュータが提供する手続きをあたかも同一のコンピュータによる手続きに見せる。

NFS：他のコンピュータのファイルを自分のファイルかのように操作できる。

 

  • フォールトトレランス

故障が起きても必要な機能を維持できるようにする。

フェールソフト：システム全体は停止させずにフェールバック（障害のある部分の切り離し）などで必要な機能を維持

フェールセーフ：故障が起きても安全側になるように設計。

フェールオーバー：ほかのシステムに自動的に切り替える。

フォールトマスキング：外部に影響がないようにする。

フールプルーフ：誤った使い方などをしても

 

  • フォールトアボイダンス

故障が起きにくい構成にする。

 

複数のコンピュータを一つのコンピュータとして扱えるようにする。

HAクラスタ構成：

　フェールオーバクラスタ：いわゆるホットスタンバイ方式

　負荷分散クラスタ：処理が集中しないようにする

 

  • グリッドコンピューティング

HPC（ハイパフォーマンスコンピューティング）を実現するテクノロジー。ネットワーク上の複数のコンピュータで大規模な１つの処理を行う。

 

  • RAID：磁気ディスクを並列に並べて１つのディスクとして扱う。

０：ストライピング。１つでも止まると全体が止まる。

１：ミラーリング。どれか１つでも動いていればいい。

２：ストライピングとハミング符号。信頼度アップ。

３：ビット単位のストライピング。パリティを追加して復元できるように。

４：ブロック単位のストライピング。パリティを追加して復元できるように。

５：ブロック単位のストライピング。パリティをよりやりやすくした。

６：ブロック単位のストライピング。二種のパリティ。

０１：ストライピングとミラーリングの組み合わせ。

 

  • ストレージ接続形態

DAS：Direct Attached Storage。サーバに直接接続。

NAS：Network Attached Storage。LANに直接接続。NFSやCIFSなどのファイル共有プロトコルに対応。

SAN：Storage Area Network。ストレージ専用のネットワーク。

 

処理要求から処理結果出力開始までの時間。

  • ターンアラウンドタイム

ジョブ投入から出力終了まで。

 

  • SPEC

プロセッサの性能評価

オンライントランザクション処理の性能評価

 

  • サーバの性能向上策

スケールアウト：サーバの数を増やす

スケールアップ：サーバをより高性能にする

オートスケール：クラウドサーバ数が動的に変化

 

応用情報　学習備忘録（2024/02/01）

応用情報の勉強で得た知識のメモ。

間違った解釈や補足などあったらコメントください。

 

  • MA法

NAND回路のみで論理回路を実装する方法

 

ユーザーが自由に設計できるLSI。機能の記述（ハードウェア記述言語）、論理合成（回路への変換）、配置配線のステップで実装される。

 

  • SystemC

C++をベースとしたシステムレベル記述言語でハードウェア記述言語より抽象的。ソフトウェアとハードウェアを一貫して記述できるためハードとソフトの整合性がとりやすい。

 

  • IPコア

SoCなどの構成に使われ、再利用可能である。ソフトウェアでのライブラリに相当する。

 

  • ダイナミック電力

回路ブロックのスイッチングにより消費される電力。電源電圧Vの二乗と周波数fの席に比例する。

 

  • ダイナミック電力を小さくする手法

マルチVDD：高速に動作する必要のない回路ブロックではVを下げる。

DVS：負荷の大きさに応じてVの大きさを動的に変更する。

DVFS：Vだけでなくfも動的に変更する。

 

  • スタティック電力

動作にかかわらず漏れ出すリーク電力。

 

  • スタティック電力を小さくする手法

パワーゲーティング：動作しない回路ブロックには電源供給しないようにする

⇔電力供給がないとデータを保持できない

⇒リーク電力の少ないリテンションフリップフロップに一時的にデータを移す。

 

  • A/Dコンバータ

アナログ信号をデジタル信号に変換する。分解能とサンプリング周波数により変換の精度が決まる。

分解能：デジタル信号が1変化するにはアナログ信号がいくつ変化する必要があるか。

例）３ビットで４Vの範囲を表す時の分解能は

　　4 ÷ 2^3 = 0.5 V になる

 

  • シーケンス制御

あらかじめ決められた順序に従って制御する。リレー回路とラダー図をもちいたPLC。

 

外乱による影響をフィードバックして制御する。

 

外乱による影響を極力なくすように修正する。通常、フィードバック制御と併用される。

 

温度によって抵抗値が変わる。

 

  • 距離画像センサ

対象との距離を測るセンサ。TOF方式が最もよく使われている。

TOF方式：レーザーなどが反射してセンサにたどり着くまでの時間を用いて距離を求める。

 

  • ホール素子

ホール効果（電流に磁場をかけると起電力が発生する）を用いる非接触型のセンサ。

 

  • アクチュエータ

電気エネルギーや流体エネルギー（空気圧など）を回転、並進運動などに変換する。アクチュエータの駆動回路として主なものにPWM（パルス幅変調）制御がある。

PWM制御：１周期に対するONの時間の比率（デューティ比）を大きくするとモーターの速度が速くなる。

 

マイクロプロセッサ。CPUの機能をLSIに実装したもの。

 

デジタルシグナルプロセッサ。デジタル信号の処理に特化していて、積和演算が速い。

 

  • ワイヤードロジック

論理回路の組み合わせによって必要な処理を実現する。高速な一方、複雑な処理の実装には向かない。

 

  • 命令実行の順番

命令フェッチ→命令解読→オペランドアドレスの計算→オペランドフェッチ→実行

 

割り込みによってプログラムの実行が中断された際に、割り込み終了後にプログラムの再開ができるようにスタックに退避される情報。

 

  • 内部割込みの種類

プログラム割込み：オーバーフローや０による除算などが原因。

SVC割込み：スーパーバイザーコール割込み。OSのカーネル部が呼び出されたときの割込み。ファイル入出力など。

ページフォルト：主記憶のデータが存在しない位置を参照しようとしたときの割込み。

 

  • 外部割込みの種類

タイマ割込み：時間が超過したとき。主にマルチタスクの時。

コンソール割込み：操作者が主導でする割込み。

入出力割込み：キーボード操作やディスク読み込みの終了など。

機械チェック割込み：ハードウェアに不具合が生じたときの割込みで優先順位が最も高い。

 

単位時間当たりの処理量

 

  • ハザード

パイプライン処理が乱れることとその要因。

制御（分岐）ハザード：分岐命令によって先読みした命令が無駄になること。

投機実行：分岐先を予測して実行すること。

遅延分岐：分岐命令の後に実行しても問題ない命令は分岐後に実行することで分岐先特有の命令が分岐前に先読みされることを防ぐ。

 

  • パイプライン処理の処理時間の求め方

（D+N-1）× P

D：パイプラインの深さ。１命令当たりのステップ数。

N：命令数

P：パイプラインのピッチ。１ステップ当たりの実行時間。

 

  • スーパースカラ

複数のパイプラインを用いる。

 

Very Long Instruction Wordの略。互いに影響のない複数の命令をまとめて１つの命令のように同時に実行すること。まとめる命令数が一定になるように、数が足りない場合はダミー命令（NOP命令）が使われる。

 

 

 

使用した参考書

https://www.amazon.co.jp/%E4%BB%A4%E5%92%8C06%E5%B9%B4%E3%80%90%E6%98%A5%E6%9C%9F%E3%80%91%E3%80%90%E7%A7%8B%E6%9C%9F%E3%80%91-%E5%BF%9C%E7%94%A8%E6%83%85%E5%A0%B1%E6%8A%80%E8%A1%93%E8%80%85-%E5%90%88%E6%A0%BC%E6%95%99%E6%9C%AC-%E5%A4%A7%E6%BB%9D-%E3%81%BF%E3%82%84%E5%AD%90/dp/4297138654/ref=asc_df_4297138654/?tag=jpgo-22&linkCode=df0&hvadid=676036410708&hvpos=&hvnetw=g&hvrand=4910407951911125569&hvpone=&hvptwo=&hvqmt=&hvdev=c&hvdvcmdl=&hvlocint=&hvlocphy=1009343&hvtargid=pla-2247804171598&psc=1&mcid=42f91342aeb536a5ae0465c77c37f2db&th=1&psc=1&gad_source=1

応用情報　学習備忘録（2024/01/29-31）

応用情報の勉強で得た知識のメモ。

間違った認識、補足説明などあればコメントで教えてください。

 

  • 情報量

確率Pで起きる事象の情報量Iは底が2の対数を用いて以下の式であらわされる

I = -logP

単位はビット。その事象が起こることを説明するのに何ビット必要か的な考え方。

1/全事象 の情報量は全事象を表現するのに必要なビット数に等しい。

例）8面のサイコロの出目を表すためには -log1/8 = 3 ビット必要

 

各事象の情報量の総和Hのこと。

H = Σ(P×I)

期待値の式っぽい。平均情報量ともいう。小さいほど事象のあいまいさが小さい。

最大平均情報量はすべての事象の発生確率が同じとき。

 

  • ハフマン符号化

出現率が高いものは短いビット列、低いものは長いビット列であらわすことで圧縮する。

 

  • ランレングス符号化

同じ文字の繰り返しを連続回数とその文字を用いて書くことで圧縮。

例）AAAABCC -> 3A0B1C　（数字は繰り返し回数ー１になる）

 

  • 有向グラフに関する語句

頂点に入ってくる辺の数：入次数

頂点から出ていく辺の数：出次数

次数：上記二つの和

自己ループ：端点が同じ辺（スタートとゴールが一緒）

多重辺：スタート地点が同じかつ行き先が同じ辺たち

 

最短経路問題の解法の一つ。多重辺が生まれたときはコスト最小の辺のみ残しながら一個ずつノードを消していって最終的にスタートとゴールのみにする。

 

いくつかの状態があるとき、ある状態が現れる確率が直前の状態に依存する（推移確率）。

例）明日晴れる確率は今日の天気によって変わる。

 

P（μ-σ≦X≦μ+σ）≒ 0.683

P（μ-2σ≦X≦μ+2σ）≒ 0.954

P（μ-3σ≦X≦μ+3σ）≒ 0.997

母集団N(μ, σ^2)のとき標本平均はN(μ, σ^2/n)、標本合計はN(n*μ, n*σ^2)に近づく。

 

  • ロジスティック回帰分析

yが0か1かであらわせるときに使う。

 

  • 誤差

絶対誤差=|真値ー近似値|

相対誤差=|絶対誤差÷真値|=|1ー近似値/真値|

 

 

 

 

使っている参考書

www.amazon.co.jp