【メモ】今後見るサイト
伝わるデザイン|研究発表のユニバーサルデザイン
http://tsutawarudesign.web.fc2.com/index.html
数学:物理を学び楽しむために
■ 関数や収束についての基本(2 章)
■ 一変数関数の微分とその応用(3 章)
■ 座標、ベクトル、線形代数(5 章、6 章)
■ 常微分方程式(4 章、7 章)
■ ベクトル解析(8 章)
http://www.gakushuin.ac.jp/~881791/mathbook/
「計算理論の基礎」で有名なMichael Sipser先生のP vs NP問題概論.
「P, NPってなに?」から始まり回路計算量やグラフ同型問題辺りまで一時間程度で話してる.
The History and Status of the P versus NP Question
http://www.youtube.com/watch?v=3H0UxBF3kJg
Instructor: Erik Demaine
23. Computational Complexity
https://www.youtube.com/watch?v=moPtwq_cVH8
アルゴリズム
exacnt algorithms | ・厳密解法 ・厳密解アルゴリズム |
最適解を1つ求める解法 |
approximation algorithm | 近似解法 | 求められる解の精度に何らかの保証があるもの |
heuristicn algorithm | 発見的解法 | 良いと思われる解を探索する解法。解の精度に保証は無い |
Exact Exponential Algorithms http://t.co/Xa3MoyTe の輪講をここのところ学生とやっている.指数時間アルゴリズムは結構素朴なアイデアが多いので学生も読んで理解がしやすく,達成感を感じやすい題材という気がする.
— Taisuke Izumi (@taizumi) 2012, 6月 8
Exact Exponential Algorithms
厳密指数時間アルゴリズム
http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-16532-0
Today most computer scientists believe that NP-hard problems cannot be solved by polynomial-time algorithms.
From the polynomial-time perspective, all NP-complete problems are equivalent but their exponential-time properties vary widely .
perspective (…な)考え方,見方 property (ものの)特質,特性 vary widely ばらつきが大きい
- Why do some NP-hard problems appear to be easier than others?
- Are there algorithmic techniques for solving hard problems that are significantly faster than the exhaustive, brute-force methods?
The algorithms that address these questions are known as exact exponential algorithms.
appear to (~に)見える;(~と)思われる significantly かなり,著しく,はっきりと exhaustive 徹底的な,余す所のない brute-force 腕力, [しばしば形容詞的に] 力ずくの《プログラムに工夫を凝らさず, 計算機の処理能力をたのむ》 address 〈問題などを〉扱う,処理する
The history of exact exponential algorithms for NP-hard problems dates back to the 1960s.
The two classical examples are Bellman, Held and Karp’s dynamic programming algorithm for the traveling salesman problem and Ryser’s inclusion–exclusion formula for the permanent of a matrix.
inclusion–exclusion(principle) 包除原理 permanent n次の行列式(determinant)はn個の項の積のn!個の項に適当な符号をつけた和として表される.符号をつけずに全部+にして加えた式はpermanentと呼ばれる.訳語はないが,強いて訳せば永久式である. http://www.geocities.jp/ikuro_kotaro/koramu/2042_e1.htm
The design and analysis of exact algorithms leads to a better understanding of hard problems and initiates interesting new combinatorial and algorithmic challenges.
initiate 〈…を〉始める,起こす,創始する
The last decade has witnessed a rapid development of the area, with many new algorithmic techniques discovered. This has transformed exact algorithms into a very active research field.
The last decade この10年間(2000-2010)
This book provides an introduction to the area and explains the most common algorithmic techniques, and the text is supported throughout with exercises and detailed notes for further reading.
The book is intended for advanced students and researchers in computer science, operations research, optimization and combinatorics.
optimization 最適化
巡回セールスマン問題入門 ppt file , (September 2000)
by 松井知己(東京大学)
http://homepage2.nifty.com/TOMOMI/POWER-POINT/
http://www.cs.tsukuba.ac.jp/~takahito/Gcourse/part2.pdf
最悪計算量が問題の入力ビット長の多項式では抑えられないアルゴリズムは指数時間アルゴリズム(exponential-time algorithm)とよぶ.つまり,ナップサック問題(2.1)に対する動的計画法は指数時間アルゴリズムである.
2014年2月大雪まとめ
ニュース
記録的大雪 路面凍結など注意
02月09日 06時43分
http://www3.nhk.or.jp/shutoken-news/20140209/5061383.html
発達した低気圧の影響で関東地方は記録的な大雪となり、東京の都心では45年ぶりに積雪が27センチに達しました。気象庁によりますと、低気圧が発達しながら東日本の南岸を進んだため、関東地方では8日から9日未明にかけて記録的な大雪となりました。
東京の都心の積雪は8日夜遅く、45年ぶりに27センチに達したほか、埼玉県熊谷市では60年ぶりに43センチに達しました。
千葉市では9日未明、33センチの積雪を観測し、昭和41年に観測を始めてから最も多くなりました。
午前6時の積雪は千葉市で32センチ、前橋市で31センチ、東京の都心で24センチ、水戸市で14センチ、宇都宮市で13センチ、横浜市で12センチなどとなっています。
沿岸部を中心に風も強まり、午前4時半ごろには羽田空港で22.1メートルの最大瞬間風速を観測しました。
関東甲信 記録的な大雪に
02月15日 07時39分
http://www3.nhk.or.jp/shutoken-news/20140215/5185254.html
気象庁によりますと、発達中の低気圧の影響で、関東甲信では広い範囲で雪が降り、各地で大雪になっています。東京の都心では一時、積雪が27センチと45年ぶりの大雪となった今月8日の記録に並びました。午前7時には22センチとなっています。た関東地方は日中の気温が10度前後まで上がる見込みで、雨や融雪による道路の冠水、低い土地の浸水や川の増水、それに土砂災害にも注意を呼びかけています。
東急東横線で電車衝突
東横線で電車追突 18人軽傷
02月15日 05時50分
http://www3.nhk.or.jp/shutoken-news/20140215/5259413.html
15日未明、川崎市にある東急東横線の元住吉駅で下りの電車に後続の電車が追突して、乗客18人が軽いけがをしました。
追突した電車の運転士は「電車に近づいたことに気付きブレーキをかけたが間に合わなかった」などと話しているということで、警察が詳しい状況を調べています。
15日午前0時半ごろ、川崎市中原区の東急東横線の元住吉駅で、止まっていた元町・中華街駅行きの8両編成の電車に後続の電車が追突し、追突した電車の先頭から2両が脱線しました。
この事故でいずれも乗客で男性8人、女性10人のあわせて18人がけがをし、病院に運ばれました。いずれも軽傷だということです。追突された電車に乗っていた27歳の男性は「元住吉駅に到着した際、『停車位置を行き過ぎたので戻ります』とアナウンスがあった。その後、電車は止まったままだったが、突然、強い衝撃を受けて停電になり、車内が真っ暗になった」と話しています。
警察によりますと、追突された電車はホームをおよそ30メートル行き過ぎていたということです。一方、追突した電車の運転士は「電車に近づいたことに気付きブレーキをかけたが間に合わなかった」などと話しているということです。東急東横線は大雪の影響でダイヤが乱れ、電車と電車の間隔が詰まっていたということで、警察は前の電車が停車位置を行き過ぎて止まったところに後続が追突したとみて、ATC=自動列車制御装置の作動状況を含め事故の原因を調べています。
東急電鉄の広報室は「けがをされた方には本当に申し訳なく、心からおわび申し上げたい。いまのところ、オーバーランについても追突についても原因はまったくわかっていない。雪の影響もあるかもしれないが車両や安全対策などあらゆる面から原因を究明し、再発防止策を検討していく。運転再開の見通しは立っていないが、一刻も早く復旧させるため全力で取り組んでいく。利用者にはご迷惑をおかけし、大変申し訳ありません」と話しています。
えっ前の電車に衝突して元住吉で足止め。あと1車両前に乗ってたら死んでたぜ、これ。・・・帰れない。。 pic.twitter.com/OroRkZYKma
— 井原 亮馬 (@ihr0712chelsea) 2014, 2月 14
東急電鉄東横線元住吉駅列車衝突事故の図解。
左側青の四角が横浜高速鉄道Y516編成,桃色の四角が東急電鉄5057編成。四角内は「車両番号(号車番号)」を示す。
めり込んだ7号車の外観部分はえぐれたようになっている。 pic.twitter.com/d8ddFe3gtP
— trysr_s (@trysr_s) 2014, 2月 14
Twitterで話題の写真
浅草寺のラストダンジョン感がすごい pic.twitter.com/Gb3Fh1pAJn
— たわけイヤァオ!@いざこくりつ (@fs_bigbang) 2014, 2月 8
東京駅がノスタルジック pic.twitter.com/lL8ZLmyfiN
— .N@ (@mypace29) 2014, 2月 8
二級河川「首都高速」 pic.twitter.com/vOLhMQjm9H
— macha(まちゃ) (@macha_aa) 2014, 2月 15