計算機科学・理論計算機科学総合

計算機科学や理論計算機科学を扱うスレットですを ラムダ関数やブロック暗号等についてやり取りしていただければ幸いです 自分語りにつながるかもしれませんが、一応ハンドルをここに付けておきます

文系の当職には興味あるけど難しそうな学問ナリ 頭唐澤な当職にもわかりやすいサイトや動画あったら教えてほしいナリ

>>2 はいナリ 計算機科学は計算機を科学する立場からコンピュータを科学する学問ナリ 故に情報数学を前提の解説が目立ちがちなこのスレではわかりやすいいところから掻い摘んでいきますを それではまず「計算とアルゴリズム」から紹介していきますを

計算機科学・理論計算機科学共に計算機を科学する立場上 物理的な「計算機」と仮想的な計算機として「計算模型」を扱っているナリ 一番わかりやすく言えば物理的な計算機はコンピュータや電卓で 計算模型は一般的に言えばプログラムですを 計算模型は紙と鉛筆で演算を行う他電子計算機(コンピュータ)の上でプログラムとして演算を実行させますを 当職の認識ですと、計算機が物理的なロジック回路で演算を行っていることに対し電子計算機は便器的表現上 「計算機の上で計算模型を動作させ複雑な演算を可能にしている」ことになるナリ

>>4 ここから重要ワードたる「計算可能性」の話てすを 計算機科学で言う「計算可能性」は「どのような対象が計算を遂行することができるか」を同定することですを 1から10までの数字を処理する特定の関数「f」が存在した場合、その関数を動かす為には ``` f(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) ``` と数字をセットすれば動くことになっているナリ（課程の話てすを） そして関数fが処理を遂行できるのは1から10までの数字がセットされた時のみで、これを「計算可能な状態」 つまり計算可能性と言うナリ

>>5 そして関数は計算(処理)を遂行したからには必ず値を返し（定める）働きがありますを それを定める機械的な処理規則を「アルゴリズム」と表現するナリ

なんだこれはageだage！ アルゴリズムってそういう意味だったナリか ローカル変数とグローバル変数って何でふか？

それぞれ変数のスコープの一種でふ （わかってる人向け：以下の記述は静的スコープを前提とします。） 変数のスコープというのは平たくいうとその変数の寿命のことでふ グローバル変数というのはそのプログラムが開始してから終了するまでの寿命があり、ローカル変数というのはそれが関数内で定義されているならその関数が始まってから終了するまでが基本的な寿命でふ プログラムの中で同じ関数は何回でも呼び出すことができまふが、ローカル変数はそれぞれの呼び出しで生まれては死にゆくので呼ばれ方によって異なる値を持ったりしまふし、前の呼び出しでのローカル変数をあとの呼び出しから参照することもできません。 一方、グローバル変数は常に同じものが生きていまふので、別の関数でグローバル変数に保存した値を呼び出したりしてくることもできるわけでふ グローバル変数とローカル変数を使う小さなプログラムを書いて実際に動かしてみると理解が深まると思いまふ。あなたが情報工学科の学生だったら、コンパイラを自分で書いてみるともっとよいでふ

