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

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

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

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


コンテンツ修正メモ

  • 平面内で回転している様子を表すコードを書く: $R(\theta)$ を定義して関数化する.
  • 矢印を書くときに何を描いているか, 式もきちんと書く.
  • 遊ぶ例についてコメントを残す.

途中で見せたページ・動画

競プロ、AtCoder

IT 基礎知識編

数学・プログラミング

quiver について

課題

TODO

自分用メモ

  • 遅延型方程式に対するコメント追加
  • matplotlib のチュートリアルを読もうの会
    • 公式情報に触れる重要性
    • 古い情報が古いと書いてあったりする:たとえば pylab
    • Gallery
      • 見ていて面白い
      • 「どこをいじるとどう変わるか」が視覚的にわかる
      • 公式情報なのできちんとアップデートしてくれている(はず)
      • 公式情報にソースがあるので自分でいろいろ書き換えていて破滅したとき、必ずオリジナルを復元できる

Matplotlib

  • 本当に簡単な図を描く
  • これを参考に scipy お絵描き
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import sph_harm

m,l = 0,1
phi = np.linspace(0, np.pi, 31)
theta = np.linspace(0, 2 * np.pi, 46)
phi, theta = np.meshgrid(phi, theta)

r = sph_harm(m, l, theta, phi).real
x = np.abs(r) * np.sin(phi) * np.cos(theta)
y = np.abs(r) * np.sin(phi) * np.sin(theta)
z = np.abs(r) * np.cos(phi)

fig = plt.figure(figsize=(8, 8))
ax = fig.gca(projection="3d")
ax.plot_surface(x, y, z, color="aqua", edgecolor="k")
plt.axis("off")
plt.show()
png

TeX の記録

