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

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

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

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


目次

進捗メモ

プログラミング勉強会

  • 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,2
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

TODO TeX の記録

競プロ、AtCoder

素因数分解の利用約数の総和

問題文
高橋君は完全なものが大好きです。
自然数には、完全数というものがあります。 完全数というのは、自分以外の約数の総和が自分と等しくなる自然数のことです。 例えば $6$ の場合 $1+2+3=6$ となるので完全数です。 それに対して、自分以外の約数の総和が自分より小さくなる場合は不足数と言い、大きくなる場合は過剰数と言います。
高橋君には今気になっている自然数があります。高橋君のために、それが完全数なのか不足数なのか過剰数なのか判定してください。

約数の総和のポイント

  • 約数を列挙して足せばいい
  • 「約数の個数」を求めたときの考え方を少し改変するだけで求められる
  • $N= \prod_{k=1}^K p^{e_k}$ と素因数分解できるとき、約数の総和は次のように書ける。

\begin{align}
\left( \sum_{k=0}^{e_1} p_1^{k} \right)
\cdot
\left( \sum_{k=0}^{e_2} p_2^{k} \right)
\cdots

\left( \sum_{k=0}^{e_K} p_K^{k} \right)

\prod_{l=1}^K \left( \sum_{k=0}^{e_K} p_l^{k} \right).
\end{align}

  • 単に約数の総和を求めるだけなら普通に約数列挙した方が楽

コードの参考

# n = int(input())
def solve(n):
    sqrt_n = int(n ** 0.5)
    ans = 0

    for i in range(1, sqrt_n + 1):
        if n % i == 0:
            # 完全数は定義によって自分以外の約数の和を見るので、平方数の場合は約数だけを取る
            if i**2 == n:
                ans += i
                # ans = ans + i
            else:
                # ループで sqrt_n までしか見ないので、sqrt_n 以上の値になるペアも足し込む
                # 例:n = 8 で、sqrt_n + 1 = 3, i = 2 に対して n // i = 4
                ans += i + n // i

    if ans > n*2:
        print("Abundant")
    elif ans < n*2:
        print("Deficient")
    else:
        print("Perfect")

solve(6) # Perfect
solve(24) # Abundant
solve(27) # Deficient
solve(945) # Abundant
Perfect
Abundant
Deficient
Abundant

Project Euler も見てみよう

IT 基礎知識

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

復習

OSI基本参照モデル

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

いろいろなプロトコル

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

本の記述を追いかける

P.393 ホップ・リミット
  • パケットの生存時間(通過可能なルータの最大数)
  • なぜこれが必要か?
    • プログラム(アルゴリズム)によってネットワークをたどって目的地に行くために起こる問題
    • 何か・どこかがおかしくて、ネットワークのある一部をループしてしまうかもしれない
      • ループを抜け出すような処理を書くよりはそのパケットを捨てて再送させた方が楽
      • いつ捨てるか:パケットの寿命・生存時間
    • 辿ろうと思っていたネットワークが急な瞬断・故障などで辿れなくなった
      • 適切なところまで戻ってから新たなルートを探す必要がある
      • 計算時間・ネットワーク上での情報の移動時間がかかり、その分帯域も占有し圧迫する
      • そのパケットは捨てた方が早いかもしれない

P.394 アドレス変換技術

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

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

P.395 ICMP を利用した ping

  • ネットワークの疎通確認でよく使う
    • 「ネットがつながらない」
    • 「どこまでつながるか、ping 打って試してみて」
  • 監視でも使われる:参考ページ、「PING 監視」とあるところ
    • せっかくなのでいくつかキーワードなどを盛り込む
    • PING 監視、TRAP 監視、RSH、SNMP、SOCKET 通信、POP・SMTP認証、PHN/PNSコマンド、2バイトのコマンド
    • インターフェースコンバータ
      • 「インタフェースコンバータ」は異なるインタフェースを相互に変換して接続する装置です。異なる規格の通信インタフェースを相互接続して、多種多様なシステムを構築することができます。
疎通とは
  • 意思疎通の疎通だが、ここではネットワーク用語
  • 参考:疎通確認でよくやること
    • ルーターにつながるか、ルーターの 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 ポイズニングのような攻撃手法もある

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. トランザクション
      • トランザクションはふつう銀行が例になるくらい、そちらの話が有名でしかもイメージしやすい

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

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

関連記事

  • コメント (0)

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

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

このサイトについて

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

YouTube チャンネル登録

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

メルマガ登録

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

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

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