計算可能性理論の話題が出ているので、せっかくだから計算可能でない関数の例を紹介します。 貴職らはコンピュータがあるばっかりにインターネット上で自分語りをして破滅した高校生を知っているから、コンピュータがあればあらゆることが実現できてしまうと思っているかもしれませんが、実はコンピュータには絶対解けない問題があることが知られています。 具体的には、コンピュータのプログラムが計算を完了して停止するかどうかを判定するプログラムは書けないことがわかっています。大ざっぱにいうと、無限ループが起きるかどうかはやってみないとわからない（ことがある）ということです。 証明は知っていればここに書ける程度には簡潔です。背理法で示します。 このようなプログラムHが存在するとしましょう。つまりHはそれ自身の入力としてプログラムPとPに対する入力Iを受け取り、PにIを入力として与えた時に停止するならYes、停止しないならNoを返すプログラムです。この計算結果をH(P, I)と書くことにします。 ここでプログラムAを、入力としてXを受け取ったときH(X, X)=YesならばAは意図的に無限ループを起こし（つまり停止しない）、H(X, X)=Noならば適当な値を返して停止するものとします。 このとき、 [1] H(A, A)=Yesとすると、Hの定義からA(A)は停止するが、Aの定義からA(A)は意図的な無限ループを起こすはずであり矛盾します。 [2] H(A, A)=Noとすると、Hの定義からA(A)は停止しないが、Aの定義からA(A)適当な値を返して停止するはずでありやはり矛盾します。 以上からH(A, A)としてあり得る値が存在しないので、最初に仮定したHの存在が誤りであることが示されました。 コンピュータの話をしていたはずなのに突然数学の証明が出てきて驚かれた人もいるかもしれませんが、これが理論計算機科学と呼ばれる分野の特徴でもあります。実際、理論計算機科学の研究者は大学では数学科に所属していたりします。

計算可能性の話をしたら次は計算量理論がいいかな。みなさんよろしくお >>9で計算可能でない関数を紹介しましたが、証明で現れた具体的構成がそうであるように計算可能でない関数は結構変なものばっかりで、当職や貴職らが普段想定するような関数はだいたい計算可能です。 では計算可能関数であればなんでもコンピュータで解決できるのかというと、そうではありません。人間の寿命が有限だからです。コンピュータの計算には必ず時間を使いますので、計算可能であっても膨大な時間がかかるならそれは問題が解決不可能であるのと同じことです。 つまり、具体的にある問題をコンピュータで解こうとしたときにどれくらい時間がかかるかを知るのは非常に重要な問題のわけです。実際に動かしてみるのが一番確実ですが、動かしている間に人生が終わってしまってはそれこそ意味がありません。 ここでプログラムとその入力を見て計算時間の予想を立てる動機が生まれ、計算量理論はこの問題を解決するために発展しました。 多くのプログラムの実行時間は入力の大きさが重要な決定要因であるという経験則があり、計算量理論でもあるプログラムと入力に対してかかる時間をその入力の長さの関数で表現することが多いです。 抽象的な物言いになってしまったので具体的な例を出しましょう。 今、コンピュータとして1桁の足し算と掛け算をわかっている子共を想定します。これも椿森日東師のいうところの立派な計算模型です。計算量理論においては想定する計算モデルを固定するのが一般的です（暗黙のうちに現代のCPUのようなものを仮定することも多いです）。 この子共がn桁の整数同士の掛け算を筆算するとき、何回の掛け算をする必要があるでしょうか？ お互いの整数の各桁を掛け算する必要があるのでn^2回ですね。 ということは計算時間もおおよそnの2乗に比例しそうなので、たとえば5桁の筆算にこの子共が1分かかったとすると、4倍の20桁のときにはその16倍の16分くらい掛かりそうだということが予想できるわけです。 ランダウの記号とか P vs. NP とか計算量的安全性の話をしたかったけど長くなったので一旦ここまで。

昨日の続きですを 筆算の例では計算時間を見積もるのに使った掛け算の回数はわかりやすい形をしていましたが、ふつうはもう少し複雑な形をしていて、たとえばf(n) = n^3 + n^2のような計算量になることもありえます。 ところで、当職らが計算時間の関数を考えていた動機は大きなデータでプログラムを動かした時の実行時間を調べることでした。 今挙げたfを考えてみると、nが非常に大きいときはn^3の項が支配的となりn^2は無視してもよいことがわかります。n=10000の時を考えるとn^2はn^3の1万分の1しかないからです。 計算量理論においてはこういうときにランダウの記号を用いて関数の挙動を表現します。支配的な項だけを抜き出してf(n)はO(n^3)である、と言います。 このようにして計算量を表現すると、最初の動機だった計算時間の予測以外にもメリットがあります。 その1つは、プログラムが解こうとしている問題の難易度を比較できるようになるということです。ここでいう難易度とは、コンピュータで解くのに必要な時間として定義します。 ある問題を解くためのO(n^2)時間かかるプログラムが存在するなら、その問題の難易度はO(n^2)以下であると考えるのです。 「以下」がついているのがポイントで、O(n)のプログラムが存在していないのが人類が無能で発見できていないだけか理論的に不可能であるからかはわからないからです。 たとえば、掛け算問題については筆算のプログラムによってO(n^2)以下であることがわかりましたが、高速フーリエ変換を用いるとO(n log(n))時間で解けることが知られているので、掛け算問題の難易度はO(n log(n))以下ということになります。 やっと伏線張り終わったので次回で終わりの予定です。

