2020-07-26_hw オンライン プログラミング勉強会

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

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

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


2020-07-26 課題

メモ:先に進む前に録画してあるか確認しよう

自分用メモ

  • 勉強のおすすめ:AtCoder はどうか?C++の解説もあるし、仕事・評価にも割と直結するし、具体的な問題つきで勉強できる。
    • https://atcoder.jp/contests/apg4b
      • C++のコードをPythonで書き直してみるだけでもかなりの勉強になるはず
    • Python によるアルゴリズム https://qiita.com/cabernet_rock/items/cdd12b07d213b67d0530
  • 遅延型方程式に対するコメント追加
  • matplotlib のチュートリアルを読もうの会
    • 公式情報に触れる重要性
    • 古い情報が古いと書いてあったりする:たとえば pylab
    • Gallery
      • 見ていて面白い
      • 「どこをいじるとどう変わるか」が視覚的にわかる
      • 公式情報なのできちんとアップデートしてくれている(はず)
      • 公式情報にソースがあるので自分でいろいろ書き換えていて破滅したとき、必ずオリジナルを復元できる

Matplotlib

  • とりあえず本当に簡単な図を描く
  • 今回は有限フーリエ級数

\begin{align}

f(x)

\frac{4}{\pi} \left( \sin x + \frac{1}{3} \sin 3 x + \frac{1}{5} \sin 5 x + \cdots \right)
\end{align}

  • ついでなのでこれの TeX も紹介する
import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-3, 3, 1001)
y = (4 / np.pi) * (np.sin(x) + np.sin(3*x) / 3 + np.sin(5*x) / 5 + np.sin(7*x) / 7 + np.sin(9*x) / 9)
y1 = np.ones(len(x))
y2 = -1 * np.ones(len(x))

plt.plot(x, y, label="finite fourier")
plt.plot(x, y1, label="y=1")
plt.plot(x, y2, label="y=-1")

plt.grid()
plt.legend()
##plt.axes().set_aspect('equal', 'datalim') # アスペクト比を合わせる
plt.show()
png

TeX の記録

  • コンパクト多様体上のラプラシアンの固有値の漸近評価

\begin{align}

\lambda_k

4 \pi \left(\frac{\Gamma (\frac{m}{2} + 1)}{\binom{m}{p} \mathrm{vol}(M)} \right) k^{m/2} + o (k^{m/2}).
\end{align}

競プロ、AtCoder

ABC085C – Otoshidama

日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が $N$ 枚入っていて、合計で $Y$ 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「
10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

入力・出力例 1

## 入力
9 45000
## 出力
4 0 5

お年玉袋に 10000 円札 4 枚と 1000 円札 5 枚が入っていれば、合計枚数が 9 枚、合計金額が 45000 円になります。
5000 円札 9 枚という可能性も考えられるため、0 9 0 も正しい出力です。

入出力例 2

不適格な場合の出力チェックにあたる。

## 入力
20 196000
## 出力
-1 -1 -1

合計枚数が 20 枚の場合、すべてが 10000 円札であれば合計金額は 200000 円になり、そうでなければ 195000 円以下になるため、196000 円という合計金額はありえません。

入出力例 4

変なアルゴリズムを組むと指定計算時間内に終わらない。

## 入力
2000 20000000
## 出力例 
2000 0 0

基本方針

  • 全探索をするしかないが一ひねりして計算量(ループの数)を減らす
  • 合計 $Y$ 円が嘘かどうかであり、「何枚以下だったかもしれない」みたいな条件は付いていない
## N, Y = map(int, input().split())
def solve(N, Y):
    for x in range(N+1):
        for y in range(N-x+1):
            z = N-x-y # z のループはせずにこれで固定
            if 0 <= z <= 2000 and 10000*x+5000*y+1000*z == Y:
                return "%s %s %s" % (x, y, z)
                exit() # ヒットしたので処理終了
    # ここまで来たら不適格だったと判断
    return "-1 -1 -1"

print(solve(9, 45000)) # 4 0 5
print(solve(20, 196000)) # -1 -1 -1
print(solve(1000, 1234000)) # 14 27 959 他にもありうるはず
print(solve(2000, 20000000)) # 2000 0 0
0 9 0
-1 -1 -1
2 54 944
2000 0 0

ABC049C – 白昼夢

英小文字からなる文字列 $S$ が与えられます。 $T$ が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで $S=T$ とすることができるか判定してください。

$T$ の末尾に dream dreamer erase eraser のいずれかを追加する。

## 入力例 1
erasedream
## 出力例 1 
YES

erase dream の順で T の末尾に追加することで S = T とすることができます。

## 入力例 2
dreameraser
## 出力例 2 
YES
## 入力例 3
dreamerer
## 出力例 3
NO
import re
##S = input()
def solve(S):
    # 正規表現を使って特定 4 文字列の繰り返しだけかどうかを判定する
    return "YES" if re.match("^(dream|dreamer|erase|eraser)+$", S) else "NO"

print(solve("erasedream")) # YES
print(solve("dreameraser")) # YES
print(solve("dreamerer")) # NO
YES
YES
NO

メモ

  • 正規表現マッチの速度:そんなに速いか?
    • 正規表現自体をいろいろ調べないといけない
    • ケースバイケースでの実測
  • 公式の解説:後ろから文字列マッチしていく

