cs

暗記

lirlia 2022年12月21日カード66 いいね0

CSにおけるデータ型の種類を答えよ

ブーリアン型
整数型
浮動小数点型
文字型
文字列型
整数型が扱える値の範囲を答えよ。またその理由を答えよ

一般的に、整数型は 4 バイト、つまり 32 ビットの長さがあります。つまり、32 ビットは 4,294,967,296（= 232）通りの 2 進数の表現が可能です。そのため、正の数だけであれば、0 ～ 4,294,967,295 の数値を扱えます。しかし、通常整数は負の数も扱いますので、正負のどちらかを識別するために 1 ビット使用し、範囲は、-2,147,483,648 ～ 2,147,483,647 になります。
符号付き整数、符号なし整数の違い

符号なしの場合は負の値を表現しない。そのため符号付き整数はより大きい値を扱える
文字コードとは何か？

0と1しか扱えないコンピュータでも問題なく文字を扱うための仕組み。
数字に対して文字をマッピングした対応表。ASCII・Unicode
符号位置(コードポイント)とは何か？

U+0000 ～ U+10FFFF のような 16 進数による番号によって表された1 つの文字を示す番号のこと
符号化文字集合とは

Unicode
文字符号化方式とは

符号位置を二進数（十六進数）にしたもの。UTF-8 など
プログラムで文字を扱う時、Hello といれると Unicode によってコードポイントに変換され、UTF-8 によって1~4byte の可変長のバイトになって扱われる。戻す時は、拾ってきた文字を UTF-8 ルールで解釈して Unicode で対応表でコードポイントに戻して出力する
文字型(char) と文字列型(str) の違いは？

プログラミング言語によっては、d のような文字と、hello のような文字列は異なるデータ型と認識される点に注意が必要です。つまり、1 文字のみの文字型を char 型、1 文字以上の文字列型を str 型とし、区別されます。

文字列は特定の順序で並ぶ配列およびリストデータ構造と定義されます。
https://recursionist.io/dashboard/course/1/lesson/12
3.4E+38 の E は何を表してる？

指数表記、3.4 x 10^38 のこと
浮動小数点とは、例を出せ

340282 × 1033 = 34028.2 × 1034 = 3.40282 × 1038 = 0.340282 × 1039

これらの数値はすべて同じ値を示します。小数点を指数表記によって動かすことができるので浮動小数点とよばれます。
https://recursionist.io/dashboard/course/1/lesson/15
仮数、指数、基数とは

3.4 × 1038 のうち 3.4 を仮数、38 を指数、10 を基数と呼びます。つまり、（仮数）× （基数）（指数）となります。
https://recursionist.io/dashboard/course/1/lesson/15
指数表示の正規化とは

3.40282 × 1038 のように一番左の数値が整数 1 桁になるように表記します。このことを「正規化」と呼びます。
https://recursionist.io/dashboard/course/1/lesson/15
3.4 × 10^38 のそれぞれの用語を答えよ

3.4 を仮数、38 を指数、10 を基数
データ型がないことをなんというか

void
https://recursionist.io/dashboard/course/1/lesson/19
0.1 + 0.2
# 0.30000000000000004 を出力される理由は？

0.1 や 0.2 を二進数で表現すると循環小数になってしまう。そのため適度なところで丸めた場合、0.1に限りなく近い数と0.2に限りなく近い数の合計になってしまうため。

```
// 0.1 が 2 進数へと変換され、2 進数　が　10 進数へ変換され、コンソールに表示されます
// 2 進数へ変換した際に近似されるため、10 進数に戻した時には正確には 0.1000000000000000055511151231257827021181583404541015625 になります
// JavaScript は値を丸めて表示します

console.log(0.1);
```
オペランドとオペレータとは
メモリアドレスとは？

メモリのセルの位置のこと。メモリアドレスは十六進数で表現されることが多い
セルとは

メモリの最小単位。１セル１バイトを表す
xxxx_xxxx の命名をなんという

snake_case
xxxxXxxxXxxx の命名をなんという

lowerCamelCase
短絡評価（short-circuit evaluation）とは

