「線形計画法」を含む日記

■線形計画法って高校数学でやったが

大学ではどんな風にやるの？なんの役に立つの？

Permalink | 記事への反応(0) | 06:28

ツイートシェア

■コンピュータ・サイエンスとは何か

コンピュータ・サイエンスで取り組まれている問題の一覧を紹介しよう。

計算複雑性

• P対NP問題
• BQPとNPの関係は？
• NC = P問題
• NP = co-NP問題
• P = BPP問題
• P = PSPACE問題
• L = NL問題
• 多項式階層 = PSPACE問題
• L = P問題
• L = RL問題
• ユニークゲーム予想
• 指数時間仮説は真か？強い指数時間仮説（SETH）は真か？
• 一方向関数は存在するか？公開鍵暗号は可能か？
• 対数ランク予想

特定のアルゴリズム問題における多項式時間と非決定性多項式時間

• 整数因数分解は古典（非量子）コンピュータで多項式時間で行えるか？
• 離散対数は古典（非量子）コンピュータで多項式時間で計算できるか？
• 格子の最短ベクトルは古典または量子コンピュータで多項式時間で計算できるか？
• グラフ同型問題は多項式時間で解けるか？
• グラフの正規化はグラフ同型問題と多項式時間で等価か？
• リーフパワーおよびk-リーフパワーは多項式時間で認識できるか？
• パリティゲームは多項式時間で解けるか？
• 二分木間の回転距離は多項式時間で計算できるか？
• 有界クリーク幅のグラフは多項式時間で認識できるか？
• 凸多面体上の単純閉準測地線を多項式時間で見つけることができるか？
• 与えられた2つのグラフに対して固定された辺を持つ同時埋め込みを多項式時間で見つけることができるか？
• 平方根和問題はチューリングマシンモデルで多項式時間で解けるか？

その他のアルゴリズム問題

• スプレーツリーの動的最適性予想：スプレーツリーは有界な競争比を持つか？
• 深さ優先探索木はNCで構築できるか？
• 高速フーリエ変換はo(n log n)時間で計算できるか？
• 2つのn桁の数の乗算の最速のアルゴリズムは何か？
• 決定論的で固定されたギャップシーケンスを持つシェルソートの平均ケース時間計算量の下限は何か？
• 3SUMは強い二次未満の時間、つまりO(n^{2−ϵ})時間で解けるか？
• 2つの文字列間の編集距離は強い二次未満の時間で計算できるか？（これは強い指数時間仮説が偽である場合にのみ可能）
• X + Yソートはo(n^2 log n)時間で行えるか？
• 行列乗算の最速のアルゴリズムは何か？
• 全対間最短経路は強い三次未満の時間、つまりO(V^{3−ϵ})時間で計算できるか？
• 多項式同一性テストのためのシュワルツ・ジッペル補題は非乱択化できるか？
• 線形計画法は強い多項式時間アルゴリズムを持つか？（これはスマイルの問題リストの問題#9）
• 嫉妬のないケーキカットに必要なクエリ数は何か？
• 最小全域木問題のアルゴリズム的複雑性は何か？同様に、MST問題の決定木複雑性は何か？MSTを計算するための最適なアルゴリズムは知られているが、決定木に依存しているため、その複雑性は不明。
• ギルバート・ポラック予想：ユークリッド平面のシュタイナー比は2/√3か？

プログラミング言語理論

• POPLmark
• バレンドレヒト・ギューヴァース・クロップ予想

その他の問題

• アンデラ・カープ・ローゼンバーグ予想は真か？
• チェルニー予想：n状態の決定性有限オートマトンが同期語を持つ場合、その長さは最大で(n-1)^2か？
• 一般化されたスター高さ問題：すべての正則言語は、限定されたネスト深さのクリーン星を持つ一般化された正則表現を使用して表現できるか？
• 単語の分離問題：2つの与えられた長さnの文字列に対して異なる動作をする決定性有限オートマトンに必要な状態数は何か？
• すべてのユニークな基本セルオートマトンのチューリング完全性の状態は何か？

Permalink | 記事への反応(0) | 15:26

ツイートシェア

■https://anond.hatelabo.jp/20230920031702

　　平成１５年の東大文系数学、入試当日に問題は出現するが、内容は、（１）積分計算（２）線形計画法（３）整数（４）確率、

