７月1日
応用情報
仮想記憶管理
仮想記憶方式は、磁気ディスクなどの補助記憶を利用することによって、主記憶の物理的容量よはるかに大きなアドレス空間を提供する方式。
プログラムの実行の際には、仮想アドレスから主記憶上の実アドレへの変換が行われまこのアドレス変換を動的アドレス変換（ＤＡＴ）という。実際にこれを行うハードウェア装置がＭＭＵ（メモリ管理ユニット）です。
ページんグ方式
仮想アドレスと実アドレスの対応付けをページテーブルというアドレス対応表を用いて行う。
主記憶上にあるページテーブをアドレス変換のたびにアクセスすると、命令実行の処理速度が低下する。そこで、MMU内部にあるTLBという一種のキャッシュを用いてアドレス変換を高速化を実現します。
ＴＬＢ・・・アドレス変換バッファ、連想レジスタと呼ばれる。
ページフォルト
プログラムの実行中、処理に必要なページが主記憶に存在しない状態が起きた時、これをページフォルトが発生したといいます。
ページインのアルゴリズムには、デマンドページングとプリページングの２つがある。
デマンドページングは、ページフォルトが発生した際に、該当ページを読み込む方式。
プリページングは、近い将来必要とされるページを予測し、あらかじめ主記憶に読み込んでおく方式。
ページイン・・・ページを主記憶に読み込むこと。
ページアウト・・・主記憶から追い出して補助記憶に書き出すこと。
スラッシング
仮想記憶システムでは、プログラムの多重度が高く、各プログラムへの割り当て主記憶容量が小さかったり、適切なページ置き換え方法がとられなかったりするとページが多発します。ページングが多発すると、プログラムに割り当てられるCPU時間が少なくなります。これにより、処理速度が極端にわるくなり、システム全体のスループットが急激に低下するという現象が発生します。この現象をスラッシングという。
ワーキングセット
プログラムには、局所参照性の性質があるといわれている。
参照された場所の近くが引き続き参照される可能性が高く、離れた場所が参照される可能性は低いというもの。
プログラム実行時にその局所参照性を把握し、各時点で局所参照しているページの集合、すなわちそのプログラムの過去Ｔ時間に参照されたページの集合を管理し、主記憶内に保存するようにします。このページの集合をワーキングセットという。
言語処理ツール
プログラミング言語で記述されたプログラムを原始プログラム（ソースプログラム）あるいはソースコードという。
原始プログラムを別の形に変換するソフトウェアを総称して、言語プロセッサという。
ジェネレータ（生成系）
手続きを記述しなくても処理条件となる入力、処理、出力に関する引数を指定するだけで自動的にプログラムを生成する言語プロセッサ。
シュミレータ（実行系）
他のコンピュータ用のプログラムの命令を解読しながら実行する言語プロセッサで、これをハードウェアで行うものエミュレータえという。
コンパイラの処理
・字句解析
プログラムを表現する文字の列、変数名、演算子、予約語、定数、区切り記号など、意味を持つ最小単位である字句（トークン）の列に分解する。
・構文解析
字句解析で切り出されたトークンをプログラム言語の構文規則に従って解析し、正しい分であるかを判定する。
・意味解析
・最適化
・コード生成
コンパイラによって生成された目的プログラムを実行可能プログラム（ロードモジュール）にするためには、プログラムで使用しているライブラリモジュールなど、実行に必要なものをまと目あげる必要があります。これをリンクといい、それを行うプログラムをリンカという。
開発ツール
静的テストツール
プログラムを実行することなく検証を行うツール
・構文チェッカ
言語で定められた構文に従ってプログラムが記述されているかを検証する。
・コードおーディタ
ソフトウェア開発において独自に定めたプログラミング規約に違反していないかを検査する。
・モジュールインタフェースチェックツール
モジュール間のインターフェースの不一致、すなわち実引数と仮引数の個数や、対応する引数のデータ型の不一致を検出する
動的テストツール
アサーションチェッカ
プログラムの処理の正当性を検証するためのツール。プログラムの任意の位置にアサーション（成立いていなければならに変数間の関係や条件）を記述した論理式をうめこむことで、実行時にその論理式成立しているか否かを検証できる。
トレーサ
追跡プログラムとも呼ばれ、命令単位、あるいは、指定した範囲でプログラムを実行し、実行直後のレジスタの内容やメモリの内容など、必要な情報が逐次得られるつーる。
テストカバレージ（分析）ツール
プログラムに存在するすべての命令あるいは経路のうち、テストによって実行できた部分の割合をカバレージ（網羅率）という。ホワイトボックステストにおいてカバーレジを測定するツール。
プロファイラ
プログラムの性能を分析するためのツール。
ＩＣＥ
ソフトウェアやハードウェアのデバッグを行うための装置であ。
開発を支援するツール
IDE
ソフトウェアの開発作業全体を一貫して支援する統合開発環境です。エディタやコンパイラ、リンカ、デバッガに加え、その他の支援ツールをまとめて提供する。
リポジトリ
ソフトウェアの開発及び保守における様々な情報を一元的に管理するためのデータベース。
UNIX系OSの基本用語
シェル
ユーザとOS間のインタフェースとなるプログラム。ユーザが入力したコマンドを解釈し、対応する機能を実行するようにOSに指示し、OSからの結果を待ってそれをユーザに返す。
ソケット
アプリケーション間で通信を行うためのプログラムインタフェースで、通信の出入り口となるもの。
デーモン
OSの機能の一部を提供するプロセスで、デーモンプロセスとも呼ばれる。
OSS（オープンソースソフトウェア）
ソースコードをインターネットなどを通じて公開し、誰でもそのソフトウェアの利用や改変、再頒布を行うことを可能にしたソフトウェア。
もう７月が始まった。勝負の７月だと思っている。応用情報、atcoder,できればWEB開発の勉強、もっと欲を言えば、コンピュータシステムの理論と実装という技術書を買って学びたい。
一日も無駄にはしない。07/02 13:30
7月2日
atcoder
【問題概要】
10000 円札と、5000 円札と、1000 円札が合計でN枚あって、合計金額が円であったという。このような条件を満たす各金額の札の枚数の組を 1 つ求めなさい。そのような状況が存在し得ない場合には -1 -1 -1 と出力しなさい。
考え方
普通に全探索すると３重ループになり計算量オーバー
二つの値が求まれば三つ目の値も求まる。
# include <iostream>
using namespace std;
int main() {
int N, Y;
cin >> N >> Y;
int res10000 = -1, res5000 = -1, res1000 = -1;
for (int a = 0; a <= N; ++a) { // 10000円の枚数を 0 〜 N で調べる
for (int b = 0; b + a <= N; ++b) { // 5000円の枚数を 0 〜 N-a で調べる
int c = N - a - b; // 1000円の枚数は決まる
int total = 10000*a + 5000*b + 1000*c;
if (total == Y) { // 答えが見つかったら
res10000 = a;
res5000 = b;
res1000 = c;
}
}
}
// 答えを出力 (見つかっていなくても -1 -1 -1 になるので OK です)
cout << res10000 << " " << res5000 << " " << res1000 << endl;
}
【問題概要】
英小文字からなる文字列Sが与えられます。Tが空文字列である状態から始めて、以下の操作を好きな回数繰り返すことで
S＝Tとすることができるか判定してください。の末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加する。
考え方
dreameraserを先頭から順に５文字dreamまで読み進めたとき、そこできっていいのか次のerまで進んでdreamerできるべきなのか判断することは容易ではなさそう。
なので後ろから見る。
# include <iostream>
# include <string>
# include <algorithm>
using namespace std;
string divide[4] = {"dream", "dreamer", "erase", "eraser"};
int main() {
string S;
cin >> S;
// 後ろから解くかわりにすべての文字列を「左右反転」する
reverse(S.begin(), S.end());
for (int i = 0; i < 4; ++i) reverse(divide[i].begin(), divide[i].end());
// 端から切っていく
bool can = true;
for (int i = 0; i < S.size();) {
bool can2 = false; // 4 個の文字列たちどれかで divide できるか
for (int j = 0; j < 4; ++j) {
string d = divide[j];
if (S.substr(i, d.size()) == d) { // d で divide できるか
can2 = true;
i += d.size(); // divide できたら i を進める
}
}
if (!can2) { // divide できなかったら
can = false;
break;
}
}
if (can) cout << "YES" << endl;
else cout << "NO" << endl;
}
substr は文字を（ここから、ここまで）を指定できる関数
|A|B|C|D|
0 1 2 3 4
動的計画法でとくと
#include <iostream>
#include <string>
using namespace std;
string divide[4] = {"dream", "dreamer", "erase", "eraser"};
bool dp[100010];
int main() {
string S;
cin >> S;
dp[0] = 1;
for(int i = 0; i < S.size(); ++i){
if(!dp[i])continue; // そこまでで矛盾があったらとりあえず無視
for(string s : divide){
if(S.substr(i, s.size()) == s){ // うまく切れたら先に進む
dp[i + s.size()] = 1;
}
}
}
cout << (dp[S.size()] ? "YES" : "NO") << endl;
return 0;
}
幅優先探索では
#include <iostream>
#include <queue>
using namespace std;
string divide[4] = {"dream", "dreamer", "erase", "eraser"};
int main() {
string S;
cin >> S;
queue<int> BFS;
bool can = false;
BFS.push(0);
while(!BFS.empty()){ // キューが空になるまで続ける
int t = BFS.front();
BFS.pop();
if(t == S.size()){ // 最後まで切れたら成功
can = true;
break;
}
for(string s : divide){
if(S.substr(t, s.size()) == s){ // 切れたらとりあえず切ったことにしてみる
BFS.push(t + s.size());
}
}
}
cout << (can ? "YES" : "NO") << endl;
return 0;
}
この問題結構深いきがする、、、
この問題は明日も読み返す、、、、
問題概要めんどいのでリンク
考え方
時間の差をとる。ｘ、ｙの差分の足し算をとる。
時間の割にｘ、ｙが遠いときは確定無理。
時間の差が奇数、ｘ、ｙの差分の足し算が偶数だと無理、逆もしかり。
# include <iostream>
using namespace std;
int main() {
int N;
int t[110000], x[110000], y[110000];
cin >> N;
t[0] = x[0] = y[0] = 0; // 初期状態
for (int i = 0; i < N; ++i) cin >> t[i+1] >> x[i+1] >> y[i+1]; // 1-index にしておく
bool can = true;
for (int i = 0; i < N; ++i) {
int dt = t[i+1] - t[i];
int dist = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i]);
if (dt < dist) can = false;
if (dist % 2 != dt % 2) can = false; // dist と dt の偶奇は一致する必要あり！
}
if (can) cout << "Yes" << endl;
else cout << "No" << endl;
}
今日もっとできた。グダグダしすぎた。絶対お金持ちになるって気持ちでやれ。おんがえしするつもりでやる。大学卒業したら大企業に入る。そして技術力つけてフリーランスで稼ぎまくる。だいぶ大雑把だけどこの目標を忘れずにやっていきたい。日本はいい国だから失敗しても普通にはなれる。普通なんてないけど、、、 ただでさえ後悔してることがあるんだからもう後悔ないようにいきろ。7/03 1:10
７月４日
応用情報
データベース設計手順
概念設計→論理設計→物理設計
概念設計
対象とする実世界のデータをすべて調査・分析して、抽象化した概念データモデルを作成する。概念データモデルは、コンピュータへの実装を意識せずに、単にデータの持つ意味とデータ間の関連をあるがままにじ表現することに重点が置かれたデータモデル。
データモデル・・・データ体系や業務のルールを一定の基準に従って表現したもの。
データ分析
概念設計のデータ分析では、業務で使用されている帳票や伝票、画面などを調査して、どのようなデータ項目があるのか、どのデータが必要なのか、そのすべてを洗いだします。各データの関連を整理して正規化を行う。
データの分析手法には、画面や帳票などから項目を洗い出し、データ分析を行った結果として現実型の概念データモデルを作成するボトムアップアプローチと、最初に理想型の概念データモデルを作成してからデータ分析を行うトップダウンアプローチの２つがある。
論理設計
概念データモデルを、データベースに実装できる形式、すなわち論理データモデルに変換します。
論理データモデルは、データベース構造モデルとも呼ばれるデータモデルである。利用者とデータベース間のインタフェースの役割を担うデータモデルであるため、どのデータベースを用いて実装するかによって、用いられる論理データモデルが異なる。
関係モデルへの変換
関係データベースを用いて実装する場合、概念データモデルを基に、主キーや外部キーを含めたテーブル構造を作成する。
物理設計
データベースに要求される性能を満たすための設計である。最適なアクセス効率及び記憶効率が得られるように、データベースの物理構造を設計します。
３層スキーマ構造
データベースは、環境の変化や時間の経過とともに実世界が変わると、少なからずその影響をうけ、変更を余儀なくされることもある。このような変更の多くは、データベース内のデータを変更する対応ができますが、場合によってはデータ構造や物理的な格納構造の変更が必要な場合もある。
そこで、データベースの構造を変更しても、その影響をアプリケーションプログラムが受けないようにするために、データの記述及び操作を行うための枠組み（スキーマ）を、外部、概念、内部の３層に分けて管理しようと考えられたのが３層スキーマ構造。
外部スキーマ・・・利用者やアプリケーションプログラムから見たデータの記述。関係データベースのビュー定義が外部スキーマ定義に相当する。
概念スキーマ・・・データベース全体の論理的データ構造の記述。
内部スキーマ・・・概念スキーマコンピュータ上に具体的に実現させるための記述。
これによりデータの独立性を確保する。
３層スキーマ構造におけるデータの独立性は、論理データ独立性と物理データ独立性に分けられる。論理データ独立性とは、実世界の変化におうじて概念スキーマを変更する必要が生じた場合でも、変更は、アプリケーションプログラムとは独立に行えるという特性。物理データ独立性は、データの物理的な格納構造を変更してもアプリケーションプログラムに影響が及ばない、すなわちアプリケーションプログラムとは独立に内部スキーマの変更ができるという特性。
インメモリデータベース・・・データを直接メモリに配置することにより最速のパフォーマンスを得ることを可能とするデータベースです。
ER図
対象世界にある情報を、実体と実体の関連（リレーションシップ）の２つの概念で表した図
実体とは実世界を構成する要素であり、実世界をモデル化するときの対象物。いずれのエンティティもそれ自体の性質や特徴を表すいくつかの属性を持つ。それが具体的な値を持つときそれをインスタンスという。
関連とは、顧客は商品を注文する、社員は組織に所属するといった業務上の規則やルールなどによって発生するエンティティ間の関係のこと。
エンティティ間に多対多の関連がある場合、関係データベースへの実装が難しくなる。そこで、１対多と多対１の関連に分解します。多対多のエンティティ間に介入させたエンティティを連関エンティティという
atcoder
考え方
まずa1を０と仮定しても一般性は失われない
なぜ
ci,j=ai+bjでa1を０にしても一般性を失われない理由は、aiとbjの和でしか各マスが決まらないという構造にある。
これは未知数の自由度を１つ減らして計算を簡単にするテクニックらしい、、、
例：a₁を0にしたい場合
たとえば、行1の値（a₁）を0にしたいとします。
そうすると、列の値（b₁, b₂, b₃）を調整して、全体の数字が変わらないようにできます。
どうやるか？
もともと a₁ が 5 だったとします。
a₁ を 0 にする代わりに、b₁, b₂, b₃ を全部 5 増やします。
計算してみると…
もともと c₁₁ = a₁ + b₁ = 5 + 2 = 7
a₁ を 0、b₁ を 7（2+5）にすると、c₁₁ = 0 + 7 = 7
どのマスも、合計は変わりません！
とても分かりやすいな
DFS（深さ優先探索）
SからTへたどりつけるか
有効グラフＧの２頂点があたえられたとき、ｓから辺をたどってｔに到達できるかを判定する。
# include <iostream>
# include <vector>
using namespace std;
using Graph = vector<vector<int>>;
// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
seen[v] = true; // v を訪問済にする
// v から行ける各頂点 next_v について
for (auto next_v : G[v]) {
if (seen[next_v]) continue; // next_v が探索済だったらスルー
dfs(G, next_v); // 再帰的に探索
}
}
int main() {
// 頂点数と辺数、s と t
int N, M, s, t; cin >> N >> M >> s >> t;
// グラフ入力受取
Graph G(N);
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
// 頂点 s をスタートとした探索
seen.assign(N, false); // 全頂点を「未訪問」に初期化
dfs(G, s);
// t に辿り着けるかどうか
if (seen[t]) cout << "Yes" << endl;
else cout << "No" << endl;
}
dfsは再帰と相性が良い
頂点ｓから頂点ｔへたどり着けるか
10 10
10 10
s.........
######### .
# .......#.
# ..####.#.
## ....#.#.
##### .#.#.
g.#.#.#.#.
# .#.#.#.#.
# .#.#.#.#.
# .....#...
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
# include <iostream>
# include <vector>
# include <string>
# include <cstring>
using namespace std;
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
// 入力
int H, W;
vector<string> field;
// 探索
bool seen[510][510]; // seen[h][w] := マス (h, w) が検知済みかどうか
void dfs(int h, int w) {
seen[h][w] = true;
// 四方向を探索
for (int dir = 0; dir < 4; ++dir) {
int nh = h + dx[dir];
int nw = w + dy[dir];
// 場外アウトしたり、移動先が壁の場合はスルー
if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
if (field[nh][nw] == '#') continue;
// 移動先が探索済みの場合
if (seen[nh][nw]) continue;
// 再帰的に探索
dfs(nh, nw);
}
}
int main() {
// 入力受け取り
cin >> H >> W;
field.resize(H);//大きさを定める
for (int h = 0; h < H; ++h) cin >> field[h];
// s と g のマスを特定する
int sh, sw, gh, gw;
for (int h = 0; h < H; ++h) {
for (int w = 0; w < W; ++w) {
if (field[h][w] == 's') sh = h, sw = w;
if (field[h][w] == 'g') gh = h, gw = w;
}
}
// 探索開始
memset(seen, 0, sizeof(seen)); // seen 配列全体を false に初期化
dfs(sh, sw);
// 結果
if (seen[gh][gw]) cout << "Yes" << endl;
else cout << "No" << endl;
}
連結成分の個数
連結とは限らない無向グラフが与えられたとき、それが何個の連結成分からなるのかを数える問題を考えます。
考え方
・まだ探索済みでない頂点ｖを１つ選んでｖを始点としたＤＦｓを行う。
# include <iostream>
# include <vector>
using namespace std;
using Graph = vector<vector<int>>;
// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
seen[v] = true;
for (auto next_v : G[v]) {
if (seen[next_v]) continue;
dfs(G, next_v); // 再帰的に探索
}
}
int main() {
// 頂点数と辺数
int N, M; cin >> N >> M;
// グラフ入力受取
Graph G(N);
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
// 全頂点が訪問済みになるまで探索
int count = 0;
seen.assign(N, false);
for (int v = 0; v < N; ++v) {
if (seen[v]) continue; // v が探索済みだったらスルー
dfs(G, v); // v が未探索なら v を始点とした DFS を行う
++count;
}
cout << count << endl;
}
いろいろあって書くのが遅くなった。きょうはあとちょっとしかないけどatcoderの過去問を解くのと応用情報の勉強をする。
7/4 17:42
7月４日
atcoder
解き方は2種類
１つめ ３パターンで解く
1,AピザBピザを直接買う場合
2,ABピザだけで必要数を満たす場合
3,ABピザでまかなえるだけまかねい、残りをAまたはBで補う
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
// 入力
int A, B, C, X, Y;
cin >> A >> B >> C >> X >> Y;
// 1. AピザとBピザを直接買う場合
int cost1 = A * X + B * Y;
// 2. ABピザだけで必要数を満たす場合
int maxXY = max(X, Y);
int cost2 = C * 2 * maxXY;
// 3. ABピザでまかなえるだけまかない、残りをAまたはBで補う場合
int minXY = min(X, Y);
int cost3 = C * 2 * minXY + A * (X - minXY) + B * (Y - minXY);
// 最小値を計算
int answer = min({cost1, cost2, cost3});
cout << answer << endl;
return 0;
}
もう一つのパターン
普通に全探索
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int A, B, C, X, Y;
cin >> A >> B >> C >> X >> Y;
int max_pizza = max(X, Y);
int ans = 1e9; // 十分大きな値で初期化
for (int ab = 0; ab <= 2 * max_pizza; ab += 2) {
int a_needed = max(0, X - ab / 2);
int b_needed = max(0, Y - ab / 2);
int cost = ab * C + a_needed * A + b_needed * B;
ans = min(ans, cost);
}
cout << ans << endl;
return 0;
}
#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>
#include<string>
#include<set>
#include <map>
#include <queue>
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include<stack>
#define rep(i,n) for(int i=0;i<(n);++i)
using ll=long long;
int main(){
ll n;
cin>>n;
int ans=10;
for(ll a=1;a*a<=n;++a){
int counta=0,countb=0;
if(n%a==0){
ll b=n/a;
ll tmpa=a,tmpb=b;
while(tmpb!=0){
tmpb/=10;
countb++;
}
while(tmpa!=0){
tmpa/=10;
counta++;
}
ans=min(ans,max(counta,countb));
}
}
cout<<ans;
return 0;
}
#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>
#include<string>
#include<set>
#include <map>
#include <queue>
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include<stack>
#define rep(i,n) for(int i=0;i<(n);++i)
using ll=long long;
int main(){
int n;
cin>>n;
int x[n],y[n],h[n];
rep(i,n)cin>>x[i]>>y[i]>>h[i];
for(int cx=0;cx<=100;++cx){
for(int cy=0;cy<=100;++cy){
int H;
for(int k=0;k<n;++k){
if(h[k]>0){
H=h[k]+abs(x[k]-cx)+abs(y[k]-cy);
break;
}
}
bool ok=true;
for(int k=0;k<n;++k){
int expected = max(H - abs(x[k] - cx) - abs(y[k] - cy), 0);
if (h[k] != expected) {
ok = false;
break;
}
}
if(ok){cout<<cx<<" "<<cy<<" "<<H;
return 0;}
}
}
return 0;
}
もう金曜日が終わった。はやい。ほんとにはやい。まだまだつきつめられるとおもう。口より脳をうごかせ。やれ。
7/5 0:11
7月5日
応用情報
関係データベース
関係モデル
集合論に基礎をおいた論理データモデル
表のことを関係 表の各行に格納される1組のデータをタプル タプルはいくつかの属性から構成される
関係データベース
関係モデルをコンピュータ上実装したもの。
属性の定義域
タプルは、同一特性をもった値の集合（定義域、ドメイン）から一定の意味を持たせるために、1つずつ要素取り出して作成されたデータの組といえる。
関係データベースのキー
スーパキー・・・表中の行を一意に特定できる属性、あるいは属性の組をスーパキーという。
候補キー・・・スーパキーのうち、余分な属性を含まず、行を一意に識別できる必要最小限の属性によって構成されるスーパキー。
主キー・・・候補キーの中からデータ管理上最も適切だと思われるもの。選ばれなかったそれ以外を代理キーという。
主キーには、一意性制約の他、実態を保証するための空値は許さないという、NOT NULL制約が設定される。これの主キーが持つ制約を主キー制約という。
外部キー・・・関連する表の候補キーを参照する属性、または属性の組のこと。外部キーの値は、NOT NULL制約が定義されていなければ空値はゆるされる。
主キーが複数の属性から構成される複合キーである場合、その構成属性数が多すぎると運用面で面倒。連番など意味のない属性を追加して、それを代用キーとする。そして複合キーを構成している属性は代理キーにする。
正規化
関数従属
ある属性ｘの値が決まると他の属性ｙの値が一意的に決まる関係を関数従属という。ｘ→ｙ この時、属性ｘを独立属性 属性ｙを従属属性という。
部分関数従属
真部分集合・・・集合ｘ１がｘの部分集合であり、ｘ１＝ｘではないとき。ｘ１＝ｘの真部分集合という。
ｘ→ｙの関係において、ｙがｘの真部分集合にも関数従属するとき
、ｙはｘに部分関数従属するという。
完全関数従属
ｘ→ｙの関係において、ｙがｘのどの真部分集合にも関数従属しないとき、これを完全関数従属という。
推移的関数従属
直接ではなく間接的に関数従属している関係。ｘ→ｙ、ｙ→z y！→ｘが成立しているとき、ｚはｘに推移的関数従属しているという。ｚ！→ｙが成立していれば完全推移的関数従属しているという。
正規化の手順
第一正規化
繰り返し部分を排除する操作。
第一正規形におけるデータ操作での不具合
第一正規形はデータが冗長であるため、このままではデータ操作時に不具合が生じます。この不具合は更新時異常とよばれる。
修正時異常
商品名を変更する場合、該当する行をすべて同時に変更しなければならない。
挿入時異常
売上明細表の主キーが複合キーとなっているため、売上のない商品は登録することができない。
削除時異常
売上実績が１つしかない商品の場合、その売り上げデータを削除すると、商品データも削除されてしまいます。逆に、商品データを残そうとすれば、売上データは削除できない。
第２正規化
主キーの一部に部分関数従属する非キー属性を別の表に分解する操作。
すべての非キー属性が、主キーに完全関数従属である状態にする操作。
主キーが複数の属性で構成されている場合にのみ第2正規化を行う。
第３正規化
主キーに推移的関数従属している非キー属性を別の表に分解する操作。
どの非キー属性も主キーに直接に関数従属している状態にする操作。
正規化の目的は、データ操作に伴う更新時異常の発生を防ぐこと。正規化により属性間の関数従属を少なくし、かつ、データの重複を排除することで更新時異常の発生を防ぐことができる。
関係演算
選択演算は、表から指定した行を取り出す演算
射影演算は、表から指定した列をとりだす演算
結合演算は、２つの表が共通に持つ項目で結合を行い、新しい表を作り出す関係演算。比較演算子が＝である結合を等結合。
商
商（R÷S）は、表R中から表Sすべての行を含む行を取り出し、そこから表Ｓの項目が取り除かれる。
SQL
データの検索、挿入、更新、削除おこなう。
基本的なSQL問い合わせ
例えば、社員表から 年齢が２４歳以上２８歳以下 の社員の社員コード及び社員名を求める場合、FROM句に社員表を指定し、WHER句に条件そしてSELECT句に社員コード、社員名を記述
SELECT 社員コード、社員名
FROM 社員
WHERE 年齢＞＝２４、AND 年齢＜＝２８
IS NULL述語
列の値が空値（NULL）であるかを判定する場合、列名＝NULL ではなく列名 IS NULL で記述しなければならない。所属部門が決まっている社員を求める場合は 部門コード IS NOT NULLと記述する。
BETWEEN述語
列の値が 値１～値２の範囲に含まれるかを判定する場合に使う。２４歳以上２８歳以下の社員を求める場合、
SELECT 社員コード、社員名
FROM 社員
WHERE 年齢 BETWEEN ２４ AND ２８とかく。
BETWEENの前にNOTをつけると否定になる。
IN述語
列の値が括弧内に記述された値リストのいずれかと等しいかを判定する場合に使います。上の例と同じにすると
SELECT 社員コード 社員名
FROM 社員
WHERE 年齢 IN （２４，２５，２６，２７，２８）と記述する。
これもINの前にNOTをつけると否定になる。
LIKE述語
列の値があるパターン値に合致するかどうかを判定する場合に使う。
WHERE 社員名 LIKE ’％子’とやると社員名の最後の子がついた社員を抽出する。
パターン文字
％・・・A%BとやるとAから始まってBで終わるになる。
＿・・・a_ _b,はaで始まりbで終わる４文字の文字列と合致する。
グループ化
取り出された行を、GROUP BY句で指定した列の値でグループ化し、グループごとに合計や平均値、最大値などをもとめることができる。HAVING句をもちいると条件に合ったグループだけをとりだす。
出力順の指定
昇順、降順に並び替えるときは、ORDER BY句を使う。昇順の場合はASC 降順の場合はDESC ASCは省略可能
例 SELECT 社員名、年齢
FROM 社員
ORDER BY 年齢 DESC
表の結合
内結合
等結合と同じ結果がえられる演算である。
内結合では、結合する表をFROM句の中でJOINを使って指定し、結合条件はJOINに続くON句で指定する。
例 FROM 社員 INNER JOIN 部門 ON 社員.部門コード＝部門.部門コード
外結合
結合列の値が一致しない行も結果に反映することができる結合演算。
結合相手の表に該当行がない場合、それをNULLで埋めて結合する。
左外結合・・・キーワードJOINの前に記述した表を基準にして、JOINの後に記述した表に存在しない行をNULLで埋めて結合する。
右外結合・・・左外結合の逆。
完全外結合・・・左外結合と右外結合を組み合わせた演算。
COALESCE式
複数の引数を左から順に評価し、「最初にNULLでない値」を返します。すべての引数がNULLの場合は、結果もNULLとなります
COALESCE(引数1, 引数2, ..., 引数N)
atcoder
考え方
増加、減少、未定の三種類の状態を定義する。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for(int &x : a) cin >> x;
int ans = 0;
int i = 0;
while (i < n) {
ans++;
int j = i;
// 状態: 0=未定, 1=増加, -1=減少
int state = 0;
while (j + 1 < n) {
if (state == 0) {
if (a[j] < a[j+1]) state = 1;
else if (a[j] > a[j+1]) state = -1;
} else if (state == 1) {
if (a[j] > a[j+1]) break; // 増加→減少で切る
} else if (state == -1) {
if (a[j] < a[j+1]) break; // 減少→増加で切る
}
j++;
}
i = j + 1;
}
cout << ans << endl;
return 0;
}
#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>
#include<string>
#include<set>
#include <map>
#include <queue>
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include<stack>
#define rep(i,n) for(int i=0;i<(n);++i)
using ll=long long;
int main(){
int n,c,k;
cin>>n>>c>>k;
vector<ll>t(n);
int ans=0;
rep(i,n)cin>>t[i];
sort(t.begin(),t.end());
int i=0;
while(i<n){
ll limit=t[i]+k;
for(int j=0;j<c&&j<n;++j){
if(t[i+1]>limit){
++i;
break;
}
++i;
}
ans++;
}
cout<<ans;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main(){
ll q;
cin >> q;
vector<vector<ll>> a;
ll g = 0; // 先頭バッチのインデックス
for(ll i = 0; i < q; ++i){
int type;
cin >> type;
if(type == 1){
ll c, x;
cin >> c >> x;
a.push_back({x, c});
} else {
ll k;
cin >> k;
ll ans = 0;
while(k > 0){
ll val = a[g][0];
ll cnt = a[g][1];
if(cnt <= k){
ans += val * cnt;
k -= cnt;
++g;
} else {
ans += val * k;
a[g][1] -= k;
k = 0;
}
}
cout << ans << "\n";
}
}
return 0;
}
まだまだできる 7/6 15:28
７月６日 一周間の復習
7/7 14:11
7月７日
atcoder
考え方
先頭要素を正にするか負にするかの２通りを考える。
#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>
#include<string>
#include<set>
#include <map>
#include <queue>
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include<stack>
#define rep(i,n) for(int i=0;i<(n);++i)
using ll=long long;
ll solve(vector<ll>a,int n,int check){
ll sum=0;
ll cnt=0;
for(int i=0;i<n;++i){
sum+=a[i];
if(check*sum<=0){
cnt+=(abs(sum)+1);
sum=check;
}
check*=-1;
}
return cnt;
}
int main(){
int n;
cin>>n;
vector<ll>a(n);
rep(i,n)cin>>a[i];
ll ans1=solve(a,n,1);
ll ans2=solve(a,n,-1);
cout<<min(ans1,ans2)<<"\n";
return 0;
}
応用情報
副問い合わせ
FROM句に副問い合わせを記述することで、処理対象データの絞込ができる。
例 SELECT 社員名
FROM（SELECT＊FROM 社員 WHERE 部門コード ＝’E01’）
副問い合わせから導出される表が主問い合わせの処理対象表となる。
SELECT 社員名 FROM 社員 WHERE 部門コード＝’E01’
これは同値
副問い合わせの使用例２
比較演算子と組み合わせて使用する副問い合わせは、単一値を導出する必要がある。
SELECT 社員名
FROM 社員
WHERE 部門コード＝
（SELECT 部門コード FROM 部門 WHERE 部門名 LIKE ’営業％’）
相関副問い合わせとEXISTS
副問い合わせの中には、主問い合わせの１行ずつをもらって順次実行する副問い合わせもある。これを相関副問い合わせ
SQLによる集合演算の実現
和 SELECT ＊FROM A UNION SELECT＊FROM B
共通 SELECT ＊FROM A INTERECT SELECT＊FROM B
差 SELECT ＊FROM A EXCEPT SELECT＊FROM B
直積 SELECT ＊FROM A CROSS JOIN B
WITH句
その問い合わせの中でだけで使用できる一時的な表を定義
問い合わせの中で、同じ表の導出を複数回行わなければいけない場合に有効。
例 WITH 部門所属人数（部門コード、所属人数）
AS （SELECT 部門コード、COUNT(*) FROM 社員 GROUP BY 部門コード）一時的な表を定義
SELECT 部門コード、所属人数
FROM 部門所属人数
WHERE 所属人数＝（SELECT MAX（所属人数）FROM 部門所属人数）
上記は社員表を基に、所属人数が最も多い部門の部門コードとその所属人数を求める場合である。
CASE式
〜ならば○○ ～ならば△△というように条件に応じて元の値を別の値に変換する場合に使用します。
SELECT 社員名、CASE
WHEN 年齢＜２０ THEN ’２０未満’
WHEN 年齢＞＝２０ AND 年齢＜３０ THEN ’２０代’
ELSE ’３０以上’ END AS年代
FROM社員
表に行を挿入するには、INSERT文を使う。
表中のデータを変更するには、ＵＰＤＡＴＥ文をつかう。
表中の行を削除するには、DELETE文を使う。
関連する２つの表間に参照制約が設定されている場合、被参照表の主キーにない値を、参照表の外部キーに追加することはできません。
被参照表の行の削除・変更するとき、どのような制約（動作）とするのかは、明示的に指定できます。これを参照動作指定という。
参照動作指定
REFERENCES 被参照表（参照する列リスト）
[ON DELETE 参照動作]
[ON UPDATE 参照動作]
参照制約とは、外部キーの値が被参照表の主キーあるいは主キー以外の候補キーに存在することを保証する制約。
また指定できる参照動作には、５つの動作がある。
NO ACTION・・・削除を実行するが、これにより参照制約が満たされなくなった場合は実行失敗となり、削除処理は取り消される。
RESTRICT・・・削除を実行する際、参照制約を検査し、当該行を参照している参照表の行があれば削除を拒否する。
CASCADE・・・削除を実行し、さらに当該行を参照している参照表の行があれば、その行も削除する。
SET DEFAULT・・・被参照表の行が削除されたとき、それを参照している参照表の外部キーへの既定値を設定する。
SET NULL・・・被参照表の行が削除されたとき、それを参照している参照表の外部キーへNULLを設定する。
データ定義言語
実表の定義
CREATE TABLE 表名
列名１ データ型 [列制約],列名２ データ型[列制約」、・・・[表制約]
列制約
列に対する制約である。
一意性制約
・PRIMARY KEY
主キーに指定
・UNIQUE
値の重複を認めない
参照制約
・REFERENCES
外部キーに指定。参照される側の表の表名とその列名を指定する。ただし、列名を省略すると主キーを参照する。
検査制約
・CHECK
登録できる値の条件を指定
非ＮＵＬＬ制約
・ＮＯＴ ＮＵＬＬ
空値を認めない列にＮＯＴ ＮＵＬＬを指定
DEFAULT制約
・DEFAULT
行の挿入時、値が指定されていない列に格納する既定値を指定。
表制約
列制約が１つの列に対する制約なので、主キーや外部キーが複数列から構成される場合、これを列制約として定義できません。このような場合、表制約を用いる。
データベースのトリガ
トリガとは、表に対する更新処理をきっかけに、あらかじめCREATE TRIGGER文を用いて定義しておいた、他の表に対する更新処理を自動的に起動・実行するという機能である。
データの整合性・一貫性を自動的に保つ
トリガを利用することで、データの登録・更新・削除時に自動で関連データの整合性を保つ処理を実行できます。例えば、削除時にバックアップを自動作成したり、集計値を自動更新したりすることが可能です。
ビューとは
ディスク装置上に存在し、実際にデータが格納される表のことを実表という。それに対しビューは、実表の一部、あるいは複数の表から必要な行や列を取り出し、あたかも１つの表であるかのうように見せかけた仮想表である。
ビューの目的
・行や列を特定の条件で絞り込んだビューだけをアクセスさせることによって、基となる表のデータの一部を隠蔽して保護する手段を提供する。
・利用者が必要とするデータをビューｎまとめることによって、表操作を容易に行えるようにする。
ビューの定義はCREATE view文を用いる。
ビューの更新
ビューへの更新処理は、ビューを定義を基に、ビューが参照している表（基底表）に対する更新処理に変換されて実行される。そのため、実際に更新される表が更新可能であり、かつ、更新対象となる列や行が唯一に決定できる場合に限り、更新可能となる。
アクセス権限の付与
複数の利用者がデータベースを利用できるようにするためには、その利用者に対して、表やビューへのアクセス権限を付与する必要がある。GRANT文を用いる。
GRANT 権限リスト
ALL PRIVILEGES on 表名 to 利用者リスト
ALL PRIVILEGESを指定すると、すべての権限を付与できる。
アクセス権限の取り消し
REVOKE文を使う
埋込み方式
静的SQLと動的SQL
静的SQLは、あらかじめ決められたSQL文をプログラム中に埋込み実行する方式。データベースの表から１行を取り出すことを非カーソル処理という、
例 社員表から社員コードが１００である社員の、社員名と年齢をとりだすといった場合、「SELECT 社員名、年齢 FROM 社員 WHERE 社員コード＝’１００’を次のように埋込み実行します。
EXEC SQL SELECT 社員名、年齢 INTO :name,:age FROM 社員 WHERE 社員コード ＝’１００’
一方、動的SQLは、実行するSQL文がプログラム実行中でなければ決まらない場合、SQL文を動的に作成し実行する方式である。
ホスト変数
データベースとプログラムのインタフェースとなる変数をホスト変数という。
埋込みSQLでは、ＳＱＬ文の実行により取り出されたデータをＩＮＴＯ句で指定したホスト変数に格納しますが、ホスト変数は通常の変数としてもアクセスできるため、出力関数を用いて表示することや、入力関数を用いて値を入力し、それをSELECT文の条件として使用することもできる。
SELECT...INTO...形式では、１行のデータしか取り出せないため、検索の結果が複数行となる場合、１行ずつ取り出すことができるカーソル処理を用いる。
カーソル処理の流れ
１ カーソルの宣言
どのレコードを対象にするかSQLで指定し、カーソルとして定義します。
２ カーソルのオープン
カーソルを開き、実際にデータの取得準備をします。
３ FETCHによる1行ずつの取得と処理
カーソルから1行ずつデータを取り出し（フェッチ）、必要な処理を行います。
４ カーソルのクローズ
全ての処理が終わったらカーソルを閉じてリソースを解放します。
今日で７月なってから１週間がすぎた。時間のながれがはやいと感じるが、着実に成長できている。勉強習慣がついてきた。１日のやった勉強をおさらいとして記事で書いているが、１日つかれてなかなか夜にできない。疲れていてもなるべく夜にその日におさらいをしたいと思う。
7/8 14:28
7月8日
応用情報
トランザクションとは
データベース管理システ（DBMS)は、複数の利用者が同時にデータベースにアクセスしてもデータの矛盾を発生させない仕組みを備えている。その仕組みをトランザクション管理といい、トランザクションは、それを行うためのSQL処理の最小単位。
原子性・・・更新処理トランザクションが正常に終了した場合のみデータベースへの更新を保証し、異常終了した場合は処理が何もなかった状態にもどすこと。
一貫性・・・トランザクションの処理によってデータベース内のデータに矛盾が生じないこと。
隔離性・・・複数のトランザクションを同時に実行した場合と、順に実行した場合の処理結果が一致すること。
耐久性・・・いったん正常終了したトランザクションの結果は、そのご、障害が発生してもデータベースから消失しないこと。
複数のトランザクションを同時に実行しても、矛盾を起こすことなく処理を実行するメカニズムを同時実行制御という。
ロック
ACID特性の隔離性により、複数のトランザクションを同時に実行しても、その結果はトランザクションを直列実行した結果と同じにならなければならない。
データにロックをかけ、先にデータをアクセスしたトランザクションの処理が終了するか、あるいはロックが解除されるまで、他のトランザクションを待たせるという制御を行う。
ロックの方式には、２相ロック方式と木制約がある。
２相ロック方式は、使用するすべてのデータに対してロックをかけ、処理後ロックを解除するという方式。
木制約は、データに順番をつけ、その順番どおりにロックをっかけていくことで、デッドロックの発生がないこと、また直列可能性を保証する方式。
ロックの種類
データベース管理システムでは、トランザクションの同時実行性を高めるため、専有ロックと共有ロックの２つのロックモードを提供している。
専有ロックは、データ更新を行う場合に使用されるロックで、データに対するほかのトランザクションからのアクセスは一切禁止される。共有ロックは、通常、データの読み取りの際に使用されるロックで、参照のみを許可する。
多版同時実行制御
多版同時実行制御（MVCC)は、同時実行性を高め、かつ一貫性のあるトランザクション処理を実現する方式。
更新中のデータに対して参照要求を行った場合には、更新前の内容が返されるため、後続トランザクションは待たずに処理を行うことができる。
今日はほぼ復習だけをやった一日だった。バイトがあったから仕方がないかもだけど、何やってんだ俺。もっと成長を感じたい。コツコツやるしかない。もう眠すぎてきつい、、、
7/9 1:55
7月9日,10日,11日、12日
応用情報
障害回復
システム障害、トランザクション、媒体障害がある。
DBMSの仕組み
ディスクの入出力効率向上のため、データをメモリ上にバッファリングしておき、データの更新は、バッファ内のデータに対して行う。
そしてバッファに空きがなくなったなどの事象発生のタイミングで、バッファに保持されている内容をデータファイルへ書き出す。バッファが保持している内容とデータベースの内容が一致しない、すなわち、更新処理が実行されたもののその更新がデータベースに反映されていないデータが存在する可能性がある。
ログ
トランザクションが行った更新処理について、その更新前の値と更新後の値が必要である。そのためDBMSでは、これらの値を｛更新、トランザクションID、データ名、更新前の値、更新後の値｝といった形式で時系列に記録する。これをログという。
WALプロトコル
ログもデータと同様、メモリ上のバッファに記録され、その後、WALプロトコルに従ったログファイルへの書き出しが行われる。
WALプロトコルとは、変更データをデータベースに書き出す前に、ログファイルへの書き出しを行う。 Write Ahead Log(先にログをかけ！)の略。
システム障害からの回復
OSやDBMSのバグ、またはオペレータの誤作動によってシステムがダウンしてしまう障害である。
COMMIT済以外のトランザクションによる更新を、ログに記録された更新前の値を用いてもとの値に書き戻す。この処理をUndoという。
また、COMMIT済のトランザクションによる更新内容をデータベースへ反映させるため、更新後の値を用いてデータベースを更新します。この処理をrendという。
チェックポイントリスタート
UNDO/REND方式による障害回復には、システム起動時からのログが必要になり、また、回復処理にも多くの時間を要す。DBMSでは、データバッファとログバッファの内容を書き出すタイミングを設けている。このタイミングをチェックポイントという。チェックポイントを設けることで、それまで行われてきた更新内容がすべてデータベースに書き出される。
チェックポイントリスタート処理
・ロールバック
障害発生時点からチェックポイントまで逆方向にログファイルを見ていき、COMMIT済以外のトランザクションの更新を、更新前情報を用いてUNDOする。
・ロールフォワード
チェックポイントから正方向にログファイルを見ていき、COMMIT済のトランザクションによる更新を、更新後情報を用いてRENDする。
トランザクション障害からの回復
トランザクション障害とは、デットロックの発生によるトランザクションの強制終了、またはプログラムのバグなどによってトランザクションが異常終了する障害。原子性によりトランザクションないで行った処理をすべて取り消す必要がある。DBMSは、データバッファの内容をログバッファの更新前情報でロールバックし、すべてにデータが書き出されていた場合はログファイルの更新前情報でデータベースをロールバックする。
媒体障害からの回復
媒体障害とは、記憶媒体の故障によってデータの読み出しができなくなったり、データが消失してしまったりする障害。バックアップファイルとデーベースの回復処理を行う。バックアップファイルとは、障害発生に備えて、データベースの内容を定期的に別の媒体に保存したファイルのこと。
データ復旧の要件
RPO（目標復旧時点）・・・システム再稼働時、障害発生前のどの時点の状態に復旧させるかの目標値。
PTO（目標復旧時間）障害発生時、どのくらいの時間でいつまでに復旧させるかの目標値。
インデックス（索引）
データベースのへのアクセス効率を向上させるために使用される。
Ｂ＋木インデックス
現在、ＲＤＢＭＳのインデックスとして最も多く使われているインデックス。
節にはキー値と部分木へのポインタを、葉にはデータを格納する構造になっている。
ビットマップインデックス
インデックスを付与する列のデータ値ごとにビットマップをさくせいするほうしき。
ハッシュインデックス
ハッシュ関数をもちいてキー値とデータを直接関係づける方式。
複合インデックス
複数の列を組み合わせて１つのインデックスとしたもの。
オプティマイザ
SQL文を実行する際に、問い合わせをどのように処理するかを決めるクエリ最適化の機能。
データベースチューニング
データベースシステムにおいて、アクセス性能の確保は重要です。
データベースシステムの運用管理はデータベース管理者（DBA)が行う。
分散データベース
分散データベースシステムの機能的な目的は、複数のサイトに分散されたデータやシステムを論理的に統合して1つのデータベースであるかのように利用者に見せること。
6つの透過性
分散データベースでは、データの位置を意識しないで利用できる位置に対する透過性と、データの移動先を意識しないで利用できる位置に対する透過性、そして表が複数のサイトに分割されてもそれを意識しないで利用できる分割に対する透過性の実現が不可欠。
行単位で分割する水平分割と列単位に分割する垂直分割がある。
透過性の実現
透過性を実現するには、各サイトのデータベース管理システムがもつデータディクショナリ/ディレクトリ（DD/D）に加えて、分散データベース全体を管理すグローバルなDD/Dが必要、
DD/D・・・表の格納場所や表の構造などの情報を持つデータ辞書。
異なるサイト間での表結合
分散データベースにおいて異なるサイト間で表結合を行う場合、基本的にはどちらか一方の表を他のサイトに送る必要がある。表全体を送るとなると転送コストがかかる。
そこで、結合に必要な属性のみを相手サイトに送り、結合に成功したものだけを元のサイトに戻して、最終的な結合を行う方式がある。この方式をセミジョイン法という。
セミジョイン法にハッシュ結合を組み合わせた方式に、ハッシュセミジョイン法がある。
分散データベースの更新同期
分散データベースでは、データを複数のサイトに重複して存在させたり、データを複数のサイトに分割・分散させる場合がある。一方のサイトが更新されても、他のサイトが更新されなければ、データの整合性を維持できないため同期をとる必要がある。
レプリケーション
非同期更新を実現するメカニズムの１つ。マスタデータベースと同じ内容の複製（レプリカ）を他のサイトに作成しておき、決められた時間間隔でマスターデータベースの内容を他のサイトに複写する機能です。
２相コミットメント制御
分散データベースシステムにおけるトランザクションは、複数のサブトランザクションに分割され、複数のサイトで実行される。
２相コミットメント制御では、更新が可能かどうかを確認する第１フェーズと更新を確定する第２フェーズに処理を分け、各サイトのトランザクションをコミットもロールバックも可能な状態（セキュア状態）にした後、全サイトがコミットできる場合だけトランザクションをコミットするという方法でトランザクションの原子性、一貫性を保証する。
データベース応用
企業の様々な活動を介して得られた大量のデータを整理・統合して蓄積しておき、意思決定支援などに利用するデータベース、あるいはその管理システムをデータウェアハウスという。
データウェアハウスは、基幹系データベースからのデータ抽出、変換、データウェアハウスへのロード（書き出し）という一連の処理を得て構築される。この一連の処理をETLという。
データマート・・・データウェアハウスに格納されたデータの一部を、特定の用途や部門用に切り出したデータベース。
多次元データを、様々な視点から対話的に分析する処理形態、あるいはその技術をＯＬＡＰ（オンライン分析処理）という。
Online Analytical Processing の略でOLAPと呼ばれています。
日本語での意味がオンライン分析処理や多次元分析とも言われています。
多次元というのが、売上データだったら商品別や時系列、エリア別など様々ん分析の軸で傾向を見ることを指します。
要するにOLAPとは蓄積したデータを複数の軸で分析を行ってリアルタイムにレスポンスを返す仕組みです。
多次元データベースは、データを多次元そのままの形で管理する専用のデータベースと、関係データベースを利用してスタースキーマ構造で管理するデータベースに大別することができる。それぞれに対応したＯＬＡＰをＭＰＬＡＰ、ＲＯＬＡＰとう
スタースキーマとは、多次元構造に適合したリレーショナルスキーマである。
perplexityにきいてみた
リレーショナルとは
リレーショナルデータベース（RDB）は、データを行と列からなる表（テーブル）形式で管理し、複数のテーブル間の関係性（リレーション）をキーによって関連付けて扱うデータベースのことです。
各テーブルは「エンティティ」（例：顧客、注文など）を表し、主キーや外部キーといった識別子を使って、他のテーブルと論理的に結びつけます。
例えば、「顧客」テーブルと「注文」テーブルを顧客IDで関連付けることで、顧客ごとの注文履歴を簡単に取得可能となります。
IT以外でも「リレーショナル」は「関係性がある」「関連する」といった意味で使われますが、データベース分野では特に「表同士の関係性」を強調する用語で
スキーマとは
スキーマとは、主にデータベース分野で使われる用語で、データベースの構造や設計図を表すものです。スキーマは、どのようなデータが、どのような形式・構造で、どのような関係性で保存されるかを定義します
リレーショナルスキーマとは
リレーショナルスキーマとは、リレーショナルデータベース（RDB）において、データをどのような表（テーブル）構造で管理し、各テーブルの列（フィールド）、データ型、主キー・外部キーなどの制約、テーブル同士の関係性などを体系的に定義した設計図のことです
データマイニング
大量のデータから統計的、数学的手法を用いて、データの法則性や因果関係を見つけ出す手法です。
代表的なデータマイニング手法
マーケットバスケット分析・・・ＰＯＳデータやeコマースの取引ログなどを分析して、顧客が一緒に購入している商品の組み合わせを発見するデータ分析手法。1人の顧客による１回の購入データをマーケットバスケットデータという。
決定木分析・・・ツリーによってデータを分析する手法。
ニューラルネットワーク・・・人間の脳や神経系の仕組みをモデル化した数学モデルで、データマイニングにおいて数値予測に使われる。
クラスタ分析・・・異質なものが混ざり合った調査対象の中から、互いに似たものを集めた集団。
データマイニングでは、発生したデータをデータベースに蓄積した後、集計・分析するためリアルタイム性に欠ける。そこで、近年注目されているのがＣＥＰ（複合イベント処理）です。
刻々と発生する膨大なデータをリアルタイムで分析し処理する技術。
NOSQL
ビッグデータの中心的な技術基盤であり、データへのアクセス方法をSQLに限定しないデータベースの総称。
NOSQLデータベース
キーバリューDB・・・１つのデータを１つのキーに対応付けて管理する。
カラム指向DB・・・キーバリューDBにカラムの概念を持たせたもの。
ドキュメント指向DB・・・キーバリューDBの基本的な考え方を拡張したもの。データをドキュメント単位で管理する。
グラフ指向DB・・・グラフ理論に基づき、ノードとノード間のエッジ、そしてノードとエッジにおける属性により全体を構造化し管理する。
BASE特性
NOSQLにおいて、ビックデータなど膨大なデータを高速に処理する必要がある。そのため、一時的なデータの不整合があってもそれを許容することで整合性保証のための処理負担を軽減し、最終的に一貫性が保たれていればよいという考え方を採用しています。これを結果整合性といい、結果整合性を保証するのがBASE特性である。
データレイク
ビックデータの貯蔵場所であり。あらゆるデータを必要に応じて加工できるように、発生した元のままの形式や構造で格納できるリポジトリ。
ブロックチェーン
ブロックチェーンは、ネットワーク上のコンピュータにデータを分散保持させる分散型台帳技術。
分散型データベースシステムにおいてデータストアに望まれる３つの特性 一貫性、可用性、分断耐性のうち、同時に満たされるのは２つまであるという理論をCAP定理という。
データストアは、コンピュータシステムに情報を格納して保護するデジタルリポジトリです。
通信プロトコルの標準化
OSI基本参照モデルでは、それぞれの階層のことをN層と呼び、N層に存在する通信機器などの実体をエンティティと呼ぶ。
TCP/IPプロトコルスイート
一般には、同じ団体が作ったプロトコルはセットで使われることが多く、このセットをプロトコルスイートという。
TCP/IPの通信
データをパケットと呼ばれる単位に区切り、各パケットにヘッダをつけて送信する。
MACアドレス
データリンク層で使用され、同じネットワークに接続された隣接ノード間の通信で相手を識別するために使います。 MACアドレスは、聞きが固有にもつ番号なので、必ず一意に定まるようにIEEEが管理している。
Ipアドレス
ネットワーク層のプロトコルIPで利用されるノードを特定するためのアドレス。
ポート番号
トランスポート層においてノード内のアプリケーションを識別するための番号である。
FTPやHTTPなどよく利用されるアプリケーションのポート番号をウェルノウンポートという。
物理層の接続
リピータは、ネットワーク上を流れる電流の増幅装置、あるいは整流装置です。ケーブルが長いと電流が減衰したり、波形が乱れてデータが読み取れなくなる。これを防ぐため一定の距離ごとにリピータを設置して、電流の増幅と整流を行う必要がある。リピータは１対１でつなぐものですが、現在では複数のノードを接続できるマルチポートリピータ（ハブ）が使われるのが一般的である。
データリンク層の接続
ブリッジはデータリンク層に位置し、宛先MACアドレスによって通信を制御する装置です。
通信のたびに、あるMACアドレスを持つノードがどのポートに接続されているか学習し、MACアドレステーブルに記録する。これにより、次回に通信があったとき、必要なポートにだけ通信を中継できるので、無駄なトラフィックを発生させずに、ネットワーク利用率を低下できる。
スイッチングハブはレイヤ２スイッチとも呼ばれる装置で、データリンク層に位置し、ブリッジと同じ働きをする。
ブロードキャストストーム
ブリッジやスイッチングハブなどのLANスイッチは、ブロードキャストフレームを受信ポート以外のすべてのポートに転送する。そのため、これらの機器をループ状に接続し冗長化させた場合、ブロードキャストフレームは永遠に回り続けながら増殖し、最終的にはネットワークダウンを招いてしまう。この現象をブロードキャストストームという。これを防ぐプロトコルにSTP（スパニングツリープロトコル）がある。
ルータ
ネットワーク層に位置し、宛先IPアドレスを見て、パケットの送り先をきめ、通信を制御す装置です。ルータで分けられたネットワークの単位をブロードキャストドメインという。
度のルータへ送れば、宛先ネットワークへの通信が速く行えるかを判断することを経路制御（ルーティング）という。
経路表の作成方法には、手作業で作成するスタティックルーティングと、ルーティングプロトコルを利用することによってルータ同士が経路に関する情報の交換を行い自律的に経路表をさくせいするダイナミックルーティングがある。
また、ルーティングプロトコルには、自立システム内をルーティングするIGPと、自立システム同士のルーティングを行う（EGP）がある。
自立システムとは同じ方針に則って管理を行うことができる範囲。
代表的なダイナミックルーティングプロトコル
・RIP・・・経路情報を一定時間間隔で交換しあい、宛先ネットワークに至るまでに経由するルータの数（ホップ数）が最小になる経路を選択する。最大ホップ数は１５でありそれ以上は採用されない。
・OSPF・・・コストを経路選択の要素に取り入れ、最もコストの小さい経路を選択する。
ルータの冗長構成
ＶＲＲＰ（virtual router redundancy（冗長性） protocol）がある。これは、同一のLANに接続された複数のルータを、仮想的に１台のルータとして見えるようにして冗長構成を実現するプロトコル。
レイヤ３スイッチ
ルータと同じネットワーク層に位置する通信機器です。特徴としては、ルータがソフトウェアを利用して転送処理を行うのに対して、れいや３スイッチでは専用ハードウェアによって転送処理を行っている点です。高速に処理が行えるため、大容量のファイルを扱うファイルサーバへのアクセスなどに適している。
ルータは、フィルタリングなどの多様機能性に重点を置いたもの。それに対し、レイヤ３スイッチは通信の高速性に重点を置いている。
トランスポート層以上の層の接続
ゲートウェイは、トランスポート層からアプリケーション層についてネットワーク接続を行う装置です。第４層のトランスポート層以上が異なるLANシステム相互間のプロトコル変換やデータ形式の変換を行う。
ゲートウェイは、アプリケーションプロトコルの内容を解釈できるため、アプリケーションヘッダに不正な情報が混入していないかなどを検出できる。プロキシサーバやファイアウォールもゲートウェイの仲間
Ｌ４スイッチは、トランスポート層で稼働する装置で、定義としてはゲートウェイに属しますが、機能的にはレイヤ２スイッチ、レイヤ３スイッチの延長上にある装置ともいえる。ＴＣＰポート番号やＵＤＰポート番号も経路制御判断の情報として扱うことができる。
Ｌ４スイッチは、アプリケーション層までの情報を使って通信制御を行う装置です。
ネットワーク仮想化
ＳＤＮは、ソフトウェアにより柔軟なネットワークを作り上げるという考え方で、これを実現する技術の１つがＯＰＥＮＦＬＯＷである。
スイッチの特徴的な機能にVLAN機能がある。物理的な接続形態に依存せずに、ノード任意に論理的なグループに分けるための仕組みのこと。
例えば、営業部と開発部が同じブロードキャストドメインに属しているため互いの通信をキャプチャできます。営業部と開発部でネットワークを分離することで解決できますが、L3SWをうまく配置すれば作業がもっと簡単になる。
atcoder
考え方
どちらの操作も合計値を２を増やすため、３つの整数の和の奇遇は変わらな
い。
#include <iostream>
#include <algorithm>
using namespace std;
int min_operations(int A, int B, int C) {
int M = max({A, B, C});
int sum = A + B + C;
int target = (3 * M % 2 == sum % 2) ? M : M + 1;
int diff = (target - A) + (target - B) + (target - C);
return diff / 2;
}
int main() {
int A, B, C;
cin >> A >> B >> C;
cout << min_operations(A, B, C) << endl;
return 0;
}
考え方
アリスとボリスの差が偶数ならボリスの勝ち
それいがいならアリスの勝ち
#include <iostream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define ll long long
int main(){
int n,a,b;
cin>>n>>a>>b;
if((b-a)%2==1){
cout<<"Borys";
return 0;
}
cout<<"Alice";
return 0;
}
7/14 22:00
４日間はたくさん遊んだ あしたから切り替える。
7月前半終了