\begin{align}
Y^m_k(\theta, \phi)
&=
(-1)^{(m+ |m|)/2} \sqrt{\frac{2k+1}{4 \pi} \frac{(k-|m|)!}{((k+|m|)!}} P^{|n|}k (\cos \theta) e^{im\phi}, \ P^{m}_k (t) &= \frac{1}{2^k} (1-t^2)^{m/2} \sum{j=0}^{\lfloor (k-m)/2 \rfloor} \frac{(-1)^j (2k-2j)!}{j!(k-j)!(k-2j-m)!} t^{k-2j-m}.
\end{align}

競プロ、AtCoder

素因数分解の利用約数の個数

整数 $N$ が与えられます。 $N!$ の正の約数の個数を $10^9+7$ で割った余りを求めてください。

約数の個数のポイント

  • $N= \prod_{k=1}^K p^{e_k}$ と素因数分解できるとき、約数の個数は $(e_1+1)(e_2+1)…(e_K+1)$ 個
    • 具体例で計算すればわかる
  • 約数の個数を求めるだけなら素因数分解はオーバーキル:約数列挙で十分
  • 素因数分解で考えるメリット:約数に関する考察がしやすい

コードの参考

#N=int(input())
from collections import defaultdict
from functools import reduce

# 前回の素因数分解とだいたい同じ
def solve(n):
    p = defaultdict(int)

    # クロージャー:上の p にアクセスしてそこに結果をためる
    def inner(n):
        sqrt_n = int(n ** 0.5)
        for i in range(2, sqrt_n + 1):
            x = 0
            while n % i == 0:
                n //= i
                x += 1
            if x:
                p[i] += x
        if n > 1:
            p[n] += 1

    for i in range(2, n+1):
        inner(i)

    # 関数型でいう fold
    print(reduce(lambda x, y: x * (y+1), p.values(), 1) % (10**9 + 7))

solve(3) # 4: 3! = 6 で 6 の約数は 1, 2, 3, 6 の 4 つ
solve(6) # 30: 6! = 720, 約数は 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360, 720
solve(1000) # 972926972
4
30
972926972

Project Euler も見てみよう

  • GitHub の回答ページ
  • 中高生の数学・プログラミング学習用によかろうと思い、ちょこちょこやっている $a$
  • F#, Julia の |> を説明する
    • Twitter (私の TL)でも話題になった $f(x)$ か $xf$, $x^f$ か
    • F# や Julia の標準も $f(x)$ 型だが、$xf$ と書くための機構がある
    • Unix のパイプラインと同じ:データがあって、それをコマンドで順に整形していくワンライナーのイメージ
    • この感覚が育っていると実に自然な記法
    • 書いていて楽しい

IT 基礎知識

  • 応用情報の本を一日2ページくらい眺めてみてください。毎日やれば大体 1 年で読み終わります。
    • 次回対応予定:7.4 ネットワーク層のプロトコルと技術

復習

OSI基本参照モデル

  • 会社の部署と同じ気分
  • 特定層は自分のところにしか責任を持たない
  • 「他の層は他の層で専門的に管轄してね」
  • お互い全くの無関係ではないが、基本的には自分のことだけ考えていればいい。

いろいろなプロトコル

  • IP, HTTP, SMTP, POP, ARP…
  • 通信の規格
  • 状況に応じて適切なプロトコルを選ぶ
  • ヘッダ・ボディーの概念

本の記述を追いかける

P.392 IPv6

  • IP アドレスの枯渇
  • IPv4 でも「特殊なIPアドレス」などグローバル・ローカルを分けたりして枯渇対策はしてきた。
  • 「端末」が世にあふれてきて、アドレスが足りなくなってきた
    • 原理的に「IPアドレスは32けたの2進数」としているので、これ以上増やせない
      • IPはよく「インターネット上の住所」に例えられるが、市町村合併で起きる実際の住所変更のように柔軟に変えられるわけではない
        • 実際の住所にしても行政関係はもちろん、郵便や運送業などのシステムのレベルでは修正や対応が必要
    • 既存の機器・プログラムはこの前提で動いていて、勝手に変えられないし、仮に変えられるとしても膨大な手間になる
    • 新たな仕様を作り、それで世界全体に持っていく
    • 少なくとも既存の欠点はつぶしておく必要があるし、しばらく枯渇しないようにしたい

P.392 IPv6 の特徴

  • 家電などへもIP アドレスを採番できるようになった。
  • アドレス空間が32ビットから128ビットに拡張
  • ルーティングに不要なフィールドを拡張ヘッダに分離
    • 基本ヘッダを簡素かつ固定長:固定長のご利益はあとで
    • ルータなどの負荷を軽減
  • IPレベルのセキュリティ機能IPsecに標準対応
    • IPSec
    • 暗号技術で IP パケット単位で改竄検知や秘匿機能を提供するプロトコル
    • 暗号化をサポートしていないトランスポート層やアプリケーションでも通信路の途中での盗聴や改ざんを防止できる。
  • IPアドレスの自動設定機能の組み込み
    • DHCP を使わなくてもよくなる
  • 特定グループのうち経路上最も近いノード,あるいは最適なノードにデータを送信するエニーキャストの追加
    • エニーキャスト
      • ルーティングトポロジーから見てデータを「最も近い」または「最もよい」あて先に送信するネットワークのアドレッシング/ルーティング手法である(anycast―どこかに送信)。
固定長レコードのメリット・デメリット
  • 対義語は可変長レコード
  • 固定長レコード
    • 全てが桁数で決まる
      • メリットであり、デメリットでもある
      • 参考
      • すべてのデータの長さが同じ
      • わざわざ「何文字で終わりか」と考える必要がなくなる
      • データベースにもプログラム(変数の型)にもある:「何文字までを許すデータ型」
  • デメリット
ホップ・リミット
  • パケットの生存時間(通過可能なルータの最大数)
  • なぜこれが必要か?
    • プログラム(アルゴリズム)によってネットワークをたどって目的地に行くために起こる問題
    • 何か・どこかがおかしくて、ネットワークのある一部をループしてしまうかもしれない
      • ループを抜け出すような処理を書くよりはそのパケットを捨てて再送させた方が楽
      • いつ捨てるか:パケットの寿命・生存時間
    • 辿ろうと思っていたネットワークが急な瞬断・故障などで辿れなくなった
      • 適切なところまで戻ってから新たなルートを探す必要がある
      • 計算時間・ネットワーク上での情報の移動時間がかかり、その分帯域も占有し圧迫する
      • そのパケットは捨てた方が早いかもしれない

P.394 アドレス変換技術

インターネットに接続するノードには,IPアドレスが割り当てられている必要があります。しかし,各組織に1つのIPアドレスがあれば,IPアドレスを割り当てられていないノードからもインターネットに接続できるといった技術があります。

  • ルーターやグローバル IP・ローカル IP の発想でもある

P.395 ICMP を利用した ping

  • ネットワークの疎通確認でよく使う
    • 「ネットがつながらない」
    • 「どこまでつながるか、ping 打って試してみて」
  • 疎通
    • 意思疎通の疎通だが、ここではネットワーク用語
  • 参考:疎通確認でよくやること
    • ルーターにつながるか、ルーターの IP を打ってみて確認
      • つながらなければマシンの設定がおかしい可能性がある
      • マシンの無線 Wi-Fi 送受信のハードウェアが壊れている
      • ルーターが死んでいる(壊れた・停電後に電源が落ちたまま)など
    • 適当な DNS につながるか、DNS の IP を打ってみて確認
      • 何らかの理由でルーターから出られていない?
      • DNS が死んでいる?
  • こういう感じの状況切り分けでよく使う
    • 状況切り分けという手法自体、アルゴリズムの二分探索にも近い発想で、プログラミングそれ自体にも非常に重要。
  • 他にもいろいろな応用がある
    • パソコンサポートでの一幕
    • 「パソコンがつかない」
    • 「コンセントは繋いでいますか?」
      • 直接聞くと怒るタイプの社会性が高い人もいる
      • 「まずは電源を差し込んでみてください」

P.395 COLUMN

  • これらのコマンドはたまに使う:ifconfig, netstat, nslookup
  • 覚えなくてもいい:そういうコマンドがあることを知っているだけでも全然違う

P.396 7.5 トランスポート層のプロトコル

P.396 7.5.1 TCP と UDP

  • トランスポート層は IP を補完し、データ送信の品質・信頼性を上げる
  • プロトコルは TCP・UDP

P.396 TCP

  • IP はデータ通信の安全性を保障しないコネクションレス型通信
  • IP の補完のために送達管理・伝送管理の機能を持つコネクション型プロトコル
  • 特に HTTP や FTP のような全て確実に伝わってほしいリクエスト・レスポンスに使われる
  • 参考:一部が落ちてもいいリクエスト・レスポンス
    • 動画:一部が抜け落ちてもそれほど問題なく、かつ大容量で帯域を圧迫するので再送も控えたい

P.397 TCP でのコネクションの確立

  • 3 ウェイハンドシェイク
    • クライアント→サーバー:コネクションの確立要求、SYN(synchronize packet)
    • サーバー→クライアント:上記への ACK(acknowledgement packet)・SYN
    • クライアント→サーバー:上記への ACK
  • TCP コネクションは, あて先 IP アドレス, あて先 TCP ポート番号, 送信元 IP アドレス, 送信元 TCP ポート番号の 4 つによって識別される.

ポート・ポート番号

ポートとは、ネットワークでデータを通信するための扉のようなものだと思うとわかりやすいだろう。ポート番号はその扉の番号だ。

それぞれプログラムの種類によって、使うポート(扉)が違う。例えば、メールを送るにはこの扉、メールを受け取るにはこの扉、Webページを見てもらうのはこの扉、などと決まっているわけだ。

実際TCPやUDPで通信を行うときは、コンピュータ一台という単位ではなく「プログラム単位」つまり「プロセスやスレッド単位」で通信が行われる。そのためプロセス同士、正しく受け渡しをする必要がある。

  • プロセス・スレッドなどいきなりかなり低レイヤーの話がでてくることに注意。

このとき通信しているプロセスには「ポート番号」というものが割り振られる。プロセスやスレッドはこのポート番号を目印にして、どのアプリケーションとどのアプリケーションが通信をとっているのかを判別することになる。

IPアドレスを建物の住所に例えるなら、ポート番号は「部屋の番号は何号室か?」という例えになる。コンピュータネットワークにおいて、プロトコル、IPアドレスとポート番号はまとめると、「どのような方法」で「どこ」の「何号室」に通信をとるのか?という形にいいかえることが出来る。

通信において重要なポート番号だがポートを開くということは、特定の部屋の扉をあけはなっている状態に等しいので、サービスを提供するサーバでもないかぎり、基本的に不必要なポートは開かないように設定しておかなければならない。

  • サーバーのセキュリティなども絡むが分かる。

代表的なポート番号とプロトコル
それぞれ「どの様なプロトコルがどの様なポート番号で運用されるのか?」代表的な例をあげると以下のようになる。

  • TCP 20 : FTP (データ)
  • TCP 21 : FTP (制御)
  • TCP 22 : SSH
  • TCP 23 : Telnet
  • TCP 25 : SMTP
  • UDP 53 : DNS
  • UDP 67 : DHCP(サーバ)
  • UDP 68 : DHCP(クライアント)
  • TCP 80 : HTTP
  • TCP 110 : POP3
  • UDP 123 : NTP
  • TCP 443 : HTTPS
  • WELL KNOWN PORT NUMBERS 0~1023
  • MySQL: 3306

P.397 アプリケーション間の通信

  • トランスポート層にはアプリケーション間の通信の実現という役割がある
  • 各アプリケーションはトランスポート層のヘッダにあるポート番号をみて自分宛のデータか判断する。

P.398 7.6 アプリケーション層のプロトコル

P.398 7.6.1 メール関連

P.398 メールプロトコル

  • 送信転送する SMTP (Simple Mail Transfer Protocol)
  • メールを受け取る POP3 (Post Office Protocol 3)
  • IMAP (Internet Message Access Protocol)

補足:POP と IMAP

  • (気分的には)管理する主体が違う
  • POP は単純にサーバーからメールデータを取ってくる
    • 取ってきたらサーバーからデータが消える
    • そのあとは自分で管理する
  • IMAP の説明の参考
    • 郵便にたとえると、(実際にはできませんが)郵便局から手紙は受け取らずコピーをもらってくるような形になり、手紙は郵便局が保管することになります。
    • メールはサーバに保管されますので、既読・未読・削除、フォルダの分類といった管理は、すべてサーバ上で行われます。
    • いろいろな端末でメールが見られる
  • POP と IMAP のメリット・デメリット
    • POP
      • メリット
        • PC などの端末にメールが保存される
        • 端末が許す限りメールを保存できる
        • 端末に保存されたメールはネット接続なしで見られる
      • デメリット
        • 落としてきた端末でしたメールが見られない
        • サーバーに一定期間メールを残す設定で複数端末でメールを見ることもできるが、未読・既読・削除などの状態が反映されない
    • IMAP:サーバー上でメール管理
      • メリット
        • 未読・既読などの状態が共有できる
        • サーバー上で一元管理できる。
      • デメリット
        • メールの閲覧・状態修正のためにサーバーと通信する必要がある
        • サーバーの容量の上限に達するとメールからサーバーを削除する必要がある

Gmail と IMAP

  • (何となくの理解しかないので間違っているかもしれない)
  • Web インターフェースからの Gmail 利用と Thunderbird などのアプリからの利用で事情が違う
  • POP や IMAP が関係してくるのはアプリからの利用
  • アプリを使う場合はふつう IMAP を使う
  • IMAP にしないと他の端末、もっといえば Web インターフェースからも見られなくなる(はず)
  • 会社で特定端末からしかメールを見ないなら POP でもいいかもしれない。
    • マシンが変わるとき、メールデータも引越ししないと昔のメールが掘れない
    • 会社のメールサーバー管理問題・容量問題などはかなり大変
    • 一頃「Gmail でサーバー管理問題を解決して、IT 部門が攻めの IT を提案できるようになった」みたいな記事も出ていた
    • メールが止まると直接的にビジネスに被害が出る
    • 何にせよサーバー管理は大変なので

P.398 メール受信プロトコル、メール関連のプロトコル・規格

  • 昔のプロトコルはセキュリティ関連の仕様がなかった
  • SMTP-AUTH, SMTP over TLS/SSL など

P.399 Web 関連

  • HTTP: HTTP(Hyper Text Transfer Protocol)は WebサーバとWebクライアント(ブラウザ)間でHTMLなどのWeb情報の配信 に使うプロトコル
    • セキュリティ:HTTP に SSL/TLS の認証機能や通信の暗号化を実装した HTTPS が登場
  • SOAP: XML を使ってデータ構造を記述
    • 最近あまり見かけない印象
    • XML 自体もうあまり使わない
    • 最近は JSON や GQL をよく見かける

P.401 DNS(Domain Name System)

  • TCP/IPでは,各ノードに対して一意なIPアドレスが割り当てられている
  • IPアドレスは覚えにくい
  • IP アドレスと対応する別名であるドメイン名がつけた
  • ドメインと IP を対応させるサービスが DNS
  • 原理的には世界中のすべてのノードのドメイン名とIPアドレスの対応関係を知ってい なければならない
    • 事実上不可能
    • DNSの規約では変換表作成の負担を細分化して,DNSを分散データベースとすることで対応しています。
  • DNS ルートサーバー
  • DNS ポイズニングのような攻撃手法もある

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

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

関連記事

  • コメント (0)

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

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

このサイトについて

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

YouTube チャンネル登録

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

メルマガ登録

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

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

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