ある問題を解くプログラムの計算量のOの中身が多項式になる問題のクラスをPといい、計算量理論では簡単な問題であるという扱いになっています。 これまではプログラムの実行環境としてシングルコア、つまり同時に1つの計算の流れしかないことを前提としましたが、これを無限個に増やしたときに多項式時間で解ける問題のクラスをNPといいます。 （たぶんこれはNPの正式な定義と等価のはずですが、自信がないです。計算機科学に強芋による補足を切に望む） Pに属する問題はNPにも属することに注意してください。無限にあるコアのうちの一つだけを使えばいいわけですから。 今説明したPとNPが実は同じであるかどうか？　はおそらく計算機科学で最も有名な未解決問題で、P≠NP予想と呼ばれています。 予想の名前から分かるように、多くの専門家はこの2つは異なる、つまりNPには属するがPには属しない問題があると考えています。 NP完全と呼ばれるNPのなかでは最も難しい問題のクラスがあり、これが1つでも多項式時間で解けるとP=NPが証明できます。 NP完全問題には実用上重要な問題も多くあり、たくさんの研究者たちが高速化に励んできましたがこれらの問題が多項式時間で解けたとする報告が一切なかったことが≠説の根拠となっています。 ちなみに、この問題には100万ドルの懸賞金がかかっています。解けたとしたらお金よりも人類の歴史に名前を刻むであろうその栄誉の方がはるかにすごいと思いますが、 専攻選びに悩んでいる高校生たちがこれをもし見ていたら、こういう夢のある理論計算機科学なんかいかがでしょうか。

計算論的安全性の話が入れられなかったから延長戦です 前回の話だとP=NPであるほうが人類にとっては得であるように感じられますが、実はP≠NPでもそれほど嫌な思いはしません。 現代で広く用いられる公開鍵暗号であるRSAは、その安全性が「素因数分解が高速に解けないこと」に依拠しています。 この素因数分解が高速に解けないというのは、計算量理論の言葉で言い直すと「素因数分解がNP問題である」となり、P≠NPでないとむしろ困るということになってしまうのです。 このような暗号解読が計算量理論の問題として難しいことによる暗号の安全性を計算量的安全性と言います。 最後に計算量とアルゴリズムの話題を一般向けにわかりやすく説明した動画を紹介して、一連の計算量理論の講義（？）を終わります https://www.youtube.com/watch?v=Q4gTV4r0zRs

凄い大作やんけ 当職文系だからさっぱりなのが悔しぃ

当職としてはできるだけ前提知識を排して専門外の人に読んでもらおうと思ってたんですが、 やっぱりややこしい分野なのには違いないですかね…… たまに大学レベルの数学書の冒頭に「前提知識は必要なく、論理的思考力があればよい」と書かれていてそれは一面の事実なんだけれど、 実際に読み通すには数学の議論の仕方に慣れていてそれをきちんと追うためのトレーニングを受けてる必要がある、というようなことがここでも起きてしまった気がします。 もしさっぱりだったとしても最後の動画だけは見てほしいです。 計算機科学はコンピュータの限界を明らかにする学問であると思っていますが、そのよい例がわかりやすく説明されているからです。 計算時間という制約からどうしても難しくて答えが得られない（不可能側の限界）こともあるし、 アルゴリズムの改善でコンピュータでできることの範囲が押し広げられる（可能側の限界）こともあるのがわかると思います。

