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

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

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

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


2020-07-19 課題

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

自分用メモ

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

Matplotlib

  • とりあえず本当に簡単な図を描く
  • 今回は減衰振動

\begin{align}

x(t)

e^{-\gamma t} \sin \omega t.
\end{align}

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

x = np.linspace(0, 10, 501)
y = np.exp(-x) * np.sin(5*x)

plt.plot(x, y, label="dump wave")

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

TeX の記録

  • 熱核
  • まず名前が格好いい

\begin{align}

k(x,y,t)

t^{N – \frac{m}{2}} e^{-\frac{d^2(x,y)}{4t}} \mathcal{K}(x,y,t).
\end{align}

競プロ、AtCoder

ABC088B – Card Game for Two

$N$枚のカードがあります. $i$ 枚目のカードには, $a_i$ という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

2
3 1

最初, Alice は 3 が書かれたカードを取ります. 次に, Bob は 1 が書かれたカードを取ります. 得点差は 3 – 1 = 2 となります.

説明
  • 逆順(大きい順、sorted(lst, reverse=True)に並べる
  • 最初からお互いに取っていく
  • これで最適戦略になる
  • 相互の得点をどう計算するかも重要
##N = int(input())
##a = sorted(map(int, input().split()))[::-1]
def solve(lst):
    a = sorted(lst, reverse=True)
    print(a)
    return sum(a[::2]) - sum(a[1::2])

lst = [3, 1]
print(solve(lst)) # 2

lst = [2, 7, 4]
print(solve(lst)) # 5

lst = [20, 18, 2, 18] # 18
print(solve(lst))
[3, 1]
2
[7, 4, 2]
5
[20, 18, 18, 2]
18

ABC085B – Kagami Mochi

  • いわゆるハノイの塔:ただし同じ半径の円盤が複数枚ある

$X$ 段重ねの鏡餅 ($X \geq 1$) とは、$X$ 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい(一番下の餅を除く)もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。
ダックスフンドのルンルンは $N$ 枚の円形の餅を持っていて、そのうち $i$ 枚目の餅の直径は $d_i$ センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

解法
  • 重複をなくせば勝手に順序がつく
  • 餅の積み方や積む順序を聞かれているわけではない
  • 最大数しか聞かれていない
  • 余計な計算をしないことも重要:高速化
仮定
  • めんどいので実際の入力例とは違う入力を想定する。
  • 縦に並んだ数を最初からリストにする
  • 実際には次のように入力を取る必要がある
N = int(input())
d = [input() for i in range(N)]
  • これを次のように入力を取る
d = [1,2,3]
def solve(lst):
    return len(set(lst)) # set で重複をつぶす

lst = [10, 8, 8, 6]
print(solve(lst)) # 3

lst = [15, 15, 15]
print(solve(lst)) # 1

lst = [50, 30, 50, 100, 50, 80, 30]
print(solve(lst)) # 4
3
1
4

IT 基礎知識

  • SSD の話:記憶の仕方、書き込み耐性
  • HDD の最小単位

SSD の話

参考記事:SSDの寿命はどれくらい?SSDの寿命に関する情報(SSDの特徴・データ記憶媒体比較・故障予兆・故障症状・寿命延ばす対策)

  • HDDと比べてSSDは読み書き速度が速い
  • 使用環境によっては寿命が短くなってしまう
寿命
  • SSDの寿命を決める要素は3つ
    • 書き込み回数、空き容量、そして使用時間
  • SSD:基本的には半導体
    • NAND型フラッシュメモリ
      • メモリーカードやスマートフォンの記憶媒体と同じタイプのメモリ
    • 参考:HDD は磁気ディスク
  • データの上書きができない
    • 「データの空き容量に新しいデータを書き込み、前のデータを消去する」
    • これがSSDの寿命に大きく影響
  • SSDは書き込み回数が増えると、次第に劣化
    • ゴリゴリの物理の話なので省略:結論だけ受け入れる
  • 書き込み可能回数はデータの保持形式にも依存
    • TLC:低価格大容量SSDの場合
      • 1セルあたりの書き込み可能回数は1千回
      • TLC:Triple、1つのセルに電子3つ
        • 単電子制御というのは尋常ではない
    • 参考:SLC(シングルレベルセル、Single Level Cell)
      • 最も耐久性が高い
      • 1セルに電子が1つ:セルの中の電子の有無で01が記録
      • 1セルに1ビットしか記録できない:データ容量は少ない→高価
        • 10万回程度の書き込みに耐え、信頼性と速度は高くなる
  • 長い間使っていても SSD は劣化
SSD・HDD・eMMC
  • SSD(ソリッドステートドライブ)
    • NAND型メモリにデータを記録
    • 高速で読み書きできる、広く使われているフラッシュメモリ
    • 近年大容量化と低価格化
  • HDD(ハードディスクドライブ)
    • プラッタと呼ばれる円盤型の磁気記憶媒体に磁気ヘッドでデータを書き込み・読み出し
    • 構造上SSDに比べるとデータの読み書き速度が低速
    • 物理的に複雑な構造
      • SSDやeMMCにて比べて大型で重く、電源消費量が多い
      • 衝撃に弱い:物理的に針を使っているため
    • 大容量のデータを保持するのが得意で安価
      • 速度にあまり影響されない画像や動画のバックアップ用
  • eMMC(embedded Multi Media Card)
    • SSDと同様:フラッシュメモリを使用した記憶ストレージ
    • SSDと比較すると読み書きの速度は劣る
    • 消費電力は3つの記憶媒体の中で一番低い
    • SSDよりもさらに小型
    • スマートフォンやタブレットなどモバイル端末用
    • UMPC などにも詰まれている
SSDの寿命が近いときの症状とその対策
  • SSDの寿命が近づいてくるといくつかの予兆がパソコンに現れる
    • 処理速度が低下する
    • 作業時にフリーズする
    • SSDドライブが認識されない
    • エラーメッセージが表示される
    • ブルースクリーン画面(※)が表示される
  • 個人メモ:デスクトップでよくブルースクリーンが出るようになった。画面にはメモリエラーと出ていたが、SSD がまずいかもしれない。

HDD の書き込み最小単位

  • もともとの問題意識:なぜ最小単位があるのか?

セクタの話

  • 参考記事
  • セクタとは、ディスクに記録する最小記録単位の事です。
  • 512 セクタと 4K セクタ
  • 4K セクタのメリット:OSで扱える容量が格段に増える
    • 今までの【WindowsXP】では、512セクタのハードディスクの場合、2TBまでしか認識できない
    • 4Kセクタ対応ハードディスクを使うと大容量ハードディスクを認識できる
  • 2TBバイトまでの認識問題
    • 参考
    • 2TBの壁:OSやマザーボードの仕様で壁を超える容量の製品を使えない
      • 使えても壁を超える部分は認識しない
    • 詳細
      • MBRが管理できるセクタ数が4,294,967,296(約43億)
        • MBR:Master Boot Record
        • ハードディスクなどのストレージ(外部記憶装置)の最も先頭にある、起動に必要なプログラムや情報を記録した小さな領域。コンピュータの起動時に最初に読み込まれる。
      • 1セクタが512バイト 管理可能な容量は4,294,967,296 × 512 = 2,199,023,255,552(約2兆2000億)バイト
        • これが2TB

セクターとクラスター

  • クラスタとは
    • HDDなどのドライブにデータを記録して管理する際に使う最小の単位
  • 「クラスタ」より小さい「セクタ」という単位がある
    • クラスタは複数のセクタで作られる
  • HDD上ではセクター単位ではなくクラスター単位でデータを管理
  • なぜセクタではなくクラスタ単位でデータを管理するのか?
    • HDDの容量が以前に比べて大きくなったため
    • セクタのような小さな単位で読み書きをすると、時間がかかる
    • 効率悪化
    • 「1 ファイル」自体の容量も大きくなっている
    • クラスタで処理しても問題は小さいはず
  • クラスタのサイズは HDD 容量によって変わる
    • 同容量の HDD を使ってもクラスタのサイズが小さい方がデータを効率的に管理できる
    • HDD 内のデータの管理を行うファイルシステムがFATやNTFS
    • 大昔「ファイルをフォーマットします。Macなどでは使えなくなります」とか出てきた理由がこれ:ファイルシステムが違う形でフォーマットするから
    • 参考:実は危険??「exFATフォーマット」との付き合い方

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

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

関連記事

  • コメント (0)

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

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

このサイトについて

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

YouTube チャンネル登録

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

メルマガ登録

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

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

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