必ずしも全ての式が評価されないことを指します。例えば、論理積 (&&) 演算子の第一引数を評価した結果が false であれば、式全体は必ず false になります。それは false && false も false && true も false と評価されるためです。また、論理和 (||) 演算子の第一引数が true であれば、式全体は必ず true になります。それは true || true も true || false も true と評価されるためです。
xxxx-xxxx の命名をなんという

kebab-case
機械語とは

CPUが直接理解できる0と1のみで構成された言語のこと
XxxxxXxxxXxxx の命名をなんという

アッパーキャメルケース(パスカルケース）
スネークケースとは

snake_case
述語（predicate）とは？

ブーリアン値を返す関数や式のこと
コンパイラとは？

私たちの言語からコンピュータが理解できる機械語へ翻訳するプログラムのこと。CPUアーキテクチャに応じて解釈できる機械語が異なるのでコンパイルの結果を変換してくれる。
ベースケース（base case）とは

再帰関数において、関数に戻り値を保証し、ループを終了させるステートメント
コールスタック（call stack）とは

関数はプログラム中に呼び出されると、オペレーティングシステムによって関数自身に関する情報をコールスタック（call stack）と呼ばれる領域に一時的に格納されます。
深さ優先探索（depth-first search, DFS）

関数の呼び出しが演算子よりも先に実行されることから、フィボナッチ数列の再帰関数では木の末端側から処理が徐々に実行されています。このような処理をしていくアルゴリズムを深さ優先探索（depth-first search, DFS）といいます。
幅優先探索（breadth first search）

深さ優先探索とよく引き合いに出されるアルゴリズムとして幅優先探索（breadth first search）というものがあります。幅優先探索では、深さ優先探索とは反対に、ツリーの根元側、すなわち頂点に近い順に処理を実行されます。
末尾再帰（tail recursion）

再帰の中でも、以下のように「return 再帰関数」の形、つまり他の全ての処理の最後（末尾）で再帰処理が行われるものを末尾再帰といいます。

def f():
return f()

「return c + 再帰関数」のような形をしているものは、末尾再帰ではありません。それは関数呼び出しの後に、「+」演算子が実行され、再帰処理が関数の最後の処理になっていないからです。
末尾呼び出し最適化が適用されるとうれしいことは？

末尾呼び出し最適化が適用されると、スタックの累積がなくなることから、空間計算量が圧倒的に削減できるというメリットがあります。末尾呼び出し最適化では、関数は自身を pop し、次の関数を同じフレーム内に push し、全ての計算を完結することができるため、空間計算量は O(1) になります。

https://recursionist.io/dashboard/course/2/lesson/144

ーーー
末尾呼び出し最適化では、再帰関数が呼び出された時、新しいスタックフレーム（スタックデータごとのかたまり）を確保するのではなく、既存のスタックフレームの値が更新されます。
ヘッド再帰

「戻り値の評価が完了する前に、次の関数を呼び出す再帰」のこと。「return c + 再帰関数」のような形をしているもの
副作用

「どこかにある何かを、知らず知らずのうちに変容させてしまっている」ことを意味します。
ヒープメモリ割り当て

スタックメモリが自動的に割り当てられるメモリ領域であるのに対し、ヒープメモリはユーザーがいつでも割り当てることのできるメモリ領域です。

ヒープ割り当ては動的に実行されるので、動的メモリ割り当て（dynamic memory allocation）とも呼ばれます。メモリを割り当てるためには new や malloc などのキーワードや関数が使用され、そのサイズもユーザーによって決められます（malloc は memory allocation の略です）

新しいメモリを割り当てる際、オペレーティングシステムはメモリ内の空き領域を探し、そのメモリアドレスを取得します。ヒープメモリはスタックメモリとは完全に分離されており、関数がスタックからポップされてもメモリアドレスとその内容が空になることはありません。メモリアドレスが参照可能な限り、そのメモリ領域が保有するデータを取得することができます。
スタックメモリ割り当て（stack memory allocation）

スタックメモリ割り当て（stack memory allocation）は、コールスタック内に新しいスタックが作成されるたびに実行されます。コールスタックとはサブルーチン（関数）に関する情報を一時的に保管する場所でした（詳しくは、中級 > 再帰 > コールスタックのページを参照しましょう）

関数が呼び出されると、新しいスコープがスタックにプッシュされ、変数はそのデータをこの空間に格納します。呼び出しスタックがこのスコープをポップすると、全ての変数とそのデータは消去されます。これは変数が格納されたメモリ上のスタック領域が空になってアクセスできなくなり、スコープに紐付けられた名前も消滅することを意味します。
糖衣構文（syntactic sugar）

if 文では、ステートメントをグループ化してブロックのように扱っています。もし述語が true を返した場合、そのブロックのステートメントのみが実行され、他のグループのステートメントは全てスキップされます。

一部の言語では switch 文と呼ばれる他の方法で同じような処理を行うことができます。このように同じ機能を持つ他のキーワードやツールのことを糖衣構文（syntactic sugar）といいます。
連結リスト（linked list）

各オブジェクトが次のオブジェクトを参照するようなデータ構造を連結リスト（linked list）と呼びます
ステートレスオブジェクトと不変オブジェクトの違い

不変オブジェクトは初期状態を持っていますが、その状態は作成後には全く変更できません。一方、ステートレスオブジェクトはそもそも全く状態を持ちません。

ステートレスオブジェクトの中にあるものは、最初から全て定義されているため、プログラムを通して値を変更することができません。

https://recursionist.io/dashboard/course/2/lesson/223
動的配列の先頭に追加する時の計算量は？
動的配列の途中に追加する時の計算量は？
動的配列の最後に追加する時の計算量は？

O(n)
O(n)
O(1)

動的配列の先頭に要素を挿入するには、元々あった最初の値を次のスロットにコピーし、その次のスロットの値をその次のスロットにコピーすることを繰り返す操作が必要になります。

n 個の要素がある場合、n 個の要素を移動させる必要があるため、結果として O(n) の計算コストが必要になります。動的配列の一番最初の要素にいきなり値を追加できないのは、すでにセルの中に値が存在していており、値を上書きしてしまうからです。

===

n 個の要素の動的配列の真ん中へ要素の挿入を行う場合、先ほど学習した先頭に要素を挿入する場合と同様の処理を配列の真ん中まで行えば良いことになります。したがって、0.5n 個の要素を移動させる必要があり、結果として O(n) の計算コストが必要になります。

===

配列の末端に要素を挿入する処理は、先述した通り、配列の論理サイズと収容可能サイズとの兼ね合いで妥当な処理が実行されます。配列の容量が最大に達している、つまり「論理サイズ = 収容可能サイズ」の場合、新しい配列を作成し、もとの配列に入っていた n 個のデータと新しく追加したデータを合わせた計 n+1 個の要素を、その新しい配列にコピーします。したがって、O(n) の計算コストが必要になります。

しかし、ほとんどのケースでは、配列に余裕があるので、最後のスロットにデータを挿入するだけで済みます。この場合は、計算コストが O(1) となります
タビュレーション

木構造の結果を下から上にキャッシュするタビュレーションについて見てみましょう。タビュレーションは、ベースケースから始まり、最終的な答えに向かって解きます。動的計画法では一般的なやり方になります。

ーーー

// 木構造の結果を下から上にキャッシュする方法をタビュレーションと呼びます
function tabulationFib(n){
// これはキャッシュであり、計算済みのフィボナッチ数をすべて保存します
// 全てを 0 に設定します
let cache = [];
for(let i = 0; i <= n; i++) {
cache.push(-1);
}

// fib0 は 0、fib1 は 1 であり、他のすべての数は fib(n) = fib(n-1) + fib(n-2) を使って求めることができます
cache[0] = 0;
cache[1] = 1;

// 反復を使って全ての数を求めます
for (let i = 2; i < n+1; i++){
cache[i] = cache[i-1] + cache[i-2];
}

// n 番目のフィボナッチを返します
return cache[n];
}

console.log(tabulationFib(50));
メモ化とは

再帰の木構造の結果を上から下にキャッシュするメモ化

メモ化ではキャッシュに値が保存されているか、つまりすでに計算が行われているかを基準に処理が行われます。すでに計算が行われている場合、キャッシュされた値を返し、そうでなければ再帰的な計算が通常通り行われます。計算をスキップできることから通常の再帰計算より良いパフォーマンスを得られることができます。

ーーー
// メモ化は、木構造の上から下へと続くアルゴリズムでのキャッシングです
// n から始まり、n-1、n-2、n-3 と下に向かって計算していきます
function memoizationFib(totalFibNumbers){
// キャッシュ内にすでに計算したフィボナッチ数をすべて保存します
let cache = [];
for(let i = 0; i <= totalFibNumbers; i++) {
cache.push(null);
}

// ローカル関数を用いてキャッシュを更新していきます
function innerMemoizationFib(n){

// キャッシュに値が保存されていない時は再帰処理
if (cache[n] == null){
if (n == 0){
cache[n] = 0;
} else if (n == 1){
cache[n] = 1;
} else {
cache[n] = innerMemoizationFib(n-1) + innerMemoizationFib(n-2);
}
}

// キャッシュに値が保存されてる時はその値を返します
return cache[n];
}
return innerMemoizationFib(totalFibNumbers);
}

console.log(memoizationFib(50));
動的計画法

キャッシュを使うことによって再帰的な問題を解決する方法を動的計画法（Dynamic Programming: DP）
分割統治法（divide-and-conquer method）

コンピュータサイエンスにおいて分割統治法とは次の 3 つのステップを再帰的に実装する方法を指します。

・分割 : 問題全体を同じ構造の小さな問題に分割します
・統治 : それ以上分割できない規模になったら、これを解いて部分問題の解を求めます
・合併 : 求めた多数の部分問題の解を分割と逆方向に順番に併合していき、全体を一つに統合します

https://recursionist.io/dashboard/course/2/lesson/262

動的計画法を学びましたが、分割統治法は少し違う手法です。分割統治法は問題を部分問題に分割しますが、これらの部分問題は重複せず、それぞれ独立的に解きます。

例えば、配列に分割統治法を適用する場合、配列を半分に再帰的に分割し、1 つの要素に到達するまで繰り返します。ベースケースは要素が 1 つになった時です。
アセンブリとアセンブラの関係を示せ

アセンブリが言語で、これを機械語にするのがアセンブラという方法
アセンブリ言語と機械語は？：？の関係か

1:1
機械語（マシン語）とバイトコード（中間言語）の違いは何か？Javaを使って説明せよ

バイトコードとはソースコードをコンパイルした中間生成物のこと。機械はこれを解釈できない。

思想としてJava以前は各OS、アーキテクチャごとにコンパイルを行いバイナリを生成していたが、この場合開発者がさまざまなマシンを持っている必要があった。
※そのためソースコードを配布し、makefile によって利用者がビルド、コンパイルする方式がメインだった

これを避けるため、JavaではJDKが入っていれば各マシン上のJVMで動作させることで、OS・アーキテクチャの差分を埋めた。このJVMで動作する状態がバイトコードである。

ちなみに Go や Rust ではコマンド一発でクロスコンパイルが可能なので、かつてのような手間はない。
CPUのクロック数は何の意味？3GHzは何を表す？

クロック数は、CPUが動くきっかけとなるクロック信号をどの頻度で発生させるかの値です。1GHzで10億回/秒です。クロック数が大きいほどCPUは高速に動きます。
32bitのCPUアーキテクチャが32bitの数値しか扱えない理由をレジスタを使って説明しろ

32bit というのはCPUの中に存在するレジスタが一度に扱えるデータサイズのこと。レジスタはメモリアドレスをそのまま扱うこともあるので、最大でも32bitのメモリアドレスしかレジスタは対応できない。

そのため、32bitのメモリアドレスまでしかメモリを管理できないので 2^32 ≒ 4GB のメモリしか扱えないことになる。
UTF-8 とは何か、何バイトで文字を格納しているか？

また、どのように各バイトが先頭ではないor先頭であることを任ん指揮させているのか？

文字符号化方式。1~4バイトの可変長。

上位bitが00か01か11なら文字の先頭バイト、10なら非先頭バイト

❯ cat texifile2
あいうえお

❯ xxd -bits texifile2
00000000: 11100011 10000001 10000010 11100011 10000001 10000100 ......
00000006: 11100011 10000001 10000110 11100011 10000001 10001000 ......
0000000c: 11100011 10000001 10001010 00001010 ....

https://atmarkit.itmedia.co.jp/ait/articles/1603/28/news035.html#:~:text=%E3%80%8CUTF%2D8%EF%BC%88Unicode%20Encoding,%E3%81%AB%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82
プレーンテキストにおいてはマジックナンバーが存在しないが、file コマンドはどのように ascii / unicode を識別しているのか？

file コマンドはCharacter Encoding Detection（文字エンコーディング検出機能）を用いている。

> マジックファイルのどの項目とも一致しない場合、そのファイルがテキストファイルと思えるかどうか調べます。ASCII、ISO-8859-x、非ISO 8ビット拡張ASCII文字セット（MacintoshやIBM PCシステムで使われているようなもの）、UTF-8エンコードUnicode、UTF-16エンコードUnicode、EBCDIC文字セットは、それぞれのセットで印刷可能テキストとなるバイトの範囲とシーケンスが異なることによって区別できるようになっています。ファイルがこれらのテストのいずれかに合格した場合、その文字セットが報告されます。

https://stackoverflow.com/questions/58328993/how-does-the-linux-command-file-recognize-the-encoding-of-my-files
linux にはバイナリフォーマットがどのようなファイルなのか識別するためにどのような方法を用いているか？

先頭に決まったマジックナンバーを付与することで種類を規定している
ミドルウェアとは何か？説明せよ。

ミドルウェアは OS の拡張機能です。

OS が提供している機能を超える機能を提供しており、ミドルウェアを使用するとアプリケーションの開発が簡素化されます。コマンドやライブラリなども考え方によっては OS を拡張している機能と言えなくはないのですが、ミドルウェアは一般的に OS の起動と同時に起動してシステムで動く複数のアプリケーションへ統一したサービスを提供するという点でより OS に近い機能を持っていると言えます。
プロセス間通信として使われる方法を3つ答えよ

pipe / network / file
ユーザーランドとカーネルをまたがる処理やデータ通信　と　ユーザランド間の通信を比較した場合どちらが早いか？

ユーザランド間の通信の方が早い

同じことを行う関数があったとして、アプリケーションからの呼び出しであれば同じユーザーランドのシステムライブラリを利用するほうが速いということです。

https://qiita.com/ko1nksm/items/935be63e940f00e4c228#%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%AB%E3%81%A8%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89
オペランドのデータ型によって演算子の機能が変わることをなんという？

オーバーロード
参照型が必要な理由を答えよ

プリミティブ型はどの程度のメモリを使用するのかが明確に定義できる。しかし文字列の場合は何文字連なるかが決まっていない。

文字列は文字型の配列なので、その文字列を指しいいているメモリアドレスを保管するだけで文字が何文字だろうが判定できるようにした。これを参照型という。このため、入れるまでどの程度のサイズになるかわからないものを管理するために参照というテクニックが登場した。
クロージャとは何か？利点は？

関数閉包と呼ばれる。宣言時に引数以外の変数を実行時の環境ではなく、地震んが定義された静的スコープにおいて解決することができる。

外側のローカル変数を取り込み、呼び出しの都度初期化されずに利用できるため、グローバル変数の策げにゃ、コールバック関数の記述が簡素化できる。
cpuとメモリ、i/oの間には何種類の線があるか？それぞれの名前と役割を答えよ。

データ線(データを送る
アドレス線(参照、書き込むアドレスを指定
制御線(w or r 、メモリ or ioを区別する)
構造化プログラミングとは？

順次、分岐、繰り返しのみでプログラムを書いて、goto を使わないようにしようというダイクストラの提唱した方法。1969年
ユークリッドの互除法とは

割り算の等式：a=bq+ra=bq+r において，

「a と b の最大公約数」＝「b と r の最大公約数」という重要な性質を使って最大公約数の計算を行う公式
データベースにおける参照整合性とは？

fkをつかうことで、使ってるデータを消させない仕組み
リレーションにおいて多対多がダメな理由は？

どちらかが1じゃないと外部キーから主キーに結びつけられないから
高階関数

ある関数が別の関数を引数としてうけとるか、もしくは関数を戻り値として返すかのいずれかに該当するもの
純粋関数

引数と戻り値があり、イミュータブルに戻り値を返すこと
テストする

よく頑張りました

暗記スタート

cs

暗記

ビューア設定