目次 情報科学 I

  1. はじめに
  2. 古代メソポタミア、エジプト、インドのアルゴリズム
  3. イタリアの数学者
  4. ライプニッツとニュートン
  5. スイスのベルヌーイ一族
  6. オイラー、ガウス

松大授業用(2016)

情報科学I(前期)

テーマ
古代ギリシアの時代からアルゴリズムの原型は存在した。しかし、高性能 コンピュータの登場と普及により強大な力を発揮し始めたアルゴリズムが 社会を変革の世紀に突入させた。世界の金融取引の中心であるウォール街 において金融新商品が次々と誕生した背景にはアルゴリズムの存在が欠か せない。日常生活で欠かせなくなってしまったグーグルなどのウェブ検索 もアルゴリズムの応用である。映画や音楽のヒット予測もアルゴリズムが 活躍する舞台である。 このようなアルゴリズムの応用例を米国のテクニカル・ライターの著書 『アルゴリズムが世界を支配する』の前半を中心にして学習する。また、 アルゴリズムを動かすためのプログラムの初歩を学習する。これらの後半 は、情報科学IIに続く。

教科書
アルゴリズムが世界を支配する(角川EPUB) Kindle版

電子メールによるレポート提出

資料

テキスト第2章

  1. Y Combinator Hacker News
  2. アリヤバータ(476-550)インド数学者・天文学者
  3. ブラーマグプタ(598-668?)インド数学者・天文学者
  4. アブー=アブドゥラ・ムハンマド・イブン=ムーサ・アル=フワーリ ズミー ペルシャ数学者。 彼の名前からAlgebra, Algorithmの単語が生 れた。
  5. 中国 算木をつかった数学書『九章算術』紀元前千年頃
  6. フィボナッチ(1170頃 - 1250頃)イタリアの数学者
  7. パスカル(19 June 1623 - 19 August 1662)
  8. アイザック・ニュートン(25 December 1642 - 20 March 1727)
  9. ゴットフリート・ライプニッツ(1 July 1646 - 14 November 1716)
  10. "Explanation of Binary Arithmetic (www.leibniz-translations.com)", 1703
  11. ヤコブ・ベルヌーイ(6 January 1655 - 27 December 1654)、スイス数学者
  12. オイラー(15 April 1707 - 18 September 1783)、スイス数学者
  13. ガウス(30 April 1777 - 23 February 1855)、ドイツ数学者
  14. チャールズ・バベッジ(26 December 1791 - 18 October 1871)、数 学者、哲学者、プログラマブル・コンピュータの概念をはじめて考案し た機械工学の発明家
  15. ブール(2 November 1815 - 8 December 1864)、英数学者、哲学者、論理学者
  16. エイダ・ラブレイス(10 December 1815 - 27 November 1852)、英 数学者、世界で最初のプログラマー
  17. シャノン(30 April 1916 - 24 Feburary 2001)、米数学者、情報理 論の父
フィボナッチ数、黄金分割のプログラム ソース

Lua版

      function fib(n)
      return n < 2 and n or fib(n-1) + fib(n-2)
		 end

		 for i=1,10 do
		 print(fib(i))
		 end
    

Swift版

      func fibonacci(n: Int) -> Int {
	if n < 2 {
	       return n
	       } else {
	       return fibonacci(n-1) + fibonacci(n-2)
	       }
	       }

	       for i in 1...30 {
	       print(fibonacci(i))
	       
	       

Burlesq版

      1J{.+}10!C
    
Lua版 黄金分割比
      function fib(n)
      return n < 2 and n or fib(n-1) + fib(n-2)
		 end

		 for i=1,20 do
		 print(fib(i),fib(i+1),fib(i+1)/fib(i))
		 
    
ライプニッツによるデジタル・機械式計算機

164年ころに考案され、1694年に完成した。その独自に発明された四則計算の ための機構は、ドイツ語で「Staffelwalze」と呼ばれる階段状のドラムに仕掛 けがあった。英文の WikipediaStepped reckoner記事参照。この Leibniz wheelと呼ばれる1673年にライプニッ ツが発明した機械式計算機の仕掛けは1970年代中期に電卓が発明されるまで 300年間様々な国々で利用された。

19世紀はじめのころのドイツ、ゲーテ、ガウス、ワーグナー

文学、数学、音楽

ガウスによる復活祭の日付を計算するアルゴリズム

ガウスはさまざまな数学の分野に多大な貢献をした。整数論、非ユークリッ ド幾何学、楕円関数などである。また幼時から数字計算に秀でていた。幼時 すでに200以下の素数および素数羃の逆数を循環小数にした表を作成してい た。高木貞治の名著『近世数学史談』の45ページによれば、素数71の逆数を 小数にしたとき、

   1/71 = 0.01408450704225352112676056338028169 014・・・・
  

「一見すれば退屈な数字の行列であるが、実際割り算をして見るならば、…… …… 無限軌道の上を赱るようなものだから、面白くて循環節が終っても残り惜 しいほどに少年ガウスは感じたのではなかろうか。」

とある。皆さん、商の第2位からさきの 14084… を2分していけば、第8位か らさきの 07042… が自動的にでることに気がつきましたか?

さて、ガウスの伝記『科学の王者 ガウスの生涯』64ページに次のようなエピソード があります。「ガウス自身の話によると、母は彼が生まれた正確な日を教えること ができなかったという。彼女が覚えていたただ一つのことは、それはキリス ト昇天祭の8日まえの水曜日であったというだけである。これがもとで、ガ ウスは復活祭の公式を探索しはじめたのである。」

日本では、クリスマス、バレンタイン、ハロウィンに続いてイースター(復 活祭)を流行にしたい動きがあるのかどうかよくわかりませんが、クリスマ スなどと違って祝日が暦により移動するイースターは果して普及するでしょ うか。

ガウスの公式は、割り算と余りを求める算数が基本ですが、条件が少し複雑で す。詳細は、ウィキペディアで復活祭の項目を検索してみてください。それと、 ガウスの誕生日と昇天祭の関係でガウスの母の言葉を確かめてみましょう。

1821 - 1825 ガウスによるハノーバー王国の3角法による測量

『ガウスの生涯』、東京図書の119ページに掲載され たガウスによる測量図

Google Earthで見たゲッチンゲン、ハ ンブルグ都市周辺の図

3角測量の基礎

地点 A、B から地点Cを測量すると仮定する。AB間の距離がLと判っているとし よう。直線LからCまでの距離を求めることにする。このために地点Aから直線L を基準線にして地点Cへの角度を測定した結果がαとする。同様にして地点Bか ら地点Cを見る角度がβだったとしよう。

          C
          |
          |
          |
    /     | d= ?        \    
   /      |              \
  A_______|_______________B
                L

すると、L、α、βから、地点Cへの直線Lからの距離dを計算することができる。


  L = d/tanα + d/tanβ 


  d = L(sinα sinβ)/sin(α+β)
  
ガウスによる測量結果への最小二乗法の適用

省略

もう一つのプログラム言語 Forth

Android または Windows や Linux でForthを動かすには、アプリ gforth を 使う。

Forthによる数とアルゴリズムへの招待

iPhone用 Sketch Luaで上のアルゴリズムを動かす

教科書第3章 「映画とアルゴリズム」

数式処理とアルゴリズム

ネットのニュースを読む