「できない」を証明する利点　問題とアルゴリズムの相性を考える

「できない」を証明する重要性

他人から何かを要求されたとき、「できない」と人を説得するのは至難の業です。しかし不可能だとあらかじめ証明されていれば、すぐに納得してもらえるでしょう。
人間と同じように、コンピュータにもできないことが存在します。例えば解のない問題です。途中までは上手くできたとしても、解が出ないため必ず計算が止まってしまいます。解がとても少なくまた計算方法が明らかでない問題もあります。コンピュータで計算可能なのか否か、瞬時に判断できれば、実際に試す時間を削減することが可能です。そのためには問題の性質を分析し、相性のいい計算方法、つまりアルゴリズムが存在するのかを考えなければなりません。

試さなければわからない探索問題

数学にはひとつの解を短時間で導き出せる問題と、複数の答えの候補を順に試して答えを見つけていくものがあります。後者を探索問題といい、素因数分解や地図彩色が当てはまります。わかりやすくイメージするために白地図を思い浮かべてみましょう。日本地図に描かれた都道府県を色で塗り分けていくとします。ただし隣接する場所には必ず別の色を使わなければいけません。全部で何色あれば、すべての都道府県を塗り分けられるでしょうか。4色あればどんな地図でも塗り分けられると数学の定理がありますが、3色ならばできる場合とできない場合があります。3色で挑んだ場合、栃木県、茨城県、群馬県に別々の色を塗ると隣接する埼玉県を塗る色がなくなってしまいます。大規模な塗り直しをすれば塗り分けできるかもしれませんし、どう頑張ってもできないかもしれません。

簡単/難しいと統計力学

できる/できない、簡単/難しいの見通しを実は理論物理学が与えてくれます。違反ありきで構わないのでまず全ての県を塗り終えてしまいます。そこから少しだけ塗り方を変えた時、違反の数はどれだけ急激に変化するか。それを繰り返すことで見えてくる「デコボコさ」を使うと様子が見えてきます。

※夢ナビ講義は各講師の見解にもとづく講義内容としてご理解ください。

※夢ナビ講義の内容に関するお問い合わせには対応しておりません。

先生情報 / 大学情報

東北文化学園大学工学部知能情報システム学科講師中島千尋先生

興味が湧いてきたら、この学問がオススメ！

数学、理論物理学

メッセージ

現代はすぐに情報を手に入れることができるため、誰かの基準に沿って生き方を決めたり、適切な方法を絞って取り組んだりする道もあります。しかし自分なりの考えを見つけて、芯をつくるための活動に時間をかけることも大切だと思います。じっくり取り組むことが難しい世の中ではありますが、できる範囲で興味や関心を深めてください。
また、物理学は物質だけでなく、数学的な対象を考えるときにも応用できる学問です。もし興味があれば、柔軟な視点で発想を広げながら取り組んでみましょう。

先生への質問

先生の学問へのきっかけは？

東北文化学園大学に関心を持ったあなたは

東北文化学園大学は、仙台・国見の丘にキャンパスを持ち、医療・福祉・社会・経済・工学・情報の幅広い学びができる総合大学です。「実学教育」を教育理念に掲げ、専門職業人を育成する大学です。2021年４月から新しい学部を設置し、学際的な教育環境がさらに充実しました。また、「キャリアサポートセンター」の就職支援と相成って、例年高い就職率を誇り、卒業生は各業界で高い評価をいただいています。