Microsoft PowerPoint - IntroAlgDs-10-2.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - IntroAlgDs-10-2.pptx"

ともあきにかどり
4 years ago
Views:

1 アルゴリズムとデータ構造入門 - 年月日大学院情報学研究科知能情報学専攻知能メディア講座音声メディア分野 okuo@i.koto-u.c.jp,okuo@ue.org TAの居室は号館階奥乃研, 研 M 奥乃研音楽 G -- The Sustitutio Model for Procedure Applictio --6 Coditiol Epressios d Predictes 復習 --7 Emple: Squre Roots Newto's Method --8 Procedures s lck-o o Astrctios.. Lier Recursio d Itertio.. Tree Recursio M 奥乃研ロボット聴覚 G 式 epressio は単純なものから構築. ほぼすべての式は, 値 vlue を持つ. 式は評価 evlute されて値を返す. すべての値には型 tpe がある.. epressios 式 primitives 基本式と comitios 合成式で構成. mes of comitio o 合成法. Mes of strctio 抽象化法. Cretig procedure ojects 手続きの作成法. 以上が言語構文 lguge st, 構築子 lguge costructs 6. Viewig the rules of evlutio from computtiol perspective 計算という観点からの評価法 7. これが言語意味論 lguge semtics Self-evlutig evlutig primitives 評価すると自分自身の値が返る Numers 数 : 8,.8,.,.e-, / Strigs 文字列 : moji, ooles 論理式 : #t, #f Primitives を使って式を合成 + 演算子引数... uilt-i i procedure 組込み手続き基本オブジェクト primitive ojects の処理 Numers 数 :+, -, *, /, <, =, <=, Strigs 文字列 : strig-legth, strig=? ooles 論理式 : d, or, ot, or, d 評価法. 部分式 suepressios p を評価し, 値を得る.. 演算子 opertor に引数 rgumets を適用. procedure pplictio 手続き適用という Nmes for uilt-i i procedures + +という組込み手続き 7 8

2 * * 8 8 * 階乗の定義その１ Astrctio of vlues defie foo 89. * foo foo * foo + foo defie fctoril if <= < * fctoril - Comitio + *. 9 To defie!, if it is o-positive, retur Astrctio of f comitios otherwise, multipl it -! どう実行されるか Susttio model で実行 defie squre * 正書法は下記 defie squre lmd * 最初のは簡便記法 St sugr 糖衣錠のこと積は 7 9 fctoril * 6 fctoril * 6 * fctoril fctorilの呼ばれる回数回 for! time compleit 未実行の * の量最大回 for! spce compleit 階乗の定義その２ To defie fi!,!!! = * * * product = couter * product couter t = couter t + 6 * * * fctoril * 6 * * * fctoril defie fct f t it fct-iter defie fct-iter product couter m-cout if > couter m-cout m cout product fct-iter * couter product + couter m-cout * 6 * * * * fctoril cto * 6 * * * * * fctoril * 6 * * * * * * 6 * * * * * 6 * * * * 6 * * * 6 * * 6 どう実行されるか Susttio model 置換モデルで実行 7 fct f t fct-iter fct-iter fct-iter fct-iter 6 fct iter fct-iter fct-iter 6 fct-iter defie fct defie iter product couter if > couter product iter * couter product + couter iter fct f t から fct-iter へ自動変換が可能 fct-iter の呼ばれる回数回 for f!! time ti compleit l it 未実行の演算の量はない余分な仮パラメータ２個 spce compleit 手続きiterは fct の中で有効仮パラメータ仮パラメタ product,couterは iterの中で有効 d t t は it の中で有効外部からは iformtio hidig g これはオブジェクト指向の１つの特徴

