忍者ブログ
2ヶ月弱で情報処理試験・ソフトウェア開発技術者に合格します。
★RSS 1.0  ★RSS 2.0
Posted at 2026.11.23,Mon
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

Posted at 2007.10.10,Wed
レジュメをまとめました。

ええと、前回のレジュメから丁度一ヶ月。
長かった分、かなりの量になってしまいました。

理解した単語から消していくのがミソです。

補数1の補数はビット反転。2の補数は1の補数+1。
バブルソートO(n^2)・O(n^2)
選択ソートO(n^2)・O(n^2)
挿入ソートO(n)・O(n^2)
クイックソートO(nlogn)・O(n^2)
マージソートO(nlogn)・O(nlogn)
ヒープソートO(nlogn)・O(nlogn)
パイプライン制御
時間123456789
処理A■■■■■    
処理B ■■■■■   
処理C  ■■■■■  
処理D   ■■■■■ 
処理E    ■■■■■
MIPSMillion Instructions Per Second
メモリインタリーブメモリを分割し連続アドレスへのアクセスを高速化
DMACPUと独立して、メモリとIO間でデータ通信を行う事
FIFOFirst In First Out
LIFOLast In First Out
LRULeast Recently Used
LFULeast Frequency Used
スラッシングスワップが頻繁におこる事
ラウンドロビン優先度を設定せずに、順番に廻す
SJFShortest Job Firs ( 処理時間の長さに従う )
垂直分散階層的に処理を分散。3層クラサバとか。
水平分散分散したサーバが対等の位置に。
NASNetwork Attached Storage
SANStorage Area Network
EAI企業内のシステムを連携して再構築
UDDIWebサービス用検索エンジン
ドライバ呼び出し元のダミー
スタブ呼び出す先のダミー
インバスケット作業(書類)を山積みにするトレーニング
サービスサポートITIL での日常的な指針
サービスデリバリITIL での中・長期的な指針
RARPMACアドレス→IPアドレス
パリティ加算で1ビット検出。訂正は無理
CRC複雑な数式で1ビット検出。訂正は無理
ハミング符号XORで2ビット検出。1ビット訂正
標本化定理復元できる周波数は半分
ATM固定長、非同期転送
パケット交換方式可変長、蓄積するため遅延が大きい
ロールバックデータを再現、論理障害での使用が多い
ロールフォワードデータと処理を再現、物理障害での使用が多い
ストアドプロシージャSQL文が実行形式で保存されたライブラリ
Webビーコン情報収集用の画像
SECEWeb上のクレカ決済の仕様
インターロック操作ミスを防ぐ仕組み
インボリューション暗号化用のテクニック
耐タンパ性物理的な解析の困難性
共通フレームSLCP-JCF98・作業の内容と項目を分類したもの
JIS X 0160ISO/IEC 12207 プロセス・アクティビティ・タスク
CORBA分散オブジェクト技術 OMG・ORB
浮動小数(-1)S × 2E-127 × (1 + F)
逆ポーランド記法X=(A−B)×C を XAB−C×= と表現する
SRAM大きい・高い・速い・バイポーラ
DRAM小さい・安い・遅い・CMOS
CISC1命令が複雑、マイクロプログラム
RISC命令1クロック、ワイヤードロジック
MIPSMillion Instructions Per Second
FLOPSFloating point Operations Per Second
ライトスルー(キャッシュメモリ) 書いたら終わり
ライトバック(キャッシュメモリ) 書いた後、更に書き戻しが必要
フルアソシアティブ任意の場所に格納
ダイレクトマッピング固定位置に格納
セットアソシアティブ固定ブロックの任意の場所に格納
タスク:待ち状態自発的な待ち状態
セマフォP→V の順で処理
フールプルーフFoolproof ( 馬鹿よけ )
フェールセーフFail Safe
フェールソフトFail Soft
フォールトアボイダンスFault Avoidance ( 回避 )
フォールトトレランスFault Tolerance ( 許容 )
Dhrystone・SPECint整数のベンチマーク
Wheatstone・SPECfp浮動小数のベンチマーク
平均待ち時間(ρ ÷ (1 − ρ)) × 処理時間
MTBF平均故障間隔
MTTR平均修理時間
故障率1 ÷ MTBF
稼働率MTBF ÷ ( MTBF + MTTR )
ファンクションポイント機能の複雑さから見積もる ( ×+× )
COCOMOコード行数から工数を見積もる
CASEツール開発で使用する色々なツール
リポジトリ成果物の格納庫。用語統一が可能。
ウォーターフォール普通の開発
プロトタイプ初期段階でプロトタイプを作る
スパイラル全行程をグルグル廻し続ける
成長モデル核となる部分を作り、少しずつ膨らませる
RAD短期集中、少人数精鋭
ラウンドトリップトライ&エラー
同値分割代表値を使用する
限界値分析境界値を使用する
原因結果グラフ複雑な要因に対する結果のグラフ
デシジョンテーブル複雑な要因に対する結果の表
バグ埋込法総バグ:発見済バグ=埋込バグ:発見済埋込バグ
ウォークスルー主催者は開発者。非公式な感じ。
インスペクション主催者は管理者。公式な感じ。
PERT・WBS図参照
コネクション型通信相手を確認して通信。TCP。
コネクションレス型通信相手を無視して通信。UDP。
CSMA/CD衝突検知後再送、長距離は無理
ANSI/SPARC 3層スキーマ内部・概念・外部
E-R図DBの設計図
候補キー主キー+代替キー
外部キー外部の主キーを参照
DBの第1正規化配列・繰り返しを無くすこと
DBの第2正規化単独キーと複合キーの表に分ける
DBの第3正規化キー以外の部分で、テーブルになる部分を抜き出す
DBの第4正規化キーに対し、関連性の薄い値を分割
ACID - AAtomicity / All or Nothing
ACID - CConsistency / データの矛盾が発生しないこと
ACID - IIsolation / 同時に実行しても順番に実行しても同じ結果
ACID - DDurability / 成功した結果は消失しない
レプリケーション複製を用意
2相コミット要求・コミット or ロールバックの2相
SAMLシングルサインオンで使用する認証方式
IDSIntrusion Detection System




