2020-09-20_hw オンライン プログラミング勉強会の記録

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

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

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


目次

進捗メモ

  • 今回は 03-02 からはじめ、03-03 の「sympy による偏導関数の実装」まで
  • 次回は「高階の偏導関数」から

プログラミング勉強会

  • 2020-09-06:線型代数、02_03 の固有ベクトルの計算その 1 まで
  • 2020-09-13:02_03 固有値・固有ベクトルの計算その 2 から 03_02 の「具体例:関数 $f(x)=3x^2+4x-5$ の $x=1$ での接線」、「sympy による接線の描画」まで

統計学・機械学習勉強会

理系のための語学・リベラルアーツ

課題

TODO

自分用メモ

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

Matplotlib

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

m,l = 0,3
phi = np.linspace(0, np.pi, 101)
theta = np.linspace(0, 2 * np.pi, 151)
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}

i \hbar \frac{\partial}{\partial t} \left| \psi \right\rangle

\hat{H} \left| \psi \right\rangle
\end{align}

競プロ、AtCoder

素因数分解の利用オイラー関数

正の整数 $N$ が与えられたとき $1,2,\dots,N$ のうち $N$ と互いに素であるものの個数を $\phi(N)$ と表します。これをオイラー関数とよびます。

問題

正の整数 $N$ が与えられる。$1,2,\dots,N$ のうち、$N$ と互いに素であるものの個数を求めよ。

(数値例)

・$N=12$

答え: 4

$1,2,3,4,5,6,7,8,9,10,11,12$ のうち、$12$ と互いに素であるものは、$1,5,7,11$ の $4$ 個です。

オイラー関数のポイント

  • 素因数分解 $N = p_1^{e_1}p_2^{e_2} \cdots p_K^{e_K}$ に対してオイラー関数は次のように書ける。

\begin{align}

\phi(N)

N (1 − 1/p_1)(1 − 1 / p_2) \cdots (1 − 1 / p_K)

N \prod_{i=1}^K \left(1 – \frac{1}{p_i} \right).
\end{align}

コードメモ