3 defie f if <= * f - このプログラムは次の翻訳! = -! * 下記の fctoril との違いは defie fctoril if <= * fctoril - f * f * * f * * * f * * * * f * * * * * f * * * * * * f * * * * * * * * * * * * * * * * * * 6 * * * SC> time ull? fctoril totl time: secs user time:.6999 secs sstem time: secs #f SC> time ull? f totl time:. secs user time:.9 secs sstem time: secs #f SC> time ull? fct totl time:.76 secs user time:.78 secs sstem time: secs #f トップダウン top-dow 式で計算線形再帰 defie fctoril if <= * fctoril - ボトムアップ ottom-up p 式で計算線形反復 defie fct-iter defie iter product couter if > couter product iter * couter product + couter iter 8 9! は! e ただし e スターリング級数は! e 対数をとると l! l l for >> l! l ウサギのつがい二羽の数内部反射回数 6

4 , if fi, if fi fi, otherwise defie fi cod = = else + fi - fi - i i i ただし, i i fi defie fi-i defie iter cout if = cout iter + - cout iter defie fi-i defie iter cout 木構造再帰 if = cout iter + - cout iter ブロック構造を使わないと, defie fi-i i fi-iter defie fi-iter cout if = cout fi-iter iter + - cout iocci 数の漸化式ビネの公式帰納法で証明せよ. 黄金比 Golde Rtio. =, を検証. k のとき成立を仮定し,k+ で成立を示すコンピュータ将棋あらか清水市代女流王将破る /, 情報処理学会のトッププロ棋士に勝つ将棋プロジェクト特製システム阿伽羅あからはの乗という数を表し将棋の局面の数がこの数に近いことに因んで命名されたハードウエア部 - 東京大学クラスターマシン : -Itel Xeo.8GHz, cores 9 台 -Itel Xeo.GHz, cores 6 台合計 69 台 6766 cores -バックアップマシン:プログラムそれぞれについて台ずつ -CPU: Xeo W68.GHz 6cores -Memor: G DDR UM ECC G 使用ハードウェアは当日変更される可能性もあります年月 6 日追記ソフトウエア部 - 構成 : 国内トッププログラムによる多数決合議法つのプレイヤープログラムに局面を渡し指し手を受け取りもっとも多い手を指し手として返す - 合議マネージャ : 開発 : 電気通信大学伊藤研究室 & 保木邦仁 - プレイヤー : 激指開発: 激指開発チーム鶴岡慶雅横山大作 - プレイヤー : GPS 将棋開発 : チームGPS 田中哲朗金子知適ほか - プレイヤー : oz 開発 : 保木邦仁 - プレイヤー : YSS 開発: 山下宏 /, 東大 THE POWER O LOGARITHM 計算尺 slide rule, slipstick 対数による積の計算乗算対数加算累乗対数乗算はいくら対数 log. K 9 G 音楽のピッチ音の知覚 8

5 Slide Rule Scle Lel Vlue Reltive to C/D A X X C C X X pi K X KZ X 6 L log X Lg log X L l X R / X R, R Squre root of X S si X Sh, Sh sih X C/M X log e LL e. Sq, Sq Squre root of X CI / X LL or ZZ e. SRT si X, t X CI / pi X LL or ZZ e. ST si, t X D X LL or ZZ e T t X, cot X D X pi LL or LL/ e T, T t X, cot X D/M X log e LL or LL/ e. T t X, cot X DM X log e LL or LL/ e. Th th X アポロミクロの決死隊タイタニック DI / X DI / pi X E e H H, H Squre root of +X HC LL or LL/ e. M log X P Squre root of X p% P, P Squre root of X V Volts W, W Squre root of X Z X ZZ, ZZ, ZZ e 大きな数小さな数 dec d deci d - hecto h ceti c - kilo K milli m - meg M 6 micro μ -6 gig G 9 o -9 ter T pico p - pet P femto f - e E 8 tto -8 zett Z zepto z - ott Y octo - te or decd setillio hudred or hectotd septillio thousd or chilid mrid decillio lc or lkh 6 vigitillio 6 millio cetillio 7 crore googol 8 mrimrid googol googolple 9 millird or illio trillio N N ple qudrillio -N N mie 8 quitillio ple 阿伽羅 88ple 無量大数 ple 垓 mie 絲糸 8ple 不可思議 6ple 京 mie 忽 7ple 那由他 ple 兆 6mie 微 6ple 阿僧祇 8ple 億 7mie 纎繊 6ple 恒河砂 ple 萬万 8mie 沙 8ple 極 ple 千 9mie 塵 ple 載 ple 百 mie 埃 ple 正 ple 十 mie 渺 6ple 澗 ple 一 mie 漠 ple 溝 mie 分 mie 模糊 8ple 穣 mie 厘 mie 逡巡 ple 杼禾偏 mie 毫毛 mie 須臾 mie 分 mie 模糊 mie 厘 mie 逡巡シュンジュン mie 毫毛モウ mie 須臾シュユ mie 絲糸シ 6mie 瞬息シュンソク mie 忽コツ 7mie 弾指ダンシ 6mie 微ビ 8mie 殺那 7mie 纎繊セン 9mie 六徳リットク 8mie 沙シャ mie 虚 9mie 塵ジン mie 空 mie 埃アイ mie 清 mie 渺ビョウ mie 浄 mie 漠バク 6

