序論（9月29日）

何を学ぶか？
基礎科学としての
計算機科学 – Computer Science
計算機科学Ⅰ
の考え方や手法，その重要性
システム情報科学研究院・情報学部門
瀧本 英二
計算機科学
スペースシャトル
エンジン
鉄腕アトム
人工知能
熱力学
主に自然が対象
• 「観測」に基づき，現象を法則化
• 法則が正しいことは決して証明できない
• 反例が発見されると法則は棄却される
手法：数式化
パターン認識
エネルギー変換
機械学習
素粒子・量子論
アルゴリズム
F=ma
・・・と信じる
物理的アプローチ
計算機科学とは？
物理学
すべての科学技術分野の基礎となりうる
N=I
物理の法則
？
計算の法則？
参考図書
• 「教養としてのコンピュータ・サイエンス」
渡辺 治 著，サイエンス社 （¥1,550+税）
• 「アルゴリズム・サイエンス：入り口からの超入門」
浅野 哲夫 著，共立出版 （¥2,400+税）
• 「アルゴリズム・サイエンス：出口からの超入門」
岩間 一雄 著，共立出版 （¥2,400+税）
CS的アプローチ
主に文字列で表現
• あらゆる問題を，関数の計算問題として形式化
• 問題を解くための効率の良い計算手順を設計
• 計算手順の正当性や効率化の限界は証明できる
手法：アルゴリズム化
主なテーマ
• 基礎科学としての計算機科学
• 情報と計算の表現
• アルゴリズムとその効率の重要性について
• 計算の限界について
• 問題の形式化，モデル化について
• 組み合わせ論や数論とかかわりについて
資料置場（整備中）：
http://www.i.kyushu-u.ac.jp/~eiji
e-mail: [email protected]
1
ウォームアップ
ウォームアップ
• そもそも「計算」とは？
• そもそも「計算」とは？
例１：プログラミングコンテストの課題
「円周率の小数点以下100桁までを求めよ」
例２：数学の未解決問題の真偽判定
「コラッツ-角谷予想が正しいか判定せよ」
writeln(‘3.141592653589793238462643383279
502884197169399375105820974944
592307816406286208998628034825
3421170679’);
はＯＫ？ インチキ？
プログラム１： writeln(‘true’);
プログラム２： writeln(‘false’);
任意の自然数 a に対し，
aが奇数 ⇒ a := 3a+1
aが偶数 ⇒ a := a/2
の操作を繰り返すと，
いつかは 1 になる
のどちらかは正しく計算している？
ウォームアップ
ウォームアップ
• そもそも「計算」とは？
• そもそも「計算」とは？
例３：紐とおもりを使った計算
「閉路のない道路地図における最長の道」
例３：紐とおもりを使った計算
「閉路のない道路地図における最長の道」
以下の方法は，アルゴリズムと呼べる？
以下の方法は，アルゴリズムと呼べる？
1. 紐とおもりを使って道路地図を工作
2. どこか１つの頂点を持って，ぶら下げる
3. 一番下の頂点を持って，ぶら下げる
1. 紐とおもりを使って道路地図を工作
2. どこか１つの頂点を持って，ぶら下げる
3. 一番下の頂点を持って，ぶら下げる
2
以下の方法は，アルゴリズムと呼べる？
1. 紐とおもりを使って道路地図を工作
2. どこか１つの頂点を持って，ぶら下げる
3. 一番下の頂点を持って，ぶら下げる
CS的アプローチの例
アセチルコリン受容体の
膜貫通領域を特徴付ける
アミノ酸配列とは？
これが
最長経路！
アセチルコリン受容体
蛋白質
細胞膜
[篠原，下園’93]
CS的アプローチの例
CS的アプローチの例
• 問題の一般化，抽象化
入力：
膜貫通領域のアミノ酸配列
PLGFVKVLQWVFAIFAFATCGSY
FFVTVAVFAFLYSMGALATYIFL
GPMLDFLATAVFAFMWLVSSSAWA
GLNTSVVFGFLNLVLWVGNLWFVF
YWVIHSITIPMLFIAGWLFVSTGLA
VLSSDIIILTITRCIAILYIYF
YILGIAGLFTIFSSFVFSTVVIHFL
ALPFFLLLIDLSRASALAKFALSSNS
膜非貫通領域のアミノ酸配列
KTGQAPGYSYTAANKNKGIIWGEDTLM
GGKHKTGPNLHGLFGRKTGQAP
PKKYIPGTKMIFAGIKKKTEREDL
NKNKGITWGEETLMEYLENPKKYIPGTK
GRKTGQAVGFSYTDANKNKGITWGEDTLME
KKIFVQKCAQCHTVEKGGKHKT
EKGGKHKTGPNLHGLFGRKTGQAEGFSYTD
KYIPGTKMIFAGIKKKSERADLI
あるなしクイズ
あ る
な い
コスタリカ共和国アラフエタ州
老いては子に従え
パンナコッタ１５８円
エイコサペンタエン酸
コンピュータサイエンス
アメリカ合衆国ユタ州
袖触り合うも多生の縁
フルーツタルト２５８円
ドコサヘキサエン酸
システムエンジニアリング
出力：２つの配列集合を分離する規則
答えはわかりましたか？
まだですか？
CS的アプローチの例
CS的アプローチの例
あるなしクイズ
あ る
コスタリカキョウワコク
アラフエタシュウ
オイテハコニシタガエ
パンナコッタ
ヒャククゴジュウハチエン
エイコサペンタエンサン
コンピュータサイエンス
あるなしクイズ
な い
アメリカガッシュウコク
ユタシュウ
ソデフリアウモタショウノエン
フルーツタルト
ニヒャクゴジュウハチエン
ドコサヘキサエンサン
システムエンジニアリング
あ る
コスタリカキョウワコク
アラフエタシュウ
オイテハコニシタガエ
パンナコッタ
ヒャククゴジュウハチエン
エイコサペンタエンサン
コンピュータサイエンス
な い
アメリカガッシュウコク
ユタシュウ
ソデフリアウモタショウノエン
フルーツタルト
ニヒャクゴジュウハチエン
ドコサヘキサエンサン
システムエンジニアリング
＊コ＊タ＊エ＊ の形をしている
3
CS的アプローチの例
CS的アプローチの例
入力：
膜貫通領域のアミノ酸配列
PLGFVKVLQWVFAIFAFATCGSY
FFVTVAVFAFLYSMGALATYIFL
GPMLDFLATAVFAFMWLVSSSAWA
GLNTSVVFGFLNLVLWVGNLWFVF
YWVIHSITIPMLFIAGWLFVSTGLA
VLSSDIIILTITRCIAILYIYF
YILGIAGLFTIFSSFVFSTVVIHFL
ALPFFLLLIDLSRASALAKFALSSNS
膜非貫通領域のアミノ酸配列
KTGQAPGYSYTAANKNKGIIWGEDTLM
GGKHKTGPNLHGLFGRKTGQAP
PKKYIPGTKMIFAGIKKKTEREDL
NKNKGITWGEETLMEYLENPKKYIPGTK
GRKTGQAVGFSYTDANKNKGITWGEDTLME
KKIFVQKCAQCHTVEKGGKHKT
EKGGKHKTGPNLHGLFGRKTGQAEGFSYTD
KYIPGTKMIFAGIKKKSERADLI
出力：２つの配列集合を分離する正規表現
膜貫通領域のアミノ酸配列
PLGFVKVLQWVFAIFAFATCGSY
FFVTVAVFAFLYSMGALATYIFL
GPMLDFLATAVFAFMWLVSSSAWA
GLNTSVVFGFLNLVLWVGNLWFVF
YWVIHSITIPMLFIAGWLFVSTGLA
VLSSDIIILTITRCIAILYIYF
YILGIAGLFTIFSSFVFSTVVIHFL
ALPFFLLLIDLSRASALAKFALSSNS
膜非貫通領域のアミノ酸配列
KTGQAPGYSYTAANKNKGIIWGEDTLM
GGKHKTGPNLHGLFGRKTGQAP
PKKYIPGTKMIFAGIKKKTEREDL
NKNKGITWGEETLMEYLENPKKYIPGTK
GRKTGQAVGFSYTDANKNKGITWGEDTLME
KKIFVQKCAQCHTVEKGGKHKT
EKGGKHKTGPNLHGLFGRKTGQAEGFSYTD
KYIPGTKMIFAGIKKKSERADLI
＊[RKDENQH][RKDENQH]＊ の形をしている
4