Hatena::ブログ(Diary)

ボクノス このページをアンテナに追加 RSSフィード

2012-11-03

英語の勉強にMITの講義でも Lec 6 | Introduction to Algorithms(SMA 5503)

またタイトル変えましたが気にせず、6回目の講義を聞いていきます。

D

シラバスとか。

Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare

Today we're going to not talk about sorting.

・・・ザワザワ・・・な、何だって・・・

  • 文法的にnotの位置が気になる。
    • そう言えば、英語勉強なので、調べます。
  • 教科書的にはto不定詞の否定はnot to do 〜。to not do 〜もかなり一般的。
  • だけど、be going to do 〜だから・・・be not going to do 〜となるはずだが、否定する所が遠い。
  • 結論:言いたい部分だけ否定するなら、be going to not do 〜はアリかな。

Order statics

  • ん? sortingじゃね?
  • ナイーブな実装なら、ソートして、n th の位置を持ってくるよね。
    • 一般的にO(n log n)な気がする。
  • 調べる。
  • だいぶ間が開いたけど、ちょっと再開。←使い回し。
  • この辺りも。選択アルゴリズム - Wikipedia
  • Randomized divide and conquer
    • うぅん全然わからんな。今度聞いてみよう(汗
  • 難しく考えていたけど、最小、最大を取り出すのは簡単。O(n)
    • そこで思いついたナイーブな実装2は、ソートする対象はk番目の要素までとすると・・・
    • kが小さければだいぶ早いけど、O(n log k)かかる。

単語

order n
the way in which people or things are placed or arranged in relation to each other

更新履歴

進みが遅いので更新したらここに書いとく。

  • 2013/03/01
    • 微妙に進めた気がする。
  • 2013/01/28
    • シラバスとか追加した。
    • そういやデザイン変えた。

2012-10-23

英語の勉強にMITの講義でも Lec 5 | MIT 6.046J / 18.410J Introduction to Algorithms

タイトル微妙に変えました。少しづつ進めて行きます。

D

今回もsortingっぽいが、sortingがアルゴリズムの基本であることは、前回までの講義で明らか。


How first can we sort?


Depends on Model

  • of what you can do with the elements.
  • Can we do better than Θ(n log n)?
    • Yes or No?
    • おぉ。主題に迫ってきた感。

Comparison sort


Sorting in linear time

  • 来ました。
  • How first can we sort? → n log n. → Often correct. "It depends."

Counting sort


Stable sort

  • 同じ値だった場合、元の順序を保つなら、stable

Radix Sort


まとめ


ふと思ったこと


単語

comparison n
the process of comparing two or more people or things 比較、対照
restriction n
a rule or law that limits what you can do or what can happen 制限、制約 limitとは若干違う。
internal adj
connected with the inside of something 内部の
implement v
to make something that has been officially decided start to happen or be used 履行する、要件を満たすように実行する
permeation n
to spread to every part of an object or a place 浸透、普及
radix n
1. the base of a number system or of logarithms 基数

お詫び

Fedoraインストール〜2012/10/23までの記事でリンク先に誤りがありました。

2012-10-19

Vim + Racket環境の構築

色々ハマったので書いとくぜ。後で書き足す。


Racketのインストール

MzScheme5とでも言うべきか?

名称が変わっただけでなく、とんでもなくパワーアップしているようだ。

Racket5.3は今のところ対応してないみたいなので、5.2.1を入れてみる。

The Racket LanguageからUnix版のソースを拾って、適当に展開。

とりあえずローカルインストール

$ ./configure --enable-shared --prefix=/home/tanaka/racket521
$ make
$ make install

インストールオプションに、--enable-sharedが必須

インストールがやたら長いのでお茶にするといい。


最新版のVimをゲット。

Racketが登場したのはVim7.3以降なので最新版を入手する。

の前に、mercurialというバージョン管理ツールインストールfedoraだと、

# yum install mercurial

で、ダウンロード

$ hg clone https://vim.googlecode.com/hg/ vim

次!


Vimコンパイルテスト

最小限のオプションで試します。

$ ./configure --enable-mzschemeinterp --with-plthome=/home/tanaka/racket521
$ make

makeまででテスト

$ src/vim

表示は?

:version
VIM - Vi IMproved 7.3 (2010 Aug 15, compiled Oct 19 2012 16:19:45)
Included patches: 1-692
...
+mzscheme
...

おぉぉぉぉ。Let's try!

:mz (version)
5.2.1
:mz "hello, Vim + Racket world!!"
hello, Vim + Racket world!!

キターーーッ!


インストールしてこう(2013/01/25 追記分)

テストが順調だったので、インストールしていく。

Vim7.3の最新パッチ(2013/01/25 782)だとRacket 5.3.1がインストール出来るようだ。

とりあえずRaketインストール

$ cd ~/src/racket-5.3.1/src/
$ ./configure --enable-shared --prefix=/usr/local/racket531
$ make
$ su
# make install
# ln -s /usr/local/racket531 /usr/local/raket
# exit

パスが通ってない気がするが、まあいいや。

Vimインストールオプションを増やして、

$ cd ~/src/vim/
$ ./configure --enable-mzschemeinterp --with-plthome=/usr/local/racket --prefix=/usr/local \
--with-features=huge --enable-multibyte --enable-perlinterp --enable-rubyinterp --enable-gui=gtk2
$ make
$ su
# make install

とりあえずこんなもん。後で色々追加する。

メモ 1:パッケージが足りなかったので、gtk2-devel, perl-coreインストールした。

メモ 2:インストール直後、/usr/local/bin/vimを見つけられず。シェル再起動するとパスが通った。キャッシュについて後で調べる必要あり。


ハマったところ


参考


まとめ

ハマったらソース


Have fun with Vim + Racket!

んじゃね〜


更新履歴

2012-10-17

Fedora 17をインストールしてみた

もちろんKDE版。


Fedoraの入手

さあ、自由を手に入れよう。

Fedora Project ホームページ

焼いて、リブート

これだけで、あなたは自由だ。


システム

$ /usr/libexec/mozc_tool --mode=config_dialog
    • おけ。
      • 追記:2013年になってから直った気がする。

開発ツール


インターネット


その他


発見


課題

  • Vim + MzScheme(Racket)
    • 前にもハマった気が・・・。
    • とりあえず、コンパイルできた!!


履歴

  • 2012/10/18
  • 2012/10/19
    • Vim + Racketは別稿で。
  • 2012/10/23
    • その他の項追加。

2012-10-14

英語の勉強にMITの授業でも Lec 4 | MIT 6.046J / 18.410J Introduction to Algorithms

今日もダラダラ英語頑張りますw

D

継続は力なり。


Quick sort

  • お、ようやく登場。期待です。
  • 今日はbald/bɔːld/な教授(発音が違ってた・・・)
  • Sort "in place"
    • 今までと形が違うのが特徴。
  • practical(with tuning)
  • Divideなが!!
    • 後はシンプル
    • そういや1段階ごとにn - 1要素数が減るんだな。枝になればなるほど要素数が減る。これは非常に大きい?という考察
  • ここからanalysis。
    • worst case
      • T(n) = T(0) + T(n - 1) + Θ(n)
      • Σが見える・・・あぁぁぁぁぁ・・・1個づつ並べてんじゃん!!
      • O(n^2)ですね。
      • 解説あり。とんくす。
    • best case
      • 半々ですな。
    • 1/10,9/10
      • 良い練習問題。
      • 間違ってもいいからvoteせよ。と。
    • 考察2
      • 再帰するごとにピポットが取り除かれ、葉になる。つまりwrostを厳密に計算すると(n^2) / 2 + n回。
      • bestの場合・・・n log_2 n + nよりは少ない・・・考え中。
        • 1, 3, 7, 15, 31, 63・・・でツリーが深くなる。ツリーの高さhの時の要素数は、Fn(h) = 2*Fn(h - 1) + 1 (h > 0), Fn(h) = 1 (h == 0)こんなもん。再帰を展開すると・・・考え中。
        • n log_2 nならば、1, 2, 4, 8, 16, 32・・・あ、一段減ってるだけ。展開してないけど、2^(h + 1) - 1。つまり、n回早くなっただけか。結合にnかかるから、n log_2 n。出た。
    • 再開。lucky, unluckyが交互に繰り返された場合
    • で、ソート済みだと遅いから、ビボットランダムにw
      • するっと、最悪のケースはよーわからんwww
      • で、それをanalysis。ってマジっすか。
      • その前にストレッチタイム入ります。
        • もうダメ・・・ツボった。アメリカ人自由過ぎるwww
      • ほほぅぅぅ。なるほど。確率論で攻めればいい。
      • なるほどと思ったが、何言ってるかワカンネ。英語が理解できないのか数学が理解できないのかw
      • このへん→Quicksort - Wikipedia
    • 気付いたら寝てたぜww
      • 数学部分は理解度が落ちる。もう一回聞こう。

単語

一応英語勉強なので。

practical /ˈpræktɪkəl/ adj
connected with real situations rather than with ideas or theories 実用的な
partition v
to divide sth into two parts 分割する
invariant adj
always the same; never changing
variant n, adj
a thing that is a slightly different form or type of sth
boundary n
a real or imagined line that marks the limits or edges of sth and separates it from other things or places; a dividing line
alternate n
happening or following one after the other regularly

まとめ

TTFN!


更新履歴

  • 2012/10/20
    • 続きを聞いた。
Connection: close