　　　（１）は最後の計算の値が出ていないと途中経過が間違いであるので最後の値が合っていれば途中経過が正しいことが明らかである。

　　　（２）線形計画法が主題だが単なる場合分けの問題で特に目玉の問題ではなかった。（３）漸化式を立てていくらかの仮定を付加すると正当に到達する問題で

　　いくらかの仮定を立てることがポイントだった。（４）確率の応用問題。

Permalink | 記事への反応(0) | 03:27

ツイートシェア

■https://anond.hatelabo.jp/20220504095838

俺が東大文Ⅰに受かった2003年の数学の問題のセットは分析内容がありすぎた。　　第2問の線形計画法の問題はクソだったが

　　　１，３，４は冷静にみると、分析する事項が多すぎた。　俺は、４の確率はできなかったが、１，３を完答して合格した。

　　　　それに対して２００２年の数学があまりにもクソすぎた。

http://server-test.net/math/php_q.php?name=tokyo&v1=0&v2=2003&v3=1&y1=2003&n1=0_1&y2=2003&n2=0_2&y3=2003&n3=0_3&y4=2003&n4=0_4&y5=0000&n5=0&y6=0000&n6=0&y7=0000&n7=0

Permalink | 記事への反応(0) | 10:02

ツイートシェア

■大学で習ったこと

・制御工学

・最適化・線形計画法

・信号処理

・情報理論

・画像処理

・アルゴリズム

・オートマトン

・AI(GOFAI)

・遺伝的アルゴリズム

・ニューラルネットワーク

・統計

・経済学

・ゲーム理論

・プロジェクトマネジメント

強そうなんだけどなー。

内容が薄くて、実験もなかったからなー。

Permalink | 記事への反応(1) | 18:30

ツイートシェア

■anond:20180919164125

ボクも大学受験は私立文系型の勉強しかしていなかったので，大学にはいって数学をやり直しました．高校でちゃんとやっていないのなら，日本人が書いた教科書じゃなくてアメリカの大学学部の教科書（翻訳）がいいと思います．特に経済学用の数学の教科書がとっつきやすいかも（事例としても経済・経営問題がでてくるし）．古いですが私が学部生の時に使ったのは数学では次の2つです：

G.C.アーチボルド (著), リチャード・G.リプシー (著), 作間 逸雄 (翻訳)『入門経済数学 』(1) と(2), 1982/9

学生版でなく，練習問題の解答が附属している2分冊になっている通常版（コレ）が良いです．アマゾン中古で数百円で買えます．線形代数，微分積分，最適化問題，線形計画法等をカバーしています．

A.C. チャン (著), K. ウエインライト (著)『現代経済学の数学基礎〈上〉〈下〉』 単行本 – 2010/1/1

旧版なら，これもアマゾン中古で数百円で入手可．上の書籍がカバーしている項目のに加え，微分方程式と差分方程式が学べます．

あと確率・統計なら

T.H. Wonnacott, R.J. Wonnacott, Introductory Statistics for Business and Economics, 4th ed. 1990.

が定評のあった教科書で，私もコレに助けられました．これもアマゾン中古で数百円．

Permalink | 記事への反応(0) | 03:17

ツイートシェア

■ランド研究所の古典公開

ランド研究所というのはアメリカ空軍が設立したシンクタンクで、色々面白い研究をしている。

ゲーム理論とか線形計画法、動的計画法、帰納推論に正規表現、論理回路の縮約法、パケット交換ネットワーク、

RAND のレポートが先で、学術論文は後、そんな 1950 年代はアメリカの冷戦パラノイアいっぱい夢いっぱいの時代だった。

彼らがどうも昔のレポートを気まぐれに無料公開しているっぽい。2005年から毎年その数は増えている。半導体のスイッチング速度が10ギガの壁にぶちあたり絶賛停滞中のわれらが人類文明だけど、近過去に目を転じると、けっこーすげーじゃん、って気分になれるかもしれない。

試しに

site:www.rand.org/pubs/papers/2008/

とか

site:www.rand.org/pubs/papers/2005/

とか、年号を変えてぐぐってみよう！

追記：

site:www.rand.org/pubs/research_memoranda/2005/

とかもためしてみてね。ペーパーとメモの違いは正直よくわかりません

Permalink | 記事への反応(0) | 20:51

ツイートシェア