6 iocci 数の漸化式線形差分方程式の解法. 線形差分方程式の解法特性方程式を作成解を求める. その根を α,β とすると元の差分方程式の解はと表せる D C と表せるただし, C, D は定数 D C 初期値等から定数項の値を求める母関数 geertig fuctio の解法. 母関数 geertig fuctio の解法漸化式 :,, 般的な解法一般的な解法. 方程式の根を φ,ψ とすると t t 一般項はと表せるただし A は定数である A ただし A, は定数である. 初期値等から定数項の値を求めるより, より A 9 A フィボナッチ数列 : 8 フィボナッチ数列 :,,,,,, 8, 母関数 6 左辺右辺左辺部分分数への分解両辺を比べて +β β 両辺を比べて α+β=, α β=- これはの解 t t 級数展開をするとの係数はボナチ数... の係数はフィボナッチ数の係数はフィボナッチ数一方,, defie fi cod = = else + fi - fi - 木構造再帰木構造再帰木構造再帰木構造再帰

7 fi-i iter iter iter iter iter iter 8 iter 8 8 Lier itertive process 線形反復プロセス defie fi-i defie iter cout if = cout iter + - cout iter C: に対して fi の呼ばれる回数 C=C= に対して C=C-+C-+ C=, C=, C=9, C=, 一般に Ck > k/ C を求める. =C+ とおくと. =-+- for. =, = に対して C=C-+C-+ =C+ とおくと =-+- for =, = A, φ,ψ は t t の根 A C 9 i は.6 より従って fi はに最も近い整数 6. 繰り返し版階乗のプログラムのファイルを作成せよ. fct.scm. 階乗のプログラムを実行し, 出力結果を求めよ.. lod fct.scm. fct + ご自分の学籍番号の下桁. 階乗のプログラムの説明と出力結果を lte で作成し,pdfをレポートとする. 紙でも可. Progrm ファイルと pdf を SICP-@zeus.kuis.koto-u.c.jp koto-u cjp に送付 otherwise 回答は減点 6. Commd Prompt, cgwi で cop&pste. Shell の機能を使う. Output file を明示的に使用 defie out ope-output-file outfile.tt out 同じファイル名のファイルがあると上書き out #<port to outfile> displ fct 7 out 結果を outfile.tt に書き込む ewlie out #t close-output-port output port out. cll-with-output-file Output file の非明示的使用 cll-with-output-file fct.tt lmd out ewlie out displ fct out ewlie out 6

Microsoft PowerPoint - IntroAlgDs-11-2.pptx

Microsoft PowerPoint - IntroAlgDs-11-2.pptx アルゴリズムとデータ構造入門 - 年月日 documetclss{pper,pt}{rticle} usepckge{listigs} title{ タイトル } uthor{ 学籍番号氏名 } begi{documet} mketitle sectio{ 反復型階乗 } lstset{umbers=left,bsicstle= smll} lstiputlistig{fct.scm} 以上で,