Skip to content

Instantly share code, notes, and snippets.

@uta8a

uta8a/out.txt Secret

Created September 3, 2019 19:48
Show Gist options
  • Save uta8a/5cfc3a1d2abc7963b24445820d2b26b2 to your computer and use it in GitHub Desktop.
Save uta8a/5cfc3a1d2abc7963b24445820d2b26b2 to your computer and use it in GitHub Desktop.
独学でやろうと思っていること、やっていること
# 卒業までに自学をしようと思っている範囲 (20190904)
!注意!
全部の本を読んだわけではないです。
# 動機
東大の理学部情報科学科卒相当のコンピュータ・サイエンス(以降CSと略す)の知識があれば、知識面で見ればそれほど困らないだろうという仮定、東大生はブログにやったことを書いてくれる(情報共有をしようという土壌がある)の2点から、理情のシラバス(https://www.is.s.u-tokyo.ac.jp/appli/curriculum.html)を見てみます。
概要
- 2年後期
情報数学
形式言語理論
計算機システム
ハードウェア構成法
アルゴリズムとデータ構造
情報科学基礎実験
- 3年前期
オペレーティングシステム
離散数学
情報論理
言語処理系論
情報科学演習1
計算機構成論
システムプログラミング実験
関数論理型プログラミング実験
ハードウェア実験
- 3年後期
...
# 2A
そこで、まずは2年後期をマスターしようと考えます。
https://www.is.s.u-tokyo.ac.jp/vu/vu_lesson.php 学生による紹介。内容のイメージが湧く
https://blog.knshnb.com/posts/graduation-is/ 理情のカリキュラムについてイメージが湧く
https://kammer0820.hatenablog.com/entry/2019/02/20/210146 2Aについて特に詳しく書かれています
以下のことを勉強すればよさそうです。
## 情報数学
> 代数系と暗号(情報理論)について。 前半が数学パートで、群、環、体周辺の定義/定理を爆速でまとめました。後半は暗号(情報理論)パートで、情報量・エントロピーから始まって具体的な暗号形式(RSA、ElGamal)、符号化や誤り訂正まで触りました。パリティ検査行列とか。前半と後半のつながりは正直そこまで感じられませんでした(準同型暗号とかそれはそうなんですが)。
弊学では離散数学と、2年から習う情報理論にあたる。単語をググればそれっぽい大学の資料とか出てくる。
あとはCTFのCryptoをすればOKです
本は、[暗号技術のすべて](https://www.amazon.co.jp/dp/B073J82NQX)がおすすめ。
数学は雪江先生の本で代数をしましょう。
## 形式言語理論
> オートマトン、正則言語、文脈自由文法と関連する概念/アルゴリズム/定理を学びます。言語(文法)をモデル化して数学的に扱っていこうという分野だと理解しています。
> 応用としてコンパイラに繋がっていきますが、それを抜きにとても面白い授業で、2Aで一番好きでした。計算とは?みたいなところまで踏み込んでいくはずです。有限と無限のせめぎ合い。
> 形式検証の話までは深くは扱わなかったので学科でゼミが生える気がします。
弊学では2年でオートマトンをするらしい?
本は、[計算理論の基礎](https://www.amazon.co.jp/dp/4320122070)がよさそう。
応用として、この内容をマスターすると、競プロの記事 [Powerset Construction DPについて](https://blog.knshnb.com/posts/aoj2587/) で何を言っているのか分かるようになりそう
## 計算機システム
> 計算機(コンピュータ)がどのように作動するかを勉強します。データ形式、命令セット、アドレッシングモード、呼出規約、割り込み、キャッシュ、OS、仮想記憶、システムコール、プロセスとスレッド、ファイルシステム、I/O、通信、ネットワーク、セキュリティなどなど(一部のキーワードです)。これもパタヘネなど読むと役立ちそう。
いわゆる普通のパソコンの勉強です。
弊学ではあまりしなさそう。
本は、[UNIXプログラミング](https://www.amazon.co.jp/dp/B00KRB9U8K) これは定番。
[30日でできる!OS自作入門](https://www.amazon.co.jp/dp/4839919844) これはGUIの仕組み
## ハードウェア構成法
> 論理回路について勉強し、回路設計ができるようになります。組合わせ回路、順序回路、演算回路など。冬休みの課題では突然VHDLを書く課題が出され、環境構築さえうまくできず泣きながら回路設計しました。授業は発展的すぎて正直ついていけませんでした。難易度がバグ。符号拡張より定数加算!
これはどちらかというと工学部よりなので弊ではやらないと思う
[ディジタル回路設計とコンピュータアーキテクチャ](https://www.amazon.co.jp/dp/4798147524)
[コンピュータの構成と設計](https://www.amazon.co.jp/dp/4822298426)
このあたりが定番。(かなり重たいので読めてない)
## アルゴリズムとデータ構造
> 具体的には
>・計算量の話
>・基本的なデータ構造(配列/リスト/スタック/待ち行列/木)
>・集合の表現(優先度付き待ち行列/二分探索木/平衡木/ハッシュ/集合群)
>・ソート(バブル/クイック/マージ/ヒープ/バケット/基数)
>・グラフ(ダイクストラ/フロイド/深さ優先探索/幅優先探索/トポロジカルソート/強連結成分/プリム/クラスカル/関節点)
>・文字列(KMP/BM)
>・設計法(分割統治法/動的計画法/貪欲法)などを扱いました。
弊では離散数学にあたりますね。
競プロしてれば大丈夫です。ただ、AtCoderではソートの実装とかしないので、STLに入っている基本的なアルゴリズムの実装を自分で行う経験は必要そうです。
[Open Data Structures](https://github.com/spinute/ods)
アルゴリズムイントロダクション
プログラミングコンテストチャレンジブック
あたりが鉄板です
## 情報科学基礎実験
> C、Scheme、アセンブリを扱いました。競プロ形式で、課題に対してその要件を満たすプログラムを提出するスタイルです。出席の必要も無く、講義も行われませんが、質問には真摯に対応してくださるそうです。
> Cではhello, worldから始まってポインタやメモリ、アルゴリズム(二分探索木やらダイクストラやら)の実装まで学びました。オプショナル課題としてウェーブレット行列やシェル、CPUシミュレータの実装などが出ました。
> SchemeはLispの方言の関数型言語です。これも基本から始まり、最後はScheme処理系をSchemeで作成しました。オプショナル課題として自分自身を読み込める処理系(Scheme on Scheme)が出され、Scheme on Scheme on Scheme on...やらを作っている同期もいました。
> アセンブリはPowerPCを扱いました。最初は何がなんやらですが徐々に慣れました。関数呼び出しでスタックフレームを確保するあたりが山場です。最後はシステムコールを軽く触って終わりでした。オプショナル課題としてクイックソート、printfのサブセット、Brainf*ckのコンパイラの実装が出ました。
アセンブリが読めて、関数型とCができればOKっぽい
https://qiita.com/kaito_tateyama/items/89272098f4b286b64115 これをしましょう
https://sites.google.com/site/isutbe2018/ これをしましょう
# 終わりに
僕は今情報科学基礎実験にあたる部分をやっていて、Schemeや、型理論とかをやっています。
弊で先生が頑張って教えているC言語は、理情では情報科学基礎実験の一部として3週間で終わるそうです。東京できちんとした給料、労働環境で就職したいならそれくらいの速さで積み重ねてきた人と就活で勝負するのかーと思うと、彼らと同じことをより深く独学で学んで対抗しようという気持ちになりました。(もちろん、別の軸で勝負してもいいけど僕にはその方法が浮かばなかった)
まずは2年後期分(半年分)の勉強をがんばります。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment