Fedora27入れた

お久しぶりです。最近はイラレの人やってます。

SSDを買ってFedora27をクリーンインストールしたので、インストールメモを残していこうと思います。

※ 雑多すぎるのでそのうち分割する

Hello Fedora27

https://spins.fedoraproject.org/
から、KDE版のFedoraをダウンロードして、焼いときます。

リブートしたら、フリーダムな世界へ行きましょう。

SSDの容量が少ないので、/homeと/のパーテーションを一緒にしてみた。

化石の知識

何もかもが新鮮だ。

知識をアップデートしないと色々ヤバい気がしたので、たまにはブログでも書こうと思った。はてな記法忘れたし。

とりあえずよろしくお願いします。

DNF

Fedora22から、パッケージシステムがDNF(Dandified Yum)に変更されたらしい（情報遅すぎるだろ）。

Fedoraらしい略語ですが、慣れねぇ・・・

# dnf update とりあえず打っとけ
# dnf install 何か 何かをインストール
# dnf search 何か　何かを検索
# dnf list installed 何か　何かがインストール済みか

yumと打ち間違えても、dnfにリンクしてる様子。

% ls -l /bin/yum
lrwxrwxrwx. 1 root root 3 Nov 29 18:48 /bin/yum -> dnf

親切だけど、矯正ギブスにはならないなぁ。

何はともあれブラウザ入れた

軟弱なのでchromeです。
https://www.if-not-true-then-false.com/2010/install-google-chrome-with-yum-on-fedora-red-hat-rhel/

あ・・・sudo出来ん・・・dnfの補完が効かない！！ま、後。

一気に環境が戻るって素晴らしい！

Vim

vimって打ち込んだら、command not found・・・だと・・・イラッと来たので、vim-enhancedを超速インストール。

コンパイルしなきゃなーと思いつつ、現況を確認。

:terminal

！！

一瞬落ちたかと思ったぜ。分割されたシェルの画面に泣いた。色も大丈夫。マジかぁ・・・感動しすぎて前が見えねぇ・・・

で、正気に帰ると、戻れないという罠にハマる。^Wは効く様子。ふぅ。

よくわかんないときは、Vim鬼の鉄則。ヘルプを見よう。

:terminalもバッチリ書いてある・・・流石です。

日本語入力環境

お約束どおり日本語入力でハマった。

とりあえず従来通りibus-mozc入れた。

自動起動でハマった。

• ibus-deamonをどのタイミングで起動するのか・・・
• あれ？~/.xprofileが読み込まれてない気がするので調査中。 ← fedora9で廃止ｗ
• 当たり前ですが、chmod +xしないと動かないｗ
• ~/.xうんたらは何が廃止されたんだろう？要追加調査。 ←　fedora25からWayland採用。X使ってない。
• ~/.bash_profile or ~/.bashrcに書けば動作するけど、なんかねぇ・・・

色々調べ回った結果、素直に自動起動に記述するのが良いようだ。
System Settings > Startup & Shutdown > autostartに

ibus-daemon -rdx

をadd。
起動オプションはibus-daemon -hに書いてある。デスクトップの事はデスクトップに任せる。KDEは言語オプションがしょっぱいなぁ。

そういや、なんかパッケージがあった気がする・・・

im-chooser

ソレダ・・・ようやく思い出したｗｗｗ　←　この時点でやる気喪失ｗｗｗ

なんとか従来通りに日本語を打てるようにしたけど、初回起動時はDirect Inputなのが気に食わない。

Direct Inputは仕様なので、ソースをいじるか、自動で選択するからしい。

追記:

• konsoleで日本語入力できないので。im-chooser入れました。
• 打てるようになったけど間違えて入力→ESC→文字が残ったままになる。

フォント環境

とりあえず、見られそうなフォントを入れる。

# dnf install ipa-*-fonts

*を使うとカッケー。ってかどうやって展開してんだっけ・・・

セット内容は{明朝, ゴシック} × {等幅, 可変長, 等幅(日)+可変(英)}。

まぁ、マシになった。

# dnf search *-fonts

したら夢が広がった。

サウンド

音が鳴らねぇ・・・と思ったら、デジタル出力してたんだった。復帰手順のメモ。

• デフォルトだとアナログ出力しか出来ないようだ。
• アナログ端子繋がないと、何故か設定画面まで一緒に消えるようだ。設定画面だけの問題で認識はされてる様子。焦ったぜ。
• とりあえず一旦アナログ端子繋いで再起動。(緑の所に刺すようだｗ)
• サウンドカードの設定画面が出たら、アナログ出力→デジタル出力に変更。

無事ヘッドホンアンプ経由で音が出た。アンプと言っても単なるヘッドホンとスピーカーのスイッチャーなんだけど、色々古いのでマジ焦る。

zshのインストール

最近のbashはマジ便利なので、特にzshに移行する必要は無いけれど、秘伝のタレの蓄積が多少多い。

# dnf install zsh

適当に環境を整えた。

dotfilesのレポジトリとの整合性をどうしよう・・・

未解決問題

• デフォルトシェルとKonsoleが連動してない点。
• ttyの画面がやたら乱れる。

Vimをコンパイルしよう

だいたい環境が揃う＆linuxの感覚を取り戻せるんじゃないかという安易な計画。

とりあえずコンパイル出来ることを確認していく。

では始める。

$ mkdir src # まずこれ
$ cd src
$ mkdir vim
$ cd vim

コマンドが酷いな。やり直し。

$ cd ~
$ rm -r src
$ mkdir -p src/vim
$ cd src/vim # insert-last-argument alt+.

まだ修行が足りない。

何はともあれ、とりあえずgit

$ which git  # ないでござる。
/usr/bin/which: no git in (/usr/local/bin:...
$ su -
# dnf install git
# exit

dnfに慣れてきた。

ハイ。

% mkdir -p ~/src/git
% cd ~/src/git
% git clone https://github.com/vim/vim.git
% cd vim
% ./configure # 怒られたら入れていく。

入れたやつ。

# dnf install gcc
# dnf install ncurses-devel

意外と少ない。

行くぜ！

$ make
$ src/vim
VIM - Vi IMproved
version 8.0.1428

ローカルのvimのバージョンは1427。ほぼ最新。Fedoraありえん・・・

最新版を追いかける目的なら、ソースからインストールする必要は無いし、rubyもpythonも使えちゃうてんこ盛りコンパイルオプション・・・Fedoraにはいつも感動させられる。

追記:

• Fedoraのvim-enhancedは・・・+clipboard付いてねぇ！！しばらく中クリックだな・・・

racketのコンパイル

Vimのオプション+mzschemeを有効にするのが目的。

% mkdir ~/usr
% cd ~/src/git
% git clone https://github.com/racket/racket.git
% cd racket
% make unix-style PREFIX=$HOME/usr CONFIGURE_ARGS_qq=--enable-shared

Makefile見ながら色々試行錯誤してこれに落ち着く。

コンパイルに2時間以上かかるので、慎重に。

~/.dotfiles

ドットファイル系は、github管理なのですが、モダン環境に慣れるため、1から書き直してます。

とりあえず、gitのお勉強が中心。

githubから引っ張ってきたら、makeで環境をガガッと構築出来るようにしたいので、Makefileだけ書いた。

$ make deploy # シンボリックリンク張る
$ make clean  # 消す

素敵すぎる。

毎日が楽しい。続きます。

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

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

シラバスとか。
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)な気がする。
• 調べる。
  • Order statistic - Wikipedia, the free encyclopedia
  • 「これは使えそうだ」
    • 検索で上位何件を引っ張ってこれそうな気がする。
  • だけどやっぱり統計勉強しないといけないわけで(涙)
    • とりあえず、高校の参考書からかな。
• だいぶ間が開いたけど、ちょっと再開。←使い回し。
• この辺りも。選択アルゴリズム - 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
  • シラバスとか追加した。
  • そういやデザイン変えた。

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

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

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

How first can we sort?

• 僕としては、n log nかなと。曖昧だな。
  • Often correct.らしい。
• It depends.
  • よく使う英会話表現だなｗ
  • 日本語だと「あ〜」って感じになっちゃうけど、英語だと上手く伝えられる表現だと思う。
  • 解説は、404 Blog Not Found:学校では教えてくれないグッドラッパー英語#0 - it depends.
    • It depends.
  • dependの本来の意味は依存する。
  • It depends on 〜もよく使う。
  • という事で、今回の講義は、

Depends on Model

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

Comparison sort

• お、初めて聞くアルゴリズム。と思ったら、「モデル」についての話だった。
  • と、気付くまでに相当の時間を要した。
• Comparison sort - Wikipedia
  • 日本語だと、比較ソートの理論限界
  • 補助資料 スターリングの公式
    • 微積ですか・・・。大学だと解析学とか言うんですか？
• 比較ソートは全て決定木で表すことが出来る。
  • 再帰も、forで表せば決定木だな。
• リストの順列はn!あるので、決定木の葉の数はそれ以上になる。決定木の高さh=計算量である。決定木が持てる最大の葉の数は2^h。つまり、n! <= 2^h , h >= lg n!、スターリングの公式より(It's a magic!)・・・= Ω(n log n)になる？スターリングの公式がわからん。
  • 決定木の全体像はとんでもなくでかい。
• だいぶ迷走したが、ようやく感覚的に理解できた。数学的には詰める所がいっぱいあるな。
• 途中でアルゴリズムを切り替える手もアリ。
  • 僕の日記のヒープソートの項も参照。

Sorting in linear time

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

Counting sort

• 度数分布を使う方法。
  • Counting sort - Wikipedia
  • バケットソート - Wikipedia
    • 分布数えソートが下の方に書いてある。bucketの場合はデータごと突っ込む。
• 頭いいな。
• とりあえず考察。
  • 予めデータの範囲がわかっている必要がある。
  • 初期化(キーの範囲 k)とカウント n、再配置(k + n)で済むな。= 2(k + n) = Θ(k + n)→早い？→kがでかいと初期化、位置計算で泣ける。→kに依存する。
  • ヒープを使えば、データの範囲を除外出来る→早くね？→ヒープ作成に最大n log nのコストがかかるな・・・→重複が多い事が条件か・・・
  • 結論：データの値に強く依存する。→"It depends."
• ま、聞くべ。
  • おぉっと、僕の考えていた方法と講義と再配置の方法がちょっと違った。
  • 予め戻る位置を計算しておけば、元のデータをもう一度走査しながら、付随する情報もソートできるのか。→Counting sortは安定ソート。
    • 考察を修正：初期化 k →カウント n →オフセットの計算 k → 配置 n なるほど！！
• アルゴリズムの選択は重要だな。
• 考察したことを解説。

Stable sort

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

Radix Sort

• とりあえず考察編。
  • 基数ソート - Wikipedia
  • Counting sortの欠点を補い、データの範囲が広くてもまぁまぁ対応できそう。
  • 基数ソートの各要素に、Counting sortを使ってみると、
  • 8ビットなら、2(n + 2) x 8 = 16n + 32
    • データ数が少ないとパフォーマンスが出ない。データ数nが2^16 + 32 = 65536 + 32以上なら比較ソートより早い？
  • あぁ、8ビットだと0〜255個の範囲なので、10進数だと、2(n + 10) x 3 = 6n + 60か。
    • データの範囲と、nによって最適な基数は変化しそうだ。最適な基数は・・・。
  • 条件次第だが、n log nを凌ぐパフォーマンスが出せそうだ。→"It depends."
• 聞く。
  • パンチカードに関する貴重な話。
    • この辺→タビュレーティングマシン。メモメモ。
    • Amazon.co.jp： JIS FORTRAN入門 (上): 森口 繁一: 本この本思い出したわ。
      • 大学の授業全く出席してなかったな。覚えたコマンドは、$ netscape www.yahoo.co.jpだけだったが、今は高階している。
  • 並べ替えてみると、安定ソートを上手く使ってるなぁ。
  • 最適な基数は・・・。の答えが出てたありがたいｗ
  • という事で、O(bn / log n)っと。
• 続きはnext fallか。聞けるかな・・・。

まとめ

• ソートの理論限界はΘ(n log n)は間違いで、「比較ソートの理論限界はΘ(n log n)」である。
• 条件によっては、もっと早いアルゴリズムを選択することも出来る。

ふと思ったこと

• 挿入ソートの高速化について。
  • 挿入ソートの挿入時にバイナリサーチすれば、ちょっと早くなるな。
    • 固定配列だとずらしが必要で、連結リストだとバイナリサーチが苦手。
    • →却下。
  • 連結リストならば比較だけで、交換処理が不要なので、Θ(n^2)変わらないけど、ちょっと高速化出来るのか。
  • 連結リストだと、バイナリサーチしにくい。ならデータをヒープにしちゃえばいいよね→ヒープソート。
  • ありがとうございました。
• Interactive transcript
  • いまさら気付いたけど、超便利。
  • 字幕で好きな所まで飛べる。
  • 辞書で調べるのが楽。

単語

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までの記事でリンク先に誤りがありました。

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を見つけられず。シェルを再起動するとパスが通った。キャッシュについて後で調べる必要あり。

ハマったところ

• Racket5.3はまだ対応してなかった。
• Racketのコンパイルオプションで、--enable-sharedを付ける必要があることに気づかず。
• Racketのインストール長すぎ。
• VimのバージョンとRacket,MzSchemeのバージョンの関係を掴むのに時間がかかった。

参考

• racket (:mz) SEGV's vim - Google Groups
  • だいぶ参考になった。vimが落ちる(セグメンテーション違反)というネタだが・・・。
• 最新のvimをインストールする | 村式流 イッパシエンジニアへの道
• rubyビルドガイド
  • --enable-sharedの解説。
• if_mzsch.c
  • MzScheme, Racket関連のソース。
• 14.7 Environment and Runtime Information
  • バージョンの取得は(version)

まとめ

ハマったらソース嫁

Have fun with Vim + Racket!

んじゃね〜

更新履歴

• 2013/01/25
  • ようやくインストールした。
• 2012/10/20
  • Racketのバージョンを5.1.3→5.2.1に変更。
  • :mz (version)でRacketのバージョンが取得出来る。

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

もちろんKDE版。

Fedoraの入手

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

Fedora Project ホームページ

焼いて、リブート。

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

システム

• 言語設定は英語。
• グラボのドライバ入れた。
  • あとで書く。
• フォント入れた。
  • プログラミング用フォント Ricty
    • 丸字っぽくてちょっと癖があるけど、視認性が抜群。
    • インストールが若干メンドイ。
• iBus-Mozc
  • google日本語入力の派生版らしい。→AboutMozc - mozc - About Mozc - Mozc - Japanese Input Method for Chromium OS, Windows, Mac and Linux
  • パッケージインストール。
  • 入力のトグルを+`に。
    • Task Switcherとキーがかぶってたので適当に移動。
    • iBus preference > General > Keyboard Shortcuts > Next Input method > graveを入力。ふぅ。
  • google日本語入力とはだいぶ違う気がする。
  • なんか設定画面が開かない。fedoraの場合、/usr/libexec/以下らしい。

$ /usr/libexec/mozc_tool --mode=config_dialog

• • おけ。
    • 追記：2013年になってから直った気がする。

開発ツール

• vim-X11
• vim-enhanced
  • root&緊急用。ローカルではコンパイルして使う予定。
• gcc
  • とりあえずこれ。コンパイル出来ん。
• Ruby
  • Vimに組み込む予定なので。
  • バージョンは、ruby 1.9.3p194 (2012-04-20 revision 35410) [i386-linux]
• JDK,JRE 1.7.0
  • フォント設定でちとハマる。リンクしすぎて何処に本体があるのやらわからん。

インターネット

• Firefox
  • インストールしても立ち上がらなかったので、システムアップデートしたら治った。
  • Flash, Reader入れた。
    • 公式からパッケージ拾ってきて、インストール。
  • Javaアプレット
    • Fedoraのバージョンによってだいぶ違うようなので要確認。Java/FAQ - FedoraProject
    • Fedora 17の場合はyum -i icedtea-web
  • Add-ones
    • とりあえず必要なものだけ入れてこう。
    • はてなブックマーク Firefox 拡張
      • はてな住民なのでｗ
    • Make Link :: Add-ons for Firefox
      • 地味に便利。
    • AdBlock
      • 無いと死ねるが、しばらく広告出しとくかな・・・。

その他

• GoldenDict
  • ネットの辞書が使える。
    • OALDと、LEOCD登録。
      • 基本の3000語だけ覚えれば使えるので、ESLな僕にはぴったり。
    • CSSいじらないと。
  • ポップアップが便利。
• TheBrain
  • パッケージには無いが、マインドマップツール。
  • 一部有料の機能あり。
  • 思考の分解に便利なので愛用してた(過去形ね)
  • Javaで動くので、Javaインストールした。

発見

• Fedoraのパッケージはほぼ最新版を追っかけてる。
  • 新しいモノ好きにはオススメ。
• はてなダイアリーって広告出るんだね・・・ってかネットってこんなに広告だらけだったのかと気付いた。
• bashって普通に補完してくれるんだね。bashも進化してるようだ。
• rtkit-daemonという名前のプロセスがある。害は無いっぽいが、あとで調べる。

課題

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

履歴

• 2012/10/18
  • 日本語入力の設定追加。
  • Firefoxの項を詳しく。
• 2012/10/19
  • Vim + Racketは別稿で。
• 2012/10/23
  • その他の項追加。

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

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

継続は力なり。

Quick sort

• お、ようやく登場。期待です。
• 今日はbald/bɔːld/な教授(発音が違ってた・・・)
• Sort "in place"
  • 今までと形が違うのが特徴。
• practical(with tuning)
  • また重要な発言。
• Divideなが！！
  • 後はシンプル。
  • そういや１段階ごとに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が交互に繰り返された場合。
    • 視点が面白い。
  • で、ソート済みだと遅いから、ビボットをランダムにｗ
    • するっと、最悪のケースはよーわからんｗｗｗ
    • で、それをanalysis。ってマジっすか。
    • その前にストレッチタイム入ります。
      • もうダメ・・・ツボった。アメリカ人自由過ぎるｗｗｗ
    • ほほぅぅぅ。なるほど。確率論で攻めればいい。
    • なるほどと思ったが、何言ってるかワカンネ。英語が理解できないのか数学が理解できないのかｗ
    • このへん→Quicksort - Wikipedia
      • 英語版のWikiは詳しすぎる。
  • 気付いたら寝てたぜｗｗ
    • 数学部分は理解度が落ちる。もう一回聞こう。

単語

一応英語の勉強なので。

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

まとめ

• 間違う事で大きな気付きを得ることもある。
• 授業中の寝方　みんなはどのタイプだった？ : 2chコピペ保存道場
  • 俺は4タイプだが。今回は10だ。

TTFN!

更新履歴

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

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

ダラダラ英語の勉強を続けましょう。本末転倒って奴です←自覚アリ

Divide and Conquer

• 分割征服？ by forceだから統治は政治的意訳？
  • 語源は英国らしい。→分割統治 - Wikipedia
  • 知ってはならない事だったかも・・・
• とにかく本題へｗ
  • →Divide and conquer algorithm - Wikipedia 予習のため音読した。
• 本当は3 steps, Divide Conquer Combine
• Marge sort
  • 前回の講義を含めて復習。
• Binary search
  • バイナリサーチ知らない人は一人・・・授業を受ける人の質が違いすぎる。
  • 6.001をほぼ全員が受けてるのね。ハッカーがハッカーに教えている・・・感動。
  • ようやく再帰の計算量をサクサク計算出来るようになってきた。
• Powering a number
  • 分割統治しながら、メモ化すると早そう。
  • 偶数を考慮しないとな。
  • メモ化の話は無いよ。そらそうか。
• Fibonacci numbers
  • 趣味嗜好が完全一致ｗ
  • ナイーブな実装はΩ(φ^n)
  • メモ化するとΘ(n)だと思った。一般項からΘ(1)と行きたい所だが正確ではない。√5は展開する必要があるのでΘ(n)より早くはならない。
  • 数学ガールを読むぞぉ 6 - フィボナッチ数列の一般項 - ボクノス
  • 数学ガールを読むぞぉ 7 - フィボナッチ数列の一般項(2) - ボクノス
• Bottom up algorithm
  • おぉっと早とちり。上の説明。
  • そしてマトリックス・・・苦手だ。激しく苦手。
  • 手計算で求まる事は確認。Powering numberと同じ方式。偶数、奇数を考慮すること。
  • で、Θ(log n)。不思議だ。証明してないからよーわからんけどスゲー。←いつかやります。
  • なんとなくわかったかな・・・。
• Matrix multiplication
  • 手計算でオーダーは出した。Θ(n^3)
• Strassen algorithm
  • この辺のお話→Strassen algorithm - Wikipedia, the free encyclopedia
  • 2x2だと8→7と微妙な改善だが、人類にとってはとんでもなく有用な改善。
  • magic！なのだが、手計算なら採用しないわｗ
  • ここらへんはCPUかGPUにお任せでｗ
• VLSI layout
  • VLSIは集積回路の事IC→LSI→VLSI→ULSIらしい。
  • コンピュータ以外への応用。なかなか面白い練習問題。
  • おぉぉぉ。正解したｗ
• See U later!

単語

今日はムズイ単語もなくすらすら進みそう。

conquer v

to take control of a country or city and its people by force 征服

polynomial n

an statement in algebra that contains several different numbers and signs which are equal to a specific amount 多項式

induction n

a method of discovering general rules and principles from particular facts and examples 帰納法

pseudo- 接頭

false or pretended 偽の〜

まとめ＆雑感

• 1時間の講義内容が濃すぎる。
• フィボナッチは更に深かった。新たな発見をまた一つしたので、英語以外にも役立った。
• やっぱりMITの授業は面白い！！