『Pythonによるプログラミング入門 東京大学教養学部テキスト: アルゴリズムと情報科学の基礎を学ぶ』学習メモ（2020年4月に書いていたもの）
構成
1.はじめに
2.まずは使ってみる
3.プログラムを作ろう
4.データ処理の基本：成績の集計
5.ライフゲーム
6.放物運動のシミュレーション
幕間 テストとデバッグの基本
7.p値の計算
8.大規模データの検索
9.データからの情報抽出：回帰分析
10.拡散のシミュレーション
11.高度な検索：ゲノムを解析する
12.データを分類する
1.はじめに
- 情報科学における基礎的な問題の軽減のため、プログラミングにあたっては以下のアプローチを取る必要がある。
- プログラムの正しさを確認する。不正確度を検証する。
- プログラムが現実的な時間で扱えるデータの規模を確認する。
2.まずは使ってみる
- プログラミングを始める
- Python開発環境の扱い方。
- 計算
- 整数と小数
- 誤差
- 指数表記（eを使った表記）
- 変数の導入、変数での表現
- プログラムの書き方
3.プログラムを作ろう
- プログラム作成にあたって
- 関数
- ライブラリ
- 組み込みライブラリ
- 値を返さない関数：結果がNoneとなる
4.データ処理の基本：成績の集計
- データ処理の基本・電子データでの表現について
- 配列
- len()
- 繰り返し
- range()
- 分岐
- プログラムの検証
- 正しさ
- テスト
- 可視化
- 時間
- 見積る
- 正しさ
- for文・繰り返しについて
- iteratorの仕組み
- オブジェクトについて
- 誤差
- 平均
- 分散
- 最大値
- 配列の任意の要素を初期値として比較を繰り返す
- 処理の分離・疎結合
- 配列の次元
- 文字列
- 型
練習問題でのポイント
- 多次元配列
range()の扱い
def ex4_8(l): if l[0] > l[1]: subMax = l[1] max = l[0] else: subMax = l[0] max = l[1] for i in range(2, len(l)): if max < l[i]: subMax = max max = l[i] elif subMax < l[i]: subMax = l[i] return subMax def ex4_9(scores): max = scores[0][0] for i in range(len(scores)): if max < scores[i][0]: max = scores[i][0] return max文字列の配列も多次元配列として扱う
def ex4_10(strs, char): cnt = 0 for x in strs: for i in range(len(x)): if x[i] == char: cnt += 1 return cnt
5.ライフゲーム
- プログラミング（変数・関数・配列・for文・if文）の理解を深めるため、ライフゲームを例に見ていく
- モジュール化：シミュレーション処理の、部品への適切な分解。
- →拡張性・保守性
- 例：全体の表現 ＋ 個別の処理 ＋ シミュレーション（1ステップ（一まとまりの処理）の複数回実行）
- 可視化
- 配列の操作
スライス
> a = [8, 6, 2, 5, 4, 1] > a[0 : 4] [8, 6, 2, 5]スライス＠負数
- インデックスに負数を指定したとき、末尾の要素を-1とする相対インデックスとして解釈する
内包表記
> [i for i in range(0, 7) if i % 2 == 0] [0, 2, 4, 6]append()
- 参照型
- 明示コピー
- ディープコピー、シャローコピー
練習問題でのポイント
座標
def ex5_5(img, y1, x1, y2, x2, color): # x1 < x2, y1 < y2を仮定 for y in range(y1, y2 + 1): for x in range(x1, x2 + 1): if (0 <= y < len(img) and 0 <= x < len(img[y])): img[y][x] = color幾何の復習
def ex5_6(img, y1, x1, y2, x2, color): if x2 - x1 > y2 - y1: for x in range(x1, x2 + 1): y = round((y2 - y1) / (x2 - x1) * (x - x1) + y1) if (0 <= y < len(img) and 0 <= x < len(img[y])): img[y][x] = color else: for y in range(y1, y2 + 1): x = round((x2 - x1) / (y2 - y1) * (y - y1) + x1) if (0 <= y < len(img) and 0 <= x < len(img[y])): img[y][x] = color同時変化：コピーが必要
def step(room): m = len(room) n = len(room[0]) nextRoom = ita.array.make2d(m, n) for k in range(2): for i in range(m): for j in range(n): if room[i][j] == 1 and not i == j == 0: if k == 0: if j != 0 and room[i][j - 1] == 0: nextRoom[i][j - 1] = 1 else: # 変わらないパターンを忘れない nextRoom[i][j] = 1 else: if i != 0 and room[i - 1][j] == 0: nextRoom[i - 1][j] = 1 else: nextRoom[i][j] = 1 room = nextRoom nextRoom = ita.array.make2d(m, n) return room def ex5_7(room, n): for i in range(n): room = step(room) return room
6.放物運動のシミュレーション
- 連立微分方程式で表現する現象のモデル化・シミュレーション
- 差分化：「微分している変数のごく小さな変化」で表現する（「微分している変数のごく小さな変化」に関する方程式で近似する）。
Δtによる近似で、x(t + Δt) = (x(t)の式)の形で表現する。
微分方程式をもとに、(t + Δt)とtについての漸化式を導出する。def population_step(x, a, b, stride): return a * x * stride - b * (x ** 2) * stride + x def ex6_4(init, a, b, stride, n): populationSteps = ita.array.make1d(n) population = init for i in range(0, n): population = population_step(population, a, b, stride) populationSteps[i] = population return populationSteps定積分の差分化
- 関数のコードでの表現
while条件
def integral_step(g, f, stride): return g + f * stride def ex6_5(f, stride, a, b): x = a g = 0 integral = 0 while x < b - stride * 0.1: g = integral_step(g, f(x), stride) x += stride integral += g return g def square(x): # f引数とする関数 return x * x
シミュレーションのプログラム・モデル化に必要な処理・表現
- 可視化による正しさの検証
- モジュール化による柔軟なモデル
- OOD
- 繰り返しのbreak
練習問題でのポイント
配列操作
逆順イテレーション
def ex6_2(n, m): for i in reversed(range(1, min(n, m))): if n % i == 0 and m % i ==0: return i
計算量
def ex6_3(n): i = 0 while 2 ** i < n: i += 1 return i微分方程式をもとに、(t + Δt)とtについての漸化式を導出→ex6_4()
- 定積分の差分化・while条件→ex6_5()
幕間 テストとデバッグの基本
- コーナーケース
- デバッグ手順
- バグ範囲を狭める
- 可読性
7.p値の計算
- p値：probability値
- p値の利用の制限・p値の不適切な利用
- p値を計算するプログラム
- 組み合わせの計算
- 漸化式と再帰関数
- 漸化式を解く
- 同じ形
- アルゴリズム：問題に対する解凍を正しく求める手順
- 問題の解法を、計算量で比較する
- 漸近計算量の算出
- O記法
- 漸近計算量の算出
- 再帰モデル
- 問題の解法を、計算量で比較する
- 乱数シミュレーション
- 乱数を処理する1ステップとステップを用いたシミュレートにより、p値の近似値を導出する
- モンテカルロ法→複雑な形状でも内外が分かれば面積を導出できる
- 疑似乱数の性質
- 疑似乱数プログラム（二項分布）の検証
- 実行速度と精度のトレードオフ
- 疑似乱数プログラム（二項分布）の検証
練習問題でのポイント
計算量
再帰関数は漸化式で計算量を表す。
def ex7_3(n): if n == 0: return 0 elif n > 0: return ex7_3(n - 1) + n実行時間で検証する
import time t1 = time.time() ex7_3(1000) t2 = time.time() print((t2 - t1) * 1000) %%timeit ex7_3(1000)
-
def ex8_5(n): line = ita.array.make1d(3 ** n) cantor_main(line, 0, 3 ** n) return line def cantor_main(line, i, m): if m == 1: line[i] = 1 else: cantor_main(line, i, m // 3) cantor_main(line, i + m * 2 // 3, m // 3) -
def ex8_6(n): image = ita.array.make2d(3 ** n, 3 ** n) vicsek_main(image, 0, 0, 3 ** n) return image def vicsek_main(image, x, y, size): if size == 1: image[x][y] = 1 else: m = size // 3 vicsek_main(image, x + m, y, m) vicsek_main(image, x, y + m, m) vicsek_main(image, x + m, y + m, m) vicsek_main(image, x + 2 * m, y + m, m) vicsek_main(image, x + m, y + 2 * m, m) メモ化による計算量の削減
def ex8_7(n): nums = ita.array.make1d(n) nums[0] = 1 nums[1] = 1 for i in range(2, n): nums[i] = nums[i - 1] + nums[i - 2] return nums[n - 1]-
randrange(1,7)で1から6を表す
import random def sumDicesNums(): sum = 0 for i in range(5): sum += random.randrange(1, 7) return sum def ex8_8(step): under20 = 0 for i in range(step): if sumDicesNums() <= 20: under20 += 1 return under20 / step積分：y <= f(x)となった回数にxの範囲を掛けることで求められる
import random import math def ex8_9(step): cnt = 0 for i in range(step): x = random.random() * math.pi / 2 y = random.random() if y <= math.sin(x): cnt += 1 return cnt / step * math.pi / 2random()で確率を表す
import random def isAWinMatch(): winA = 0 for i in range(7): if random.random() <= 0.55: winA += 1 return winA >= 4 def ex8_10(step): cnt = 0 for i in range(step): if isAWinMatch(): cnt += 1 return cnt / step
8.大規模データの検索
- 大規模データの検索・集約
- 線形探索
- 二分探索
- start,endを操作する
- 同じデータに何度も検索を行う場合や、既に整列済みのデータに対してのみ有効
- ヒストグラム（分類）の計算
- 併合整列法
- 分割統治法に基づく
- 分割統治法：大きなデータはとりあえず小さなデータに分けて処理をし、後でその結果を併合する
- 再帰における注意点
- 小さい入力の結果から大きい入力の結果が得られること
- 十分小さな入力の結果がわかっていること
- 計算量
- n = 2 ** kとなるk回の分割で終わるため、O(nlogn)
- 分割統治法に基づく
- 時間計算量と空間計算量（メモリ使用量）
- データ構造
- 集合（set）
- 1集合に重複要素不可
- 辞書（dict）
- 集合（set）
- 文章の分析の例
練習問題のポイント
二分探索は、不等号のときも限界値を探索できる ← start = endでwhileを抜ける
def searchStartIdx(data, a): start = 0 end = len(data) while start != end: center = (start + end) // 2 if data[center] < a: start = center + 1 else: end = center return start def searchLastIdx(data, b): start = 0 end = len(data) while start != end: center = (start + end) // 2 if data[center] > b: end = center else: start = center + 1 return end def ex9_2(data, a, b): return searchLastIdx(data, b) - searchStartIdx(data, a)併合：インデックスを保持
併合整列・分割統治：未整列のデータの探索の繰り返しを、logn回に抑え込むdef mergeByK(data1, data2, k): mergedList = ita.array.make1d(min(k, len(data1) + len(data2))) idx1 = 0 idx2 = 0 for i in range(min(k, len(mergedList))): if (idx2 >= len(data2) or (idx1 < len(data1) and data1[idx1] <= data2[idx2])): mergedList[i] = data1[idx1] idx1 += 1 else: mergedList[i] = data2[idx2] idx2 += 1 return mergedList def ex9_5(data, k): n = len(data) if n <= 1: return data else: data1 = ex9_5(data[0 : n // 2], k) data2 = ex9_5(data[n // 2 : n], k) return mergeByK(data1, data2, k)重複する要素を除いた併合
- 併合結果と同じ性質を併合元データは持つ
併合で重複を排除するインデックス操作をすることで、いずれの併合元内でもユニークな要素のみ持つ状態となる
def merge(data1, data2): mergedList = [] idx1 = 0 idx2 = 0 l1 = len(data1) l2 = len(data2) while idx1 < l1 or idx2 < l2: if (idx2 >= l2 or (idx1 < l1 and data1[idx1] < data2[idx2])): elem = data1[idx1] mergedList.append(elem) idx1 += 1 elif idx1 >= l1 or data1[idx1] > data2[idx2]: elem = data2[idx2] mergedList.append(elem) idx2 += 1 else: elem = data1[idx1] mergedList.append(elem) idx1 += 1 idx2 += 1 return mergedList def ex9_6(data): n = len(data) if n <= 1: return data else: data1 = ex9_6(data[0 : n // 2]) data2 = ex9_6(data[n // 2 : n]) return merge(data1, data2)
9.データからの情報抽出：回帰分析
- 巨大なデータの集約→要約が重要となっている。
- 回帰分析
- 最小2乗法
- 数値誤差が生じるパターン
- 浮動小数点数の計算
- ピボット選択で誤差を回避
- 誤差のない行とswap
練習問題のポイント
-
> 0.1 + 0.1 + 0.1 0.30000000000000004 > print(0.10000000000000001) 0.1 > a = 0.5 > b = -0.9999999 > c = 0.4999999 > b ** 2 0.9999998000000101 > - 4 * a * c -0.9999998 > b ** 2 - 4 * a * c 1.0103029524088925e-14 def average(scores): #scores中の成績の平均を求める return total(scores) / len(scores) def total(scores): #scores中の成績の総和を求める s = 0 for x in scores: s = s + x return s def variance2(scores): #scores中の成績の分散を求める s = 0 for i in range(0, len(scores)): s = s + scores[i] ** 2 return s / len(scores) - average(scores) ** 2 > x = 10 ** 5 > variance2([x + 0.1, x - 0.1, x + 0.1, x - 0.1]) 0.009998321533203125 > x = 10 ** 7 > variance2([x + 0.1, x - 0.1, x + 0.1, x - 0.1]) 0.0
10.拡散のシミュレーション
- 言葉の定義の確認
- 差分化 ＋ 初期値 ＋ 境界条件：シミュレーションの設定
- 1次元配列の可視化
- アニメーションのために、各時間ステップでの結果を格納した配列を作成
- 安定/不安定
- シミュレーションが安定するための条件
- k次式のテイラー展開による誤差の評価
- 前進差分→中心差分で誤差を小さくする
- 誤差のあるプログラム・処理のテスト
練習問題のポイント
差分化による微分の導出
差分化の式をそのまま返す
def ex11_1(func, dx, x): return (func(x + dx) - func(x)) / dx def square(x): return x * x > ex11_1(square, 0.001, 0) 0.001 > ex11_1(square, 0.001, 3) 6.000999999999479
前進差分誤差 ≒ 後退差分誤差
2階微分方程式のシミュレーション
import math def ex11_3(th, l, dt, step): g = 9.8 pastTh = th curTh = th thList = ita.array.make1d(step) for i in range(step): nextTh = 2 * curTh - pastTh - g / l * math.sin(curTh) * dt ** 2 pastTh = curTh curTh = nextTh thList[i] = curTh return thList
11.高度な検索：ゲノムを解析する
練習問題のポイント
2次元のDP
- 2変数漸化式は、2変数ともループが必要
配列生成時の初期値の設定
import ita def isSumM(isSumMList, curNum, i, m): if i == 0: if m == 0 or curNum == m: return True else: return False elif i < 0: return False else: if m >= curNum: return isSumMList[i - 1][m] or isSumMList[i - 1][m - curNum] else: return isSumMList[i - 1][m] def ex12_1(data): n = len(data) m = 100 isSumMList = ita.array.make2d(n, m, value = False) for i in range(n): for j in range(m): isSumMList[i][j] = isSumM(isSumMList, data[i], i, j) return isSumMList[n - 1][m - 1]
3項間漸化式
def ex12_2(points, days): n = min(len(points), days) pointsList = ita.array.make1d(n) pointsList[0] = points[0] pointsList[1] = max(pointsList[0], points[1]) for i in range(2, n): pointsList[i] = max(pointsList[i - 1], pointsList[i - 2] + points[i]) return pointsList[n - 1]全ての項が関わる漸化式（ C(i) = （0 <= j <= i - 1 について、(C(j) + cost(j, i)) の最小））
- 各項ごとに、対象の項まで繰り返す
最後の繰り返しの結果が答となる
def ex12_3(cost, n): costList = ita.array.make1d(n + 1) costList[0] = cost(0, n) for i in range(n + 1): minC = cost(0, i) for j in range(i): minC = min(minC, costList[j] + cost(j, i)) costList[i] = minC return costList[n]
確率漸化式でのDP
def ex12_4(p, q, t, a): probList = ita.array.make2d(t + 1, 11) probList[0][5] = 1 for i in range(1, t + 1): for j in range(11): if 0 <= j <= 1: probList[i][j] = q * probList[i - 1][j + 1] elif 2 <= j <= 8: probList[i][j] = p * probList[i - 1][j - 1] + q * probList[i - 1][j + 1] else: probList[i][j] = p * probList[i - 1][j - 1] return probList[t][a]
