Week 1: コンピューターサイエンス入門¶

1. コンピューターサイエンスの基本概念¶

コンピューターサイエンスは、情報の処理と計算に関する理論と実践を扱う学問です。この分野は、問題解決、アルゴリズム設計、データ処理、プログラミング言語理論、ソフトウェア工学など、幅広いトピックを包含しています。

graph LR
    A[CPU]
    B[メモリ]
    C[ストレージ]
    D[入出力装置]
    A --> B
    B --> A
    A --> C
    C --> A
    A --> D
    D --> A

1.1 情報と表現¶

コンピューターは全ての情報をデジタル形式、つまり0と1の組み合わせで表現します。この二進法表現は、コンピューターの動作の基礎となっています。

1.1.1 ビットとバイト¶

ビット（bit）: デジタルデータの最小単位。0または1の値を取る。
バイト（byte）: 8ビットの集まり。2^8 = 256 種類の値を表現できる。

graph TD
    A[ビット（bit）] --> B[バイト（byte）]
    B --> C[8ビット]
    A --> D[デジタルデータの最小単位]
    D --> E[0または1の値を取る]
    C --> F[256種類の値を表現できる]
    B --> G[メモリ容量やファイルサイズの単位として使用]

10進数 (Decimal)	16進数 (Hexadecimal)	2進数 (Binary)
0	0	0000
1	1	0001
2	2	0010
3	3	0011
4	4	0100
5	5	0101
6	6	0110
7	7	0111
8	8	1000
9	9	1001
10	A	1010
11	B	1011
12	C	1100
13	D	1101
14	E	1110
15	F	1111

1	`文字 'A' → ASCII コード 65(dec) → 0x41 → 二進表現 01000001`

	0	1	2	3	4	5	6	7
