アルゴリズム及びテューリング機械

アブラクサス・アイオーン @Abraxas_Aeon

「アルゴリズム」という語は９世紀のペルシアの数学者の名前アブ・ジャファール・ムハマド・イブン・ムサ・アル＝フワーリズミー（長ぇｗ）に由来するという豆知識。

TANI_Röhei@赭埴庵 @Taroupho

あれ、今日はエイプリルフールじゃない……？ RT @Abraxas_Aeon 「アルゴリズム」という語は９世紀のペルシアの数学者の名前アブ・ジャファール・ムハマド・イブン・ムサ・アル＝フワーリズミー（長ぇｗ）に由来するという豆知識。

アブラクサス・アイオーン @Abraxas_Aeon

？　RT　@Taroupho あれ、今日はエイプリルフールじゃない……？ RT @Abraxas_Aeon 「アルゴリズム」という語は９世紀のペルシアの数学者の名前アブ・ジャファール・ムハマド・イブン・ムサ・アル＝フワーリズミー（長ぇｗ）に由来するという豆知識。

エリザバス @jutaityu

アルしかとってないW RT @Abraxas_Aeon: 「アルゴリズム」という語は９世紀のペルシアの数学者の名前アブ・ジャファール・ムハマド・イブン・ムサ・アル＝フワーリズミー（長ぇｗ）に由来するという豆知識。

TANI_Röhei@赭埴庵 @Taroupho

@Abraxas_Aeon なるほど実話ですかｗ　了解しましたｗ

アブラクサス・アイオーン @Abraxas_Aeon

@Taroupho @jutaityu ちょｗ、つ、続けますw

アブラクサス・アイオーン @Abraxas_Aeon

アルゴリズムが“algorism”の代わりに“algorithm”と綴られるようになったのは“arithmethic”（算数）との連想が働いたからだろうといわれている。代数“algebra”という言葉は彼の本の表題『キタブ・アル＝ジャブル・アル＝ムカバラ』のアル＝ジャブルに由来。

アブラクサス・アイオーン @Abraxas_Aeon

こういう話だと下手するとエイプリルフールと見間違われるというｗ

アブラクサス・アイオーン @Abraxas_Aeon

アルゴリズムの「実例」それ自体は、アル＝フワーリズミーよりさらに以前から知られている。「ユークリッドの互助法」である。これはある任意の二つの数の最大公約数を求めるための系統的な手段である。

アブラクサス・アイオーン @Abraxas_Aeon

問題：42と60の最大公約数を求めよ。

ぷ @puripuripuripul

@Abraxas_Aeon 6

アブラクサス・アイオーン @Abraxas_Aeon

レスどうもありがとうございます、正解です。RT @lebesmann @Abraxas_Aeon 6 RT @Abraxas_Aeon 問題：42と60の最大公約数を求めよ。

アブラクサス・アイオーン @Abraxas_Aeon

解法：だいたい義務教育で習うのは、42と60をそれぞれ2で割る。42/2=21、60/2=30 21と30をそれぞれ3で割る。21/3=7、30/3=10、7と10には公約数が存在しない。よって、2*3=6、6がこの場合の最大公約数である。と、こういう感じになる。

アブラクサス・アイオーン @Abraxas_Aeon

しかしこの方法は実用的でない。たとえばこんな問題が出されれば、このやり方では非常に面倒くさい作業が必要になる。問題：399と741の最大公約数を求めよ。

ぷ @puripuripuripul

@Abraxas_Aeon 57

アブラクサス・アイオーン @Abraxas_Aeon

先ほどは失礼しました。引き続きどうもありがとうございます、正解です。　RT @lebesmann @Abraxas_Aeon 57 RT @Abraxas_Aeon 問題：399と741の最大公約数を求めよ。

アブラクサス・アイオーン @Abraxas_Aeon

こういう数字になると、ユークリッド互除法が実用的である。解法：741を399で割る。741/399=1余り342、399を余りの342で割る。399/342＝1余り57、342を余りの57で割る。342/57=6（ちょうど割り切れる）したがって、57がこの場合の最大公約数である。

エリザバス @jutaityu

@Abraxas_Aeon 57ですか？

樫尾キリヱ@ヘンな美魔女 @kassy_jpn

ほえー RT @Abraxas_Aeon: こういう数字になると、ユークリッド互除法が実用的である。解法：741を399で割る。741/399=1余り342、399を余りの342で割る。399/342＝1余り57、342を余りの57で Re http://ow.ly/19A31

@nanasi3119

@Abraxas_Aeon なんでこうなるんですか?驚きです。いや、自分で調べます。

@lebesmann

ユークリッド互除法による解法知ってると大学入試の整数問題に強くなれる。

アブラクサス・アイオーン @Abraxas_Aeon

@jutaityu 57ですｗ

アブラクサス・アイオーン @Abraxas_Aeon

@nanasi3119 どの数字でやっても不思議とそうなりますよーｗ。

エリザバス @jutaityu

こんな解法あるんですね。多分初めて知りました。RT @Abraxas_Aeon こういう数字になると、ユークリッド互除法が実用的である。

アブラクサス・アイオーン @Abraxas_Aeon

,@lebesmann @jutaityu @kassy_jpn @nanasi3119 みなさまおつきあいくださりありがとうございます。