記憶する必要の無い単語は、ぼんやりと目になじませて、拒否反応が出ないようしておきましょう。
PR
Posted at 2007.10.09,Tue
ええと、ヒープソートです。

実は、一度書いたのですが、ヒープソートのメリットが全然活かせてなかったのでボツにしました。

ちょっと勘違い。

ヒープの構築(2分木の作成)と要素の取り出しを繰り返せばヒープソートだと思ってたのですが、毎回 木全体を作り直してしまうと遅いですよね。

というわけで、やり直しです。

  001: var count = 10;
002: var nums = new Array(count);
003:
004: // 適当な数値で初期化 ( 重複OK )
005: if (var c = 0; c < count; c++) {
006: nums[c] = Math.floor((Math.random() * 100) % 100);
007: }
008:
009: // ヒープ構造の初期化
010: for (var c = Math.floor(count / 2); c >= 0; c--) {
011: heap(c, count);
012: }
013:
014: // 入れ替え&ソート
015: for (var c = count - 1; c >= 0; c--) {
016: var x = nums[c];
017: nums[c] = nums[0];
018: nums[0] = x;
019: heap(0, c);
020: }
021:
022: // 特定のノード以下の木構造を再構築
023: function heap(node, cnt) {
024: var p = (node + 1) * 2 - 1;
025: if (p > cnt) return;
026:
027: if((nums[node] < nums[p]) &&
028: ((p == (cnt - 1)) || (nums[p] > nums[p + 1]))) {
029: // 左側の葉と入れ替え
030: var x = nums[p];
031: nums[p] = nums[node];
032: nums[node] = x;
033: heap(p);
034: }
035: else if (((p + 1) < cnt) && (nums[node] < nums[p + 1])) {
036: // 右側の葉と入れ替え
037: var x = nums[p + 1];
038: nums[p + 1] = nums[node];
039: nums[node] = x;
040: heap(p + 1);
041: }
042: }


最大値となる根を抜き出した後は、ヒープの末端の葉を正しい位置に入れてあげればOKってことですね。ヒープを全て作り直すのとは、速度は大きく違いますね。

0
1
2
3
4
5


0


1
2


3
4
5


ソートを試してみる
Posted at 2007.10.05,Fri
今回は、クイックソートです。
よく利用しますが、あまり組むことは少ないですよね。

  001: var count = 10;
002: var nums = new Array(count);
003:
004: // 適当な数値で初期化 ( 重複OK )
005: if (var c = 0; c < count; c++) {
006: nums[c] = Math.floor((Math.random() * 100) % 100);
007: }
008: qsort(0, count - 1);
009:
010: function qsort(r1, r2)
011: {
012: // 終了条件:ソート対象の要素が1つ
013: if (r1 >= r2) return;
014:
015: // 軸を適当に選ぶ(ここでは先頭)
016: var pivot = nums[r1];
017: var pos = r1;
018:
019: for (var c = r1 + 1; c <= r2; c++) {
020: // 軸を基準に分割しながら、軸が有るべき位置を見つける
021: if (nums[c] < pivot) {
022: pos++;
023: var x = nums[c];
024: nums[c] = nums[pos];
025: nums[pos] = x;
026: }
027: }
028:
029: var x = nums[r1];
030: nums[r1] = nums[pos];
031: nums[pos] = x;
032:
033: qsort(r1, pos - 1);
034: qsort(pos + 1, r2);
035: }


0
1
2
3
4
5


 ソートを試してみる
Posted at 2007.10.05,Fri
さてさて、挿入ソートです。

  001: var count = 10;
002: var nums = new Array(count);
003:
004: // 適当な数値で初期化 ( 重複OK )
005: if (var c = 0; c < count; c++) {
006: nums[c] = Math.floor((Math.random() * 100) % 100);
007: }
008:
009: for (var c = 0; c < count; c++) {
010: for (var n = 0; n < c; n++) {
011: if (nums[c] < nums[n]) {
012: // 挿入する。
013: var x = nums[c];
014: nums[c] = nums[n];
015: nums[n] = x;
016: }
017: }
018: }

言語的に 挿入 というイメージがつかみにくいかもしれません。

もし、JavaScript の Array クラスがもう少し高機能であれば、もう少し違った書き方が出来ると思いますが、C言語でも同じ感じなので仕方ないですね。

0
1
2
3
4
5


 ソートを試してみる
Posted at 2007.10.05,Fri
さてさて、選択ソートです。

  001: var count = 10;
002: var nums = new Array(count);
003:
004: // 適当な数値で初期化 ( 重複OK )
005: if (var c = 0; c < count; c++) {
006: nums[c] = Math.floor((Math.random() * 100) % 100);
007: }
008:
009: for (var c = 0; c < count; c++) {
010: // 最小値を選択する
011: var min = c;
012: for (var n = c + 1; n < count; n++) {
013: if (nums[min] > nums[n]) {
014: min = n;
015: }
016: }
017: var x = nums[c];
018: nums[c] = nums[min];
019: nums[min] = x;
020: }


最小値を選択ってところがミソですね。
しかし、Cをはじめとして、新しい言語にも swap が存在しないのはなんで?

0
1
2
3
4
5


 ソートを試してみる
Welcome ...

 
Ad.
Profile
名前:たびと。
職業:元腐れプログラマ

Template by mavericyard*
忍者ブログ [PR]