0	NUL	DLE	SPC	0	@	P	`	p
1	SOH	DC1	!	1	A	Q	a	q
2	STX	DC2	"	2	B	R	b	r
3	ETX	DC3	#	3	C	S	c	s
4	EOT	DC4	$	4	D	T	d	t
5	ENQ	NAK	%	5	E	U	e	u
6	ACK	SYN	&	6	F	V	f	v
7	BEL	ETB	'	7	G	W	g	w
8	BS	CAN	(	8	H	X	h	x
9	TAB	EM	)	9	I	Y	i	y
A	LF	SUB	*	:	J	Z	j	z
B	VT	ESC	+	;	K	[	k	{
C	FF	FS	,	<	L	\	l	\|
D	CR	GS	-	=	M	]	m	}
E	SO	RS	.	>	N	^	n	~
F	SI	US	/	?	O	_	o	DEL

1.1.2 文字エンコーディング¶

文字エンコーディングは、文字をコンピューターが理解できる数値（コードポイント）に変換する方法です。

ASCII: 128文字（英数字と基本的な記号）を7ビットで表現
Unicode: 世界中のほぼ全ての文字を網羅。UTF-8, UTF-16などの実装がある

例：日本語の「あ」のUnicode表現（UTF-8）

1	`「あ」 → Unicode コードポイント U+3042 → UTF-8 エンコード E3 81 82`

1.2 アルゴリズムとプログラム¶

アルゴリズムは、問題を解決するための一連の明確な手順です。プログラムは、これらの手順をコンピューターが理解できる言語で表現したものです。

1.2.1 アルゴリズムの特性¶

入力: アルゴリズムは0個以上の入力を受け取る
出力: アルゴリズムは1個以上の出力を生成する
明確性: 各ステップが明確に定義されている
有限性: 有限回のステップで終了する
実行可能性: 各ステップが実行可能である

1.2.2 プログラミング言語の種類¶

低水準言語: マシン語、アセンブリ言語
- コンピューターが直接理解できる
- ハードウェアに密接に関連
- 例: x86アセンブリ
高水準言語: C, Python, Java, Javascriptなど
- 人間が理解しやすい
- 抽象度が高い
- コンパイラーやインタープリターを通じて機械語に変換される

例: 「Hello, World!」を出力する簡単なプログラム

Python:

print("Hello, World!")

C:

#include <stdio.h>

int main() {
    printf("Hello, World!\n");
    return 0;
}

2. 問題解決とアルゴリズム入門¶

問題解決は、与えられた問題を分析し、効率的な解決策を見出すプロセスです。アルゴリズム的思考は、この過程で重要な役割を果たします。

2.1 問題分析¶

問題の明確化: 何が求められているかを明確に理解する
入力と出力の特定: 問題に必要な情報（入力）と、期待される結果（出力）を明確にする
制約条件の理解: 時間、空間、リソースなどの制限を把握する

例: 整数の配列から最大値を見つける問題

入力: 整数の配列 [3, 7, 2, 9, 1, 5]
出力: 配列内の最大値 (この場合は9)
制約: 配列の要素数は1以上

2.2 アルゴリズム設計の基本ステップ¶

問題の分割: 大きな問題を小さな部分問題に分割する
パターンの認識: 類似の問題やサブ問題を特定する
抽象化: 本質的な部分に焦点を当て、不要な詳細を省略する
アルゴリズムの記述: 解決手順を段階的に記述する

例: 最大値を見つけるアルゴリズム（疑似コード）

関数 最大値を見つける(配列):
    最大値 = 配列の最初の要素
    それぞれの要素について:
        もし 要素 > 最大値:
            最大値 = 要素
    最大値を返す

2.3 アルゴリズムの表現方法¶

自然言語: 日常的な言葉で手順を説明
フローチャート: 図形と矢印を使用して手順を視覚的に表現
疑似コード: プログラミング言語に似た構造化された記述
プログラミング言語: 特定の言語を用いた具体的な実装

例: 最大値を見つけるアルゴリズムのフローチャート

flowchart TD
    A[開始] --> B[最大値 = 配列の最初の要素]
    B --> C{配列の全ての要素をチェックしたか?}
    C -->|いいえ| D[次の要素を取得]
    D --> E{要素 > 最大値?}
    E -->|はい| F[最大値 = 要素]
    E -->|いいえ| C
    F --> C
    C -->|はい| G[最大値を返す]
    G --> H[終了]

3. 基本的なデータ表現¶

コンピューターでのデータ表現を理解することは、効率的なプログラミングと問題解決の基礎となります。

3.1 数値システム¶

2進数（基数2）: 0と1のみを使用
- コンピューターの内部表現に使用される
- 例: 1010 (2進数) = 10 (10進数)
10進数（基数10）: 0から9までの数字を使用
- 人間が日常的に使用する数値システム
- 例: 42 (10進数)
16進数（基数16）: 0から9の数字とAからFまでの文字を使用
- コンピューターサイエンスでよく使用される（メモリアドレス、色コードなど）
- 例: 2A (16進数) = 42 (10進数)

3.2 2進数と16進数の変換¶

3.2.1 10進数から2進数への変換¶

方法: 2で割り続け、余りを下から読み上げる

例: 42 (10進数) → 101010 (2進数)

計算過程：
42 ÷ 2 = 21 余り 0
21 ÷ 2 = 10 余り 1
10 ÷ 2 = 5  余り 0
5 ÷ 2  = 2  余り 1
2 ÷ 2  = 1  余り 0
1 ÷ 2  = 0  余り 1

余りを下から読み上げると：101010

3.2.2 10進数から16進数への変換¶

方法: 16で割り、余りを16進数の数字に置き換える

例: 42 (10進数) → 2A (16進数)

計算過程：
42 ÷ 16 = 2 余り 10

2と10(A)を組み合わせて：2A

3.2.3 2進数と16進数の相互変換¶

2進数から16進数への変換は、2進数を4桁ずつグループ化し、各グループを16進数に変換します。

例: 101010 (2進数) → 2A (16進数)

101010 → 10 1010
10   → 2
1010 → A
結果: 2A

16進数から2進数への変換は、各16進数字を4桁の2進数に変換します。

例: 2A (16進数) → 101010 (2進数)

1
2
3

2 → 0010
A → 1010
結果: 00101010 (先頭の0は省略可能)

3.3 浮動小数点数¶

浮動小数点数は、コンピューターで小数を表現するための方式です。IEEE 754規格が広く使用されています。

構成要素:

符号ビット: 正負を表す（0が正、1が負）
指数部: 小数点の位置を指定
仮数部: 実際の数値

例: 単精度浮動小数点数（32ビット）

1	`[符号(1ビット)][指数部(8ビット)][仮数部(23ビット)]`

浮動小数点数の特徴:

非常に大きな数値範囲を表現できる
計算速度が整数に比べて遅い
丸め誤差が発生する可能性がある

4. 実践演習¶

4.1 日常生活のタスクをアルゴリズムとして記述¶

目的: 日常的なタスクをアルゴリズムとして表現することで、アルゴリズム的思考を養います。

タスク: 「朝のルーチン」をアルゴリズムとして記述してください。

例:

起床する
もし時間が7:00以前なら、アラームをスヌーズし、ステップ1に戻る
ベッドから出る
歯を磨く
顔を洗う
もしコーヒーを飲む習慣があれば、コーヒーを入れる
朝食の準備をする
朝食を食べる
服を着る
家を出る

このアルゴリズムを、前述のフローチャートや疑似コードで表現してみましょう。

4.2 基数変換の演習¶

目的: 異なる基数間での数値の変換を練習します。

タスク:

以下の10進数を2進数に変換してください： a) 15 b) 27 c) 64
以下の2進数を16進数に変換してください： a) 1100 1010 b) 1111 0000 c) 1010 1111
以下の16進数を10進数に変換してください： a) 3A b) CF c) 80

4.3 簡単なプログラミング演習¶

目的: 基本的なプログラミング概念を実践的に学びます。

タスク: 以下の問題を解決するプログラムを作成してください（疑似コードまたは任意のプログラミング言語で）。

ユーザーから入力された数が偶数か奇数かを判定するプログラム
1から100までの数字のうち、3の倍数のみを表示するプログラム
ユーザーから入力された文字列が回文（前から読んでも後ろから読んでも同じ）かどうかを判定するプログラム

これらの演習を通じて、学んだ概念を実践的に適用し、プログラミング的思考を養うことができます。

5. まとめと次週への橋渡し¶

Week 1では、コンピューターサイエンスの基本概念、問題解決とアルゴリズム、基本的なデータ表現について学びました。これらの知識は、プログラミングや高度なアルゴリズム設計の基礎となります。

次週（Week 2）では、これらの基礎の上に立って、より具体的なデータ構造について学びます。変数とデータ型、配列とリスト、スタックとキューなど、プログラミングで頻繁に使用される基本的なデータ構造を扱います。これらの構造を理解することで、より効率的なアルゴリズムの設計と実装が可能になります。

準備として、簡単なプログラミング言語（例えばPython）の基本的な文法を復習しておくと良いでしょう。

	0	1	2	3	4	5	6	7
0	NUL	DLE	SPC	0	@	P	`	p
1	SOH	DC1	!	1	A	Q	a	q
2	STX	DC2	"	2	B	R	b	r
3	ETX	DC3	#	3	C	S	c	s
4	EOT	DC4	$	4	D	T	d	t
5	ENQ	NAK	%	5	E	U	e	u
6	ACK	SYN	&	6	F	V	f	v
7	BEL	ETB	'	7	G	W	g	w
8	BS	CAN	(	8	H	X	h	x
9	TAB	EM	)	9	I	Y	i	y
A	LF	SUB	*	:	J	Z	j	z
B	VT	ESC	+	;	K	[	k	{
C	FF	FS	,	<	L	\	l	\|
D	CR	GS	-	=	M	]	m	}
E	SO	RS	.	>	N	^	n	~
F	SI	US	/	?	O	_	o	DEL

	0	1	2	3	4	5	6	7
