勉強ブログ

わからんこととか覚え書きとか

Search Minimal spanning trees Union-find

■ lecture 34

  • p.3-6

A-starアルゴリズムについて。

https://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7

ダイクストラ法との直感的な比較は下のサイトがわかりやすかった。

http://tech.nitoyon.com/ja/blog/2010/01/26/dijkstra-aster-visualize/

 

A-starの方が明らかに良く見えるけどゴール地点がわかってないと使えないってことなのかな?

 

  • p.7-18

最小全域木問題に対するプリム法とクラスカル法について。

https://www.google.co.jp/amp/mickey24.hatenablog.com/entry/20090605/1244132474%3Famp=1

 

使い所が想像しにくかったけど下のサイトの問題がわかりやすい。

http://ti2236.hatenablog.com/entry/2012/12/06/145437

 

Graph Introduction Traversals

■ lecture 33

時間が空いてしまった…m(_ _)m

 

グラフ探索アルゴリズムについて。

 一応特につまることはなく。

 

  • p.3 

頂点とか辺とかグラフの構成要素について。これの最初らへん。

https://mathtrain.jp/graph

 

  • p.10-11, 13-16

深さ優先探索について。preorder, postorderの話がわかりやすい。

https://www.google.co.jp/url?sa=t&source=web&rct=j&url=http://www-ikn.ist.hokudai.ac.jp/~arim/pub/algo/algo6.pdf&ved=2ahUKEwjvjtbBoqDZAhWEVrwKHR7WDH0QFjAAegQIExAB&usg=AOvVaw2Mr6WJWNx-QX6wDEyi0Lj_

 

  • p.12, 17

DAG, トポロジカルソートについて。

https://www.slideshare.net/mobile/hcpc_hokudai/topological-sort-69581002

 

  • p.18

ダイクストラ法。なんか聞いたことがあると思ったらインターンで使った方法だった。

http://www.deqnotes.net/acmicpc/dijkstra/

 

 

Pseudo random sequences

■ lecture 32

疑似乱数についての話。

 

  • p.5

疑似乱数生成法の一つである線形合同法。メリットとデメリットについても。

http://algoful.com/Archive/Algorithm/LCG

 

  • p.10-13

暗号で使われる疑似乱数生成の話?具体例が書いてあるっぽいけど意味がわからん…

 

 

 

Balanced Search Structures

■ lecture 29, 31

コメントは追々返します、すみません…m(__)m

 

今回は平衡木について2章まとめて。

スライドをふんふんと読んだだけだけど、とりあえずいつものようにいろんなサイトで補完。

  • B木と赤黒木

http://wwwa.pikara.ne.jp/okojisan/b-tree/index.html

 

  • トライ木(Trie)

https://ja.m.wikipedia.org/wiki/トライ木

 

  • スキップリスト

https://ja.m.wikipedia.org/wiki/スキップリスト

 

wikiほんと色々載ってるな。

 

Sorting

■ lecture 26-28

ソートをまとめて。

アルゴリズムはわかったけどソースコードまでついていけなかったやつもあるので要復習。

 

  • lecture26 p.3

ソートの定義について。"total order"は全順序という意味らしい。

https://ja.m.wikipedia.org/wiki/ソート

https://ja.m.wikipedia.org/wiki/全順序

 

https://www.codereading.com/algo_and_ds/algo/

https://qiita.com/r-ngtm/items/f4fa55c77459f63a5228

CS61Bのサイトにあるシミュレーション付き解説。

https://inst.eecs.berkeley.edu/~cs61b/fa17/materials/lectures/lect28/

 

アルゴリズムの性能についてはlecture 28 p.31のサマリーとwiki参照。

 

冬休み終わっちゃった…

 

 

Macros

■ lecture 29

引き続きCS61A。

 

今回はSchemeのマクロのお話。

www.geocities.jp/m_hiroi/func/abcscm21.html

 

  • p.9

スライドはないのでビデオを見た方がわかりやすい。

quasi-quotationとは準引用符(`)のこと。

Schemeのリファレンスも参考に。


f:id:sgmk53:20180108181209j:image

 

次からCS61Bをまとめて進める予定。