コテつけることにしました 名前はCPU設計で知られる計算機科学者デイビッド・パターソンから取っています 情報系の人にわかる言い方をすると「パタヘネ」の「パタ」です 世間で流行しているAIの中身、機械学習について何日かに分けて書きます AIと呼ばれるものがどういう問題を解いているか、 その問題をコンピュータがどうやって解いているかを説明してから 最後に機械学習の難しさや応用について軽く紹介する予定です みなさんよろしくお

>>16 よろしくお

見てますを 模試解説もよろしくお

新たな講師との出会いに感謝

5年ほど前から世間を騒がせるようになったAI技術ですが 具体的にこれはなんなんでしょうか？ 結論からいえばAIという単語はビジネスであまりに都合よく用いられてしまい 文脈なしにそれが何を指しているか判定するのは不可能になってしまいました 当職が考えている、近年AIと呼ばれているものの中身は次の4つです 単なる電子化/自動化: 紙でやってるものをパソコンでやればAI！ これ自体も重要ですがAIと呼ぶのは行き過ぎだと当職は思います ルールベースでの推論: 企業のカスタマーサポートについてるチャットボットとか。キーワードに反応してそれらしい答えを返している 探索アルゴリズム: バイトのシフトを自動で組むやつとか。これはこれで奥深い分野ですが今回は説明しません 機械学習: 古くはスパムフィルタ、最近だと機械翻訳もこれ 最後に挙げた機械学習がここ数年のAIブームを支える技術であり、今回のメインテーマです。

機械学習が解いている問題はなにか、これは一言でいうと予測です つまり機械学習は今わかっている情報を入力してまだわからない情報を推測する技術です たとえば天気予報では今の気象観測データを入力として明日の天気を予測しますし 尊師の大好きな競馬だと出走馬のデータを入力としてレース結果を予測します 入力と出力の間に時間的な前後関係がある必要はなく スパムフィルタだとメール本文を入力としてそれがスパムであるかどうかを予測しています 機械学習、その中でも教師あり学習と呼ばれる最もポピュラーな枠組みでは、 すでにわかっている入力と結果のペアを大量に収集・分析してそれらの間にある関係を推測することで予測を実現しています 競馬だったら過去のレースにどの馬が出走して誰が勝ったのかわかっていますから このペアを大量に分析すれば勝つ馬の法則がわかってくるというわけです 次回でこの分析と呼ばれるプロセスが具体的にどうなっているのか見ていきます

今回はちょっと数学力が必要になってしまいました。苦手な方は細かい議論を飛ばしてください 機械学習の「学習」とは具体的にどういうことをやっているのでしょうか 今回は最も単純な機械学習モデルとみなせる線形回帰を例に説明してみようと思います 線形回帰は入力と結果の間に線形な関係があるときに使えるモデルです 入力が1変数xなら結果yはパラメータaとbをつかってy=ax+bと書けると仮定します aとbは未知なんですが、これを大量の過去のデータから推定することを学習と呼びます 抽象的で難しいと思う方は具体的問題として次の問題をイメージしてください （問題） xをチンフェ特定からの日数、yを1日に神聖六文字が書き込まれた個数する 過去の書き込み履歴からx,yの組がたくさんわかっているとして 20年後（x=7300）にはどれくらい殺害予告されるかを推定したい

