2020-06-14_hw オンライン プログラミング勉強会

08.10

この記事は6分で読めます

このサイトは学部では早稲田で物理を, 修士では東大で数学を専攻し, 今も非アカデミックの立場で数学や物理と向き合っている一市民の奮闘の記録です. 運営者情報および運営理念についてはこちらをご覧ください.

中高の数学の復習から専門的な数学・物理までいろいろな情報を発信しています.
中高数学に関しては自然を再現しようや役に立つ中高数学 中高数学お散歩コース
大学数学に関しては現代数学観光ツアーなどの無料の通信講座があります.
その他にも無料の通信講座はこちらのページにまとまっています.
ご興味のある方はぜひお気軽にご登録ください!

2020-06-14 課題

自分用メモ

  • 常微分方程式で漸化式から微分方程式に流れる部分の書き直し
  • 勉強のおすすめ：AtCoder はどうか？C++の解説もあるし、仕事・評価にも割と直結するし、具体的な問題つきで勉強できる。
    • https://atcoder.jp/contests/apg4b
      • C++のコードをPythonで書き直してみるだけでもかなりの勉強になるはず
    • Python によるアルゴリズム https://qiita.com/cabernet_rock/items/cdd12b07d213b67d0530
  • 文と式の説明
  • IT 基礎知識みたいなやつ
  • 数値計算に関わるクラス・オブジェクトの説明
    • まずは辞書・構造体の拡大版として導入するか？
    • 変な誤解を生まないような書き方を考える
  • 遅延型方程式に対するコメント追加
  • import に関する実演
  • matplotlib のチュートリアルを読もうの会
  • matplotlib 回では実際に matplotlib のチュートリアルを読もう
    • 公式情報に触れる重要性
    • 古い情報が古いと書いてあったりする：たとえば pylab
    • Gallery
      • 見ていて面白い
      • 「どこをいじるとどう変わるか」が視覚的にわかる
      • 公式情報なのできちんとアップデートしてくれている（はず）
      • 公式情報にソースがあるので自分でいろいろ書き換えていて破滅したとき、必ずオリジナルを復元できる
  • Jupyter （IPython）でのはまりどころ解説を作ろう
    • いったん変数を作ると他のセルでも読み込める（読み込めてしまう）
    • 「セルを上から順に読み込まないと動かない」問題の原因
    • カーネル再起動まで変数は残り続ける

Matplotlib

  • とりあえず本当に簡単な図を描く
import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-4, 4, 201)
y1 = - 0.5 * x + 1
y2 = np.sin(x)
y3 = np.cos(x)

plt.plot(x, y1)
plt.plot(x, y2)
plt.plot(x, y3)

plt.grid()
plt.axes().set_aspect('equal', 'datalim') # アスペクト比を合わせる
plt.show()
/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:14: MatplotlibDeprecationWarning: Adding an axes using the same arguments as a previous axes currently reuses the earlier instance.  In a future version, a new instance will always be created and returned.  Meanwhile, this warning can be suppressed, and the future behavior ensured, by passing a unique label to each axes instance.
png

勉強ネタ紹介

  • 前回も言ったように、自分に合った、楽しめるネタを探す必要がある
    • 勉強しなければいけないことと、やっていて楽しめること・長続きすることが一致しないこともよくある
  • 教材がある事案
  • 最近の私の趣味と実益を兼ねた対象がデータ構造とアルゴリズムなので、ここでもその辺を試してみている
  • 例えば上の中でも興味のあるネタがあればそれは取り上げるので、要望があれば挙げてほしい。
    • 自然言語処理の UNIX コマンドとか

競プロを 2 題解いてみる

  • https://qiita.com/KoyanagiHitoshi/items/c5e82841b8d0f750851d の 3 題目と最後の問題
  • AOJ も勉強用にお勧め
    • 素因数分解など数学ネタもある
    • これをもとにした本もある
    • 言語が C/C++ なのが難点といえば難点
    • C/C++ の方が低レイヤーを意識しやすくなる利点はある
  • 最近は Python によるデータ構造とアルゴリズムの本も出ているし、ネット上に資料もある

ABC081B、Shift only

# https://atcoder.jp/contests/abs/submissions/14323299
#input()
#A = list(map(int, input().split()))

def f(A):
    count = 0
    while all(a % 2 == 0 for a in A):
        A = [a/2 for a in A]
        count += 1
    print(count)