# http://www.tohoho-web.com/python/operators.html
# 切り捨て割り算 //
print(15 // 2) # 7
print(15 / 2)  # 7.5
print("-----")
print(7 // 3) # 2
print(7 / 3)  # 2.3333333333333335
7
7.5
-----
2
2.3333333333333335

コードの参考

def solve(n):
    # p はオイラー関数の結果をためていく変数
    p = n
    sqrt_n = n ** 0.5
    d = 2

    # いつも通り √n まで計算
    while d <= sqrt_n:
        # 割り切れるときに処理
        if n%d == 0:
            # (d-1) // d は (1 - 1/d) のこと
            p = p * (d - 1) // d
            # 互いに素な数だけ引っ張りたいので、因数に持っていたら割れるだけ割ってしまう
            while n % d == 0: n //= d
        # 一通り計算したら d を増やす
        d += 1
    # n が素数なら n > 1, True で 1 になる
    # n が合成数なら n = 1, False で 0 になる
    lst = [p, p * (n-1) // n]
    print(lst)
    return lst[n > 1]

print(solve(6)) # 2
print(solve(12)) # 4
print(solve(17)) # 16
print(solve(1000000)) # 400000
[3, 2]
2
[4, 0]
4
[17, 16]
16
[400000, 0]
400000

Project Euler も見てみよう

  • Problem3
  • GitHub の回答集
  • 中高生の数学・プログラミング学習用によかろうと思い、ちょこちょこやっている
https://projecteuler.net/problem=9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

N = 1001
for a in range(1, N):
    for b in range(a, N):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a,b,c)

200 * 375 * 425
200 375 425





31875000

IT 基礎知識

  • 応用情報の本を一日2ページくらい眺めてみてください。毎日やれば大体 1 年で読み終わります。

復習

OSI基本参照モデル

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

いろいろなプロトコル

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

本の記述を追いかける

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 ポイズニングのような攻撃手法もある

P.402 DNS クライアント(リゾルバ)の名前解決要求

コンテンツサーバへの問い合わせを繰り返すのは非効率なので,通常,自組織内にキャッシュサーバを置きます。この場合,リゾルバはキャッシュサーバに問い合わせを行い,キャッシュサーバ内に該当情報がキャッシュされていれば直接回答を得ることができます。ない場合は,キャッシュサーバが組織外のコンテンツサーバに問い合わせを行い,その結果をリゾルバに回答します。また,キャッシュサーバは,同様の問い合わせの際に再利用できるよう,問い合わせで得た結果を一定期間キャッシュします。

リゾルバからキャッシュサーバに送られる問い合わせを再帰的な問合せという。”再 帰 的”とは,「再び帰ってくる」という意味で,再帰的な問合せに対しては,最終的な結果を回答する必要がある。

  • 例えばディレクトリツリーを掘るタイプのプログラムではよくやる処理
  • (F# で)競プロをやっていると意外と再帰を使う(使える)ことに気づいた
    • いわゆる関数型言語は(命令型で)ループを使うところは高階関数か再帰で処理する
    • たいてい高階関数で足りる
    • 再帰は末尾再帰など面倒ポイントがある

P.402 インターネット上の電話サービスで用いるプロトコル

  • VoIP(Voice over Internet Protocol)
  • IPネットワークで音声をやり取りするための技術
  • データの伝送にはリアルタイム性に優れたUDPをベースとしたプロトコルが使われる
    • 届かなかったらもう一度しゃべらせればいい

P.403 その他のアプリケーション層プロトコル

  • FTP:ファイルを送る。ポートは 20、21
    • セキュリティが甘いので FTP、FTPS、SFTP、SCP などがある
  • Telnet:(あまり使ったことない)
  • SSH(Secure SHell):サーバーにログインするときに使う。とにかくよく使う。
    • テキストベースの通信であるTelnetに対し,暗号化や認証技術を利用して安全に遠隔操作するためのプロトコル
  • NTP・SNTP(Network Time Protocol):時刻合わせ
  • LDAP(Lightweight Directory Access Protocol):ディレクトリサービスにアクセスするためのプロトコル
    • Windows の ActiveDirectory も LDAP を使っている
    • 社員情報をやり取りするシステム間連携で出てくる

P.404 7.7 伝送技術

P.404 誤り制御

P.404 パリティチェック

  • 最もシンプルな検査方法
  • 7 ビットのデータを送信する場合,8 ビット目に誤り検出用のパリティビットを入れてデータの整合性を検査
    • 偶数パリティ:8ビットの各ビットについて“1”の数が偶数になるようにパリティビットを挿入する
    • 奇数パリティ:上で奇数にする
  • 有限体(ガロア体)$\mathbb{F}_2$ (ビット)で考えるといってもいい。
  • 微分形式で偶数次と偶数次・偶数次と奇数の積が偶数次になり、奇数次と奇数次の積がと奇数次になるのも一種のパリティチェック。
  • cf. P.405 水平垂直パリティチェック

P.404 CRC

  • CRC:巡回冗長検査(Cyclic Redundancy Check)
  • 送信するデータに生成多項式を適用して誤り検出用の冗長データを作成し,それを付けて送信
  • 受信側は送信側と同じ生成多項式で受信データを割り,同じ結果であればデータ誤りが
    ないと判断
  • CRCでは複雑な演算を使ってバースト誤り も検出できる
    • バースト誤り:データ転送回線上で連続して発生するビットの誤りのこと。ノイズの混入で生じることが多い。
  • HDLC 手順が採用

P.404 ハミング符号

  • 上で紹介した動画で簡単に数学的な原理を紹介している
  • 情報ビットに対して検査ビットをつけて 2 ビットまでの誤り検出と,1 ビットの誤り自動訂正機能をもつ誤り制御方式
    • 原理的には何ビットの誤り検出・自動訂正でもできる
  • 代数幾何符号もある
    • 数学的にはもちろん難しい
    • 有限体上の(非特異な射影)代数曲線を使う

P.406 同期制御

  • 通信時に送信側と受信側でタイミングを合わせる必要がある。
  • 本の話題とは別に同期・非同期にはいろいろな話があって難しい。
  • プログラミング、特に JavaScript フロントエンド周り。
  • データベースの同期・非同期
    • 大規模サービスでの問題、READ-WRITE、マスター・スレーブ
    • ふつう読み込みに比べて書き込みは少ない
    • 場合によっては読み込みは完全に最新の情報でなくてもいい
    • 書き込みメインのデータベースと、その内容を適当なタイミングでもらってくる読み込み専用のデータベースがある:これがマスターとスレーブ
    • 参考:前にやった Twitter のシステム構成など
    • 適当な意味で完全同期していないとまずいシステムもある:銀行・金融系
      • cf. トランザクション
      • トランザクションはふつう銀行が例になるくらい、そちらの話が有名でしかもイメージしやすい

P.408 7.8 交換方式

P.408 パケット交換方式

  • 回線交換方式と対になる概念
    • 回線交換方式:通信を行うノード間で物理的な通信路を確保してから通信する
    • 例:電話
  • パケット交換方式について
    • データ送信するノードはデータをパケットに区切る。
    • ひとつひとつのパケットにヘッダを付けて送信。
    • ネットワーク内ではパケット交換機にパケットがたまる
    • ネットワークの状況に応じて順次送られる

パケット通信のメリット・デメリット

メリット
  • 耐障害性
    • 通信路を固定しないため,迂回経路が取れる。
    • パケット交換機にデータが蓄積されているため,復旧まで待てる。
  • パケット多重
    • 1 対 1 の通信で回線を占有する必要がないため,1つの回線を多くのノードで共有でき,回線を効率的につかえる
  • 異機種間接続性
    • パケット交換機で中継するときにプロトコル変換・速度変換でエンドノードどうしが同じプロトコルをサポートしていなくても通信できる
デメリット
  • ネットワーク内の蓄積交換処理による遅延
    • 蓄積交換処理による遅延解消のために主に回線の帯域を広げることで対応してきた
    • 構造上,完全には遅延をなくせない
  • パケット到着順序の不整合

P.408 ATM 交換方式

  • ATM(Asynchronous Transfer Mode:非同期転送モード)
  • 遅延のない回線交換方式とパケット交換方式の利点を得たい
  • パケット交換方式の発展
  • 遅延の原因をつぶす:特にパケットの多様性
    • 多種多様なパケットに対応するために,パケット交換機はソフトウェア処理が必要
    • ATM での工夫の一例:最も特徴的なのは,パケット(ATMではセルという)の長さをヘッダ部 5 バイト,ペイロード 48 バイトの53バイトに統一
    • パケット解析がハードウェアだけでできる。
    • ソフトウェアは不要になった。
  • Wikipedia から
    • 当初の意図に反して非常に複雑な技術になってしまった
    • ATM は次世代の主流にならず限定的な使用にとどまった
    • ATM の設計思想は MPLS へと引き継がれた
    • 汎用のレイヤ 2 のパケットスイッチングのプロトコルとして、ルーターを介したIPの通信網で利用されている。

P.408 ペイロード(payload)

  • データ通信で本来転送したいデータ本体の部分、ボディを指す。
  • ATM ではペイロードのサイズを固定して処理を簡素化
  • 難点:パケット全体に占めるペイロードのサイズが相対的に小さくオーバヘッドが大きい

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

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

関連記事

  • コメント (0)

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

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

このサイトについて

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

YouTube チャンネル登録

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

メルマガ登録

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

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

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