0	NUL	DLE	SPC	0	@	P	`	p
1	SOH	DC1	!	1	A	Q	a	q
2	STX	DC2	"	2	B	R	b	r
3	ETX	DC3	#	3	C	S	c	s
4	EOT	DC4	$	4	D	T	d	t
5	ENQ	NAK	%	5	E	U	e	u
6	ACK	SYN	&	6	F	V	f	v
7	BEL	ETB	'	7	G	W	g	w
8	BS	CAN	(	8	H	X	h	x
9	TAB	EM	)	9	I	Y	i	y
A	LF	SUB	*	:	J	Z	j	z
B	VT	ESC	+	;	K	[	k	{
C	FF	FS	,	<	L	\	l	\|
D	CR	GS	-	=	M	]	m	}
E	SO	RS	.	>	N	^	n	~
F	SI	US	/	?	O	_	o	DEL

	0	1	2	3	4	5	6	7
0	NUL	DLE	SPC	0	@	P	`	p
1	SOH	DC1	!	1	A	Q	a	q
2	STX	DC2	"	2	B	R	b	r
3	ETX	DC3	#	3	C	S	c	s
4	EOT	DC4	$	4	D	T	d	t
5	ENQ	NAK	%	5	E	U	e	u
6	ACK	SYN	&	6	F	V	f	v
7	BEL	ETB	'	7	G	W	g	w
8	BS	CAN	(	8	H	X	h	x
9	TAB	EM	)	9	I	Y	i	y
A	LF	SUB	*	:	J	Z	j	z
B	VT	ESC	+	;	K	[	k	{
C	FF	FS	,	<	L	\	l	\|
D	CR	GS	-	=	M	]	m	}
E	SO	RS	.	>	N	^	n	~
F	SI	US	/	?	O	_	o	DEL