A = [8, 12, 40]
f(A)

A = [5, 6, 8, 10]
f(A)

A = [382253568, 723152896, 37802240, 379425024, 404894720, 471526144]
f(A)
2
0
8

Python の all

Pythonでリストやタプルなどのイテラブルオブジェクトの要素がすべてTrue（真）か、いずれか一つでもTrueか、あるいは、すべてFalse（偽）かを判定するには組み込み関数all(), any()を使う。

print(all([True, True, True]))
print(all([True, False]))
True
False

ABC086C、Traveling

  • 止まれない条件
    • 止まってよければ問題は簡単：時間に関する制約だけでいい
    • 非現実的な問題設定にしたおかげで難しくなっている
    • cf. たいていの場合は現実が難しすぎるから簡単にした問題を解く
  • 「距離」
    • 京都・札幌・マンハッタンのような碁盤目状に道が整備された街での 2 点間の距離をどう測るといいか？
      • 普通の2点間の距離（ユークリッド距離）$\sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2}$ では不適切。
      • $|x_1 – x_2| + |x_1 – x_2|$ で測る方が適切。
      • 機械学習でも $L^1$ 正則化などで出てくる。
      • 情報系（？）だとマンハッタン距離と呼ぶ。
      • 数学では $L^1$ ノルムと呼ぶ。
        • 一般には $L^p$ ノルムという概念がある
#N = int(input())
def f(N, course):
    count = 0
    T, X, Y = 0, 0, 0
    for i in range(N):
        #t, x, y = map(int, input().split()) # 都度読み込み：駄目な経路があれば即終了
        t, x, y = course[i]
        if abs(x-X)+abs(y-Y) <= t-T and t % 2 == (x+y) % 2:
            count += 1
        T, X, Y = t, x, y
    print("Yes" if count == N else "No")

N = 2
course = [(3, 1, 2,), (6, 1, 1)]
f(N, courses)

N = 1
course = [(2, 100, 100)]
f(N, course)

N = 2
course = [(5, 1, 1), (100, 1, 1)]
f(N, course)
Yes
No
No
if count == N:
    s = "Yes"
    if a == B:
        s = "a"
    elif a == C:
        s = "b"
else:
    s = "No"

現実的なスケジューリングの問題

  • Google Map の経路探索
  • Yahoo 路線情報などの経路探索
  • 野球・サッカーなどの年間試合日程
  • PASMO などでの運賃清算

PASMO などの運賃計算

  • 論文が出るほどの問題
    • 解説記事
    • https://www.orsj.or.jp/~archive/pdf/j_mag/Vol.54_J_001.pdf
    • https://www.seikei.ac.jp/university/rikou/pdf/JFST440213.pdf
    • https://ci.nii.ac.jp/naid/110008913789
  • 何が難しいか：乗車情報を使って東京の複雑な路線図から「最安運賃」を即座に計算させる
    • 使える時間は 0.2 秒
    • 運賃が高く計算されたら怒られる
    • 安ければ文句がでない
    • いくらでも変な経路がありうる
    • 余計な枝をはじいて重要な部分だけ計算する
  • どうやって：これがアルゴリズム研究
    • ほぼ純粋なプログラムだけの問題
  • テストの視点
    • どんな始点・終点であっても問題なく動くか、プログラムを検証する問題もある
    • 検証すべきパターンは $10^{40}$ 程度あるとか：解説記事

プロスポーツのスケジュール決定

  • OR の研究課題
  • 多数のステークホルダーの利害調整問題
    • ドームなどはコンサートもある
      • 著名アイドル・歌手の結成何周年イベントなどは「この時期、できれば第何週」というレベルで細かい指定が入る
      • ドル箱はもちろん優先
    • 春夏の甲子園の時期は高校野球に占拠される
    • 各チームが過酷な移動スケジュールにならないような配慮
      • 「九州から北海道に順に移動していき、逆順に移動していく」みたいな形だと移動の負担は少ない
      • 必ずしもそううまくは組めない
      • 長時間移動だけでも体力消費があり選手パフォーマンスに影響する
      • 旅費もかさむ
  • どうするか？
    • これも組み合わせは膨大で、電車ほど激しくはないが短時間で計算させたい
    • 最終的には人間の目も入れる必要があるだろう
    • コンピューターにいくつか候補を計算させたい
    • 適当にイベントと時期に重みづけ（ペナルティ）をつけて「一定程度以上ペナルティが積まれたスケジュールはもう考えない」といった工夫がいる
    • いい感じのスケジュールにならなければパラメータ調整して再計算させたい
      • このサイクルはなるべく早く回したい
      • 高速計算の需要
      • この辺は最近はやりの機械学習でもまさに同じような事情がある