文字列 S を dream, dreamer, erase, eraser に分解していくことを考えます。先頭から分解していこうとす
ると、例えば dreamer まで読んだとき、dream で切るべきなのか、dreamer で切るべきなのか判定するこ
とができません。(dreameraser は dream eraser と切らなければならないので、dreamer まで読んだときに
dream で切らなければいけない場合が存在することが分かります)
逆に、後ろから読んでみましょう。4 つの単語を後ろから読むと、それぞれ maerd, remaerd, esare, resare
となります。この 4 つの文字列は、ある文字列が他の文字列の接頭辞 (prefix) になっていないため、後ろか
ら読んで当てはまるものが見つかれば即座に分解するしかありません。(参考: 語頭符号) S を最終的に分解す
ることができなかった場合 NO を、そうでない場合 YES を出力します。

  • 後ろからのマッチ:今の場合の文字列設定だからできることではある
    • むしろ問題ごとにその勘所を見抜いて問題ごとに適切な手法を見つけて実装する

IT 基礎知識

  • 東大の AWS クラウド講義資料を眺めてみてください。せっかくなので状況を見て(私の勉強も兼ねて)「勉強会前半パート」で取り上げようと思います。
    • これはこれで眺めると大事な用語・概念・操作などがわかる
    • ハードル高そうなのでとりあえず保留
  • 応用情報技術者試験の本を使って浅く広く眺めてみる
    • 根本的にそういう試験
    • 横のつながりを見つつ浅く広く知る

7 章 ネットワーク

  • OSI基本参照モデル、TCP/IP、MACアドレスあたりの話と他のところの関係
  • OSI 基本参照モデル
    • 上の方が「アプリケーション」
    • 下の方はハードウェア
  • 例えばセキュリティの話をしているとポンと出てくる
    • 「下の方(ハードウェア)」レベルでやった方が処理が速いが、複雑なことはできない
      • 高負荷のシステムで手早く最低限の前処理だけしたい場合に有効
      • 複雑なことをしない(できない)からこそ速い
    • 「上の方(ソフトウェア)」レベルでやると処理は遅いが、複雑な処理ができる
      • システムに多少負荷をかけてもいいから、セキュリティを高めたい
      • 複雑な処理・計算が必要なのでその分時間がかかる

OSI参照モデルとは|ファイアウォールの種類をわかりやすく解説

  • レイヤー1:物理層 階層の1段階目は「物理層」です。ハードウェアに最も近い部分であり、電気信号やアナログ信号などによる通信を行っています。主にLANケーブルなどの回線を使って通信を行っています。カプセル化されたデータの単位は「ビット」です。
  • レイヤー2:データリンク層 階層の2段階目は「データリンク層」です。同一ネットワーク上での通信を行う階層で、直接的に接続された通信のための規定です。この通信規定により、LANやWANの間の通信を実現できます。カプセル化されたデータの単位は「フレーム」です。
  • レイヤー3:ネットワーク層 インターネットでの通信を実現するものが、第3階層である「ネットワーク層」です。この階層ではネットワーク間の通信に関する取り決めが行われています。主にIPアドレスが使われ、ルータによって通信が管理されている階層です。カプセル化されたデータの単位は「パケット」であり、この階層からファイアウォールで通信を制御しています。
    • 遥か昔、「ケータイ」のころのパケット通信料は名前が同じだけで本質的には関係ない模様

セキュリティ

  • パケットフィルタリング:レイヤー3・4で動作 パケットフィルタリング型のファイアウォールは「ネットワーク層」「トランスポート層」で動作します。
    • レイヤー3の情報である「送信元IPアドレス」「宛先IPアドレス」をもとに判断することが可能です。このタイプのファイアウォールは構成がシンプルで、ほかの種類よりも処理が速いという特徴があります。
    • しかし、安全性はほかの種類よりも低く、フィルタリングの設定が煩雑になることがデメリットです。
  • サーキットゲートウェイ:レイヤー5で動作 セッション層で動作するファイアウォールが「サーキットゲートウェイ型」という種類です。
    • 先程のパケットフィルタリングの動作に加え、ポート指定や制御ができます。使用するアプリケーションごとに細かく通信の制御を設定することが可能です。
  • アプリケーションレベルゲートウェイ:レイヤー5・6・7で動作
    • 比較的新しいタイプのファイアウォールが「アプリケーションレベルゲートウェイ」です。
    • 主にレイヤー5から7までで動作を行い、アプリケーションレベルのデータをもとに通信を判断します。細かい単位で通信を判断するため、高度な識別が可能です。従来のファイアウォールよりも通信速度が少し落ちますが、なりすましなどの対策ができます。

もう 1 つ参考:ネットワーク各レイヤーのセキュリティを強化するには

  • トランスポートモード:パケットのペイロードだけを暗号化し、それにIPヘッダを付けて開いて送信する。
  • トンネルモード:IPヘッダを含めて暗号化されるため、ネットワーク間の安全な接続に用いられる。
  • 「SSL」「TLS」「SSH」といった第4層の通信プロトコルを使用すると、データを暗号化することによって傍受などから守ることが可能になる(「SSL」は「セキュア・ソケッツ・レイヤー」、「TLS」は「トランスポート・レイヤー・セキュリティ」、「SSH」は「セキュア・シェル」の略)。特に機器をリモートで管理するためにネットワーク接続を行う際に十分考慮に入れるべきものである。
  • SSL:https の s
  • SSH:Linux サーバーにログインするときによく使う。東大のクラウド講義資料でも「SSH で云々」というのがよく出てくる
  • こういう感じで横断的にいろいろ出てくる

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

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

関連記事

  • コメント (0)

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

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

このサイトについて

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

YouTube チャンネル登録

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

メルマガ登録

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

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

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