推定手法にもこれまたいろいろあるのですが今回は一番単純な最小二乗法を説明します 最小二乗法ではa,bとしてありうる値のうち過去のデータにもっともよく当てはまるもの採用します 当てはまり具合は、ある入力と結果の組(p, q)が1つあったとき予測式と実際の値の差の2乗であると定めます。つまり(q - (ap+b))^2です この誤差をすべてのデータについて足し合わせた値はa,bの2次多項式です（p,qは全部すでに与えられた定数であることに注意） なので頑張って計算するとこの誤差の総和を最小にするaとbの値が決まります 未知のデータxが来たときには得たa,bを使ってax+bを予測として出力します 数学苦手な人向け: 高校数学に毛が生えたくらいの計算で過去のデータに最もよく当てはまる予測式が得られます 知識のある貴職の中にはディープラーニングという言葉を聞いたことがあると思います これは上の説明で言うと線形回帰と同じカテゴリの技術で、 イメージとしては線形回帰の式がめちゃくちゃ複雑になったものです あまりに複雑なので係数の推定が非常に難しかったのですが、 10年ほど前に研究でブレイクスルーがありこれが最近のAIブームのきっかけになりました

>>23 当てはまり具合として定めた値は小さいほど当てはまりがよいです 次の行ではちゃんと誤差と呼んでいるのですが明確に説明し忘れました 当職 無能 全身唐澤貴洋

その教師あり学習をつかえばコンピュータで何でも予測できるようになるんでしょ？ というとそんなことはまったくないです。もしそうなら今頃競馬はAIに荒らされて完全にオワコンになっていると思います 実際に利益の出るAIはありますが、作るのが非常に難しく広く普及していないおかげでギャンブルとして成立しています。よかったね尊師 機械学習を難しくしている要因は本当にたくさんあるんですが、今日はその1つである過学習について説明します 実際の学習の過程では訓練データに対する精度を高めていることはすでに説明しました 入力と結果の間にある関係を学習することで既知のデータにも未知のデータにも対応できると期待されるからです しかし、入出力間の関係を学習するよりも訓練データに対する精度を高める方法があります それは訓練データを暗記してしまうことです この方法だとたしかに訓練データに対しては完璧に正解できるようになりますが、入出力間の関係は全く獲得できないので 本番、つまり未知のデータに対しては全く役に立たなくなってしまいます この現象を過学習といいます。モデルのパラメータ（係数）に対して学習データが少なすぎると起きるとされていますが、これ以外の要因もあるようです。 過学習を回避する技術は非常に重要で今も活発に研究されています https://inter-concierge.net/test/read.cgi/whitenighit/1624206661/99 これは人間が過学習を起こした例と言ってよいと思います 機械学習は人間の学習にもフィードバックがあるような知見が多くあって、勉強していておもしろいです

機械学習でシミュレーション結果を高速に予測、車の空力解析が数日から数分へ(MONOist) #Yahooニュース https://news.yahoo.co.jp/articles/7cb66ccb1975aaaa7066d54c746945c2c9dff76c 実際に車を何度もテストしなくともこうやって予測できるってのは凄いナリ でもテストの気候や湿度、路面の状況によってだいぶ変わると思うがどうやって学習させているんでしょうか？

>>26 > 従来のCAEを用いたシミュレーション工程にかかる時間を大幅に短縮 とあるので、CAE（計算機援用工学; ウィッキを見ると有限要素法などに言及があるので物理シミュレーションをしているのだと思います）では すでに実際の車を使わずともシミュレーションが可能なのでしょう 記事で紹介されている技術は、このCAEによるシミュレーションだと遅すぎるので過去に蓄積したCAEの結果を使って シミュレーションの結果を予測する機械学習モデルを作るもののようです 基本的には物理シミュレーションより機械学習による予測の方が圧倒的に速いので（そのかわり精度が犠牲になる）こういうことが可能です

なぜPythonは機械学習に向いているのか？

機械学習用のライブラリが豊富に存在するからです なにか機械学習のプロジェクトをやろうと思ったときに他の言語では論文や教科書を読んで コードに落とし込む必要があるところPythonなら既存の実装が利用できるのであれば普通はPythonを選択します 言語の設計自体が機械学習に向いているということはないと思います 機械学習は学習時に膨大な計算を必要とするので処理速度が重要ですが この点でPythonは処理速度をあまり考慮しない設計やGILの存在によって不利ですらあります C言語やFortranで書かれた高速な数値計算ライブラリとの連携で補っているという印象です

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱

知恵熱