プログラミングの一般論

  • Web システムを例にした速度問題
  • データ構造とアルゴリズム
    • 連結リストと配列：どんな特性があるか？
    • スタックとキュー：いつどこで使うか？どう実装するか？

web システムの事例

  • 参考
  • システムが重いというときどこにどんな原因があるか？
    • ソシャゲでもよくある「障害発生」はどこでどう起こるか？
    • どこかのサーバーが物理的に壊れることもある
  • データ構造とアルゴリズム（いわゆる「プログラミング」）がかかわるのはどこか？
    • web サーバーでの処理（プログラム）
    • データベースの（インデックス）設計
    • ソフトによる問題なら基本的にはどこにでもありうる

データ構造とアルゴリズム

  • 鶏と卵で、同時に考えるべきテーマ：何かをするためにはどうデータを持ってどんな処理をすれば効率がいいか？
    • 効率にもいろいろある
    • 単純な処理速度・メモリ消費量・計算量

（連結）リストと配列

  • 何が違うのか？
  • メモリ上の配置やデータの「つなぎ方」
  • 状況によって使い分ける

リストの特徴

  • 要素数は変わることが前提
  • データを（先頭に）追加するのは簡単
  • データの削除も比較的簡単
  • 先頭から 1 つずつ順に処理するならそれなり
  • 検索やデータの書き換えが遅い：連結構造をたどる必要がある

配列の特徴

  • 要素数は固定
  • データの追加・削除が重め
  • データの参照・書き換えが速い：アドレスが連続なので先頭さえわかれば「そこから何番先」と直指定できる
  • 「リストで遅ければ配列で書き直す」みたいなことはよくある

ベクター（参考）

  • 「要素数可変の配列」
  • リストのように要素追加・削除が比較的低コストで、要素の参照・書き換えも配列のように速い
  • 何が問題か：要素の追加が楽なように余計なメモリ領域を確保する
  • ハードウェア組み込みプログラムのように、メモリがカツカツの状況では使えない
    • 「メモリがカツカツ」という意味が理解できるか？

中高の数学の復習から専門的な数学・物理までいろいろな情報を発信しています.
中高数学に関しては自然を再現しようや役に立つ中高数学 中高数学お散歩コース
大学数学に関しては現代数学観光ツアーなどの無料の通信講座があります.
その他にも無料の通信講座はこちらのページにまとまっています.
ご興味のある方はぜひお気軽にご登録ください!

  • このエントリーをはてなブックマークに追加
  • LINEで送る

関連記事

  1. 2020 10.16

    2020-10-16 第 006 回 第 3 文の読解 アインシュタインの特殊相対性理論の原論文を多言語で読む会

  2. 2020 10.30

    2020-10-30 第 007 回 第 3 文の単語 アインシュタインの特殊相対性理論の原論文を多言語で読む会

  3. 2020 10.09

    2020-10-09 第 005 回 第 1-2 文の単語の掘り下げ アインシュタインの特殊相対性理論の原論文を多言語で読む会

  4. 2020 03.31

    緩募: Rust・Gnuplot・ffmpeg による 1 次元波動方程式の差分解法のバグ潰し

  5. 2020 03.08

    ケットベクトルとは何か–量子系の状態概念の数理

  6. 2020 08.10

    2020-05-10_hw オンライン プログラミング勉強会

  • コメント (0)

  • トラックバックは利用できません。

  1. この記事へのコメントはありません。

このサイトについて

数学・物理の情報を中心にアカデミックな話題を発信しています。詳しいプロフィールはこちらから。通信講座を中心に数学や物理を独学しやすい環境づくりを目指して日々活動しています。
  • このエントリーをはてなブックマークに追加
  • LINEで送る

YouTube チャンネル登録

講義など動画を使った形式の方が良いコンテンツは動画にしています。ぜひチャンネル登録を！

メルマガ登録

メルマガ登録ページからご登録ください。 数学・物理の専門的な情報と大学受験向けのメルマガの 2 種類があります。

役に立つ・面白い記事があればクリックを！


数学 人気ブログランキングへ

記事の編集ページから「おすすめ記事」を複数選択してください。