「応用数学」カテゴリーアーカイブ

【基本情報・応用情報】
確率・統計の計算、分析手法を習得し、応用する。
数値解析、グラフ理論、待ち行列理論など、数学的原理を習得し、応用する。

【ITパスポート】
確率と統計の基本的な考え方を理解する。

応用数学とは

応用数学とは

応用数学(おうようすうがく、英語:applied mathematics)とは、数学的知識を他分野に適用することを主眼とした数学の分野の総称である。

Wikipediaから引用

情報処理技術者試験において、『応用数学』では、確率・統計の計算や分析手法を理解し活用すること、数値解析、グラフ理論、待ち行列理論などの基本的な数学的原理を理解し活用することが求められています。

情報処理技術者試験での学習内容

【基本情報・応用情報】
確率・統計の計算、分析手法を習得し、応用する。
数値解析、グラフ理論、待ち行列理論など、数学的原理を習得し、応用する。

【ITパスポート】
確率と統計の基本的な考え方を理解する。

(1)確率と統計 ITパスポート 基本情報 応用情報

1.確率

順列、組合せ、場合の数、確率とその基本定理、確率分布(離散型、連続型)と期待値、マルコフ過程を理解する。

用語例:階乗、加法定理、乗法定理、正規分布、ポアソン分布、指数分布、カイ二乗分布、確率密度

2.統計

度数分布表、ヒストグラム、代表値、ばらつき、相関関係、回帰直線、分散分析、検定など統計分析の手法を理解する。

用語例:中央値(メジアン)、最頻値(モード)、平均値、標準偏差、分散、相関係数、推定、回帰分析、帰無仮説、有意水準、カイ二乗検定

(2)数値計算 基本情報  応用情報

連立一次方程式の解法など、数値計算に関する基本的な内容を理解する。

用語例:行列、対数、掃出法、近似解法、収束、誤差

(3)数値解析 基本情報 応用情報

二分法、補間法、オイラー法など、近似解を数値的に求める考え方や計算過程で生じる誤差を理解する。

用語例: 数値積分、シンプソン法、ニュートン法、絶対誤差、相対誤差、丸め誤差、打切り誤差

(4)数式処理 基本情報  応用情報

コンピュータを用いて、数式を記号的に代数処理する数式処理システムとそのアルゴリズムを理解する。

用語例: 因数分解、微分、積分

(5)グラフ理論 基本情報  応用情報

グラフ理論の基本的な概念とその応用を理解する。

用語例: 無向グラフ、有向グラフ、完全グラフ、重み付きグラフ

(6)待ち行列理論ITパスポート 基本情報  応用情報

待ち行列理論の構成要素、考え方、M/M/1モデルにおける計算、乱数を利用したシミュレーションを理解する。

用語例: サービス時間、到着間隔、平均到着率、平均サービス率

(7)最適化問題 基本情報  応用情報

最適化問題とは何か、線形計画法、PERT、最短経路問題などの考え方を理解する。

用語例: 動的計画法

確率と統計(1)

この記事での学習内容 ITパスポート 基本情報 応用情報

順列、組合せ、場合の数、確率とその基本定理、確率分布(離散型、連続型)と期待値、マルコフ過程を理解する。

用語例:階乗、加法定理、乗法定理、正規分布、ポアソン分布、指数分布、カイ二乗分布、確率密度

場合の数

ある出来事が起きる可能性の数を「場合の数」と呼びます。場合の数で数えられる「ある出来事」は「事象」と呼びます。

例えば、サイコロを一個転がす場合を考えると、場合の数は6です。サイコロが2個になれば、場合の数は 6 × 6 で36です。

順列

箱の中に赤、青、黄の3種類の玉が1個ずつあるとします、この中から2個を選んで、順番に並べる場合、次の6通りの順番が考えられます。

1個め
2個め


この例のように、複数あるものから幾つかを選んで、順番を付けて並べる時の並べ方を「順列(Permutation、パーテーション)」といいます。n 個の中から r 個取って並べる順列を、nPr と表します。

順列の個数は計算で求めることが出来ます。
上の例では、1個めの玉の色は赤、青、黄の3通りあり、2個めは残りから取るので2通りあります。
1個めの3通りに続いて、2個めの2通りのとり方が並ぶと考えられるので、全部で 3×2=6 通りの順列となります。
同じ要領で、10個のうちから3個選ぶ順列は 10×9×8 = 720通りあります。

n 個の中から r 個取って並べる順列は、以下の公式で求められます。

nPr = n × (n-1) × ・・・× (n-r+2) × (n-r+1)

又は、階乗を使って、以下のような式でも表されます。

階乗とは、以下のように 値を n から 1まで、全て掛け算する計算のことです。

n! = n × (n-1) × ・・・× 2 × 1

公式を使って、10個の中から3つを選んで順に並べる順列を求めると、以下のようになります。

組合せ

複数あるものから幾つかを選んで、順番を付けずに一組にする時のまとめ方を「組合せ(Combination、コンビネーション)」といい、 n 個の中から r 個を取ってまとめる組合せを nCr と表します。

例えば、赤、青、黄の3種類の玉(1個ずつ)の中から2個を選んで組にする場合、「赤、青」「赤、黄」「青、黄」の3通りの組み合わせができます。
順列の場合と違い、「赤、青」と「青、赤」は同じ組み合わせとみなします。

組合せの数を求めるには、以下の公式のように、全体の順列を取った数の順列でわれば求められます。

公式を使って、10個の中から3つを選んだ組合せの数を求めると、以下のようになります。

確率

ある出来事が起きると期待できる割合を確立(Probability)といい、事象Aの起こる確率を P(A) と表します。

例えば、1個のサイコロを投げて、「1」の目が出る確率は次のように求めます。

  • 全ての目の数は1~6の6通り
  • そのうち、「1」の目は1つだけ

事象の排反

同時に起こりえない事象同士のことを、『事象排反する』という。

ベン図を書いた時に重なる部分がなかったり、論理積をとった時に解が空集合になる場合。

例えば、サイコロを振って『出目が2である』という事象と、『出目が3である』という事象は同時には発生し得ないので、事象が背反している。

が、『出目が2の倍数である』という事象と『出目が3の倍数である』という事象は、出目が6になったときに、ともに条件を満たすので、これらの事象は背反しない事になる。

事象の独立

二つの事象の発生確率を考えた場合、

  • 互いに影響しない→事象が独立している。
    例)サイコロを続けて振った場合の出目、ルーレットで特定の数字が出る確率など
  • 他方に影響を与える→事象が独立していない
    例)あたり数に限りのあるクジ引きで、1人目が当たる確率と、2人目が当たる確率。

*独立と排反の違い
独立している→互いに影響しない
背反している→同時に発生しない

確率の和事象(加法定理)

事象A又は事象Bが起こることを「和事象(A ∪ B)」といいます。
和事象の起こる確率は事象Aの起きる確率と事象Bの起きる確率を足したものから、事象AとBの積事象の確率を引いたものです。

例えば、サイコロを2回投げ、1回目に偶数の目が出る場合と、2回めに「2」が出る場合のいずれか、又は両方が起こる確率は以下のように求めます。

確率の積事象(乗法定理)

互いに独立した事象であるAとBがともに起こることを、事象AとBの積事象( A ∩ B)と言います。
積事象の起こる確率は事象Aの起きる確率と事象Bの起きる確率を掛けたものです。

例えば、サイコロを2回投げる時、1回目に偶数の目が出て、なおかつ2回目に「2」が出る確率は次のように求めます。

(参考)事象が独立していない場合に、事象Aが起きたという条件下で、事象Bが起きる確率は、以下のように求める。

マルコフ過程

時間とともに確率が変化する過程を「確率過程」と呼びます。例えば、降水確率は時間とともに確率が変化するので、確率過程とみなせます。
確率過程の中で、確率の値が過去の状態に一切関係がないものを「マルコフ過程」といいます。

例えば、サイコロを振り続ける場合にある目が出る確率過程を考えます。
現在のサイコロの目が出る確率は、過去のサイコロの目の影響を一切受けないので、マルコフ過程となります。
これに対して、降水確率は現在の降水状況に影響を受ける確率過程なのでマルコフ過程にはなりません。

  • 確率過程を取る例:株価、為替、電子回路に対するノイズの発生確率、降水確率など
  • マルコフ過程を取る例:サイコロ、ルーレット、宝くじの当選番号

確率分布

ある事象が起きる確率が変数によって決まる場合、変数と確率の関係を「確率分布」と呼びます。

例えば2個のサイコロを降る場合を考えます。

目の数の合計が2になるのは、1と1の場合だけなので、36分の1の確率です。
目の数の合計が3になるのは、1と2,2と1の2つの場合なので、18分の1です。
したがって、この場合は目の数の合計を変数とする確率分布が考えられます。

出た目の和23456789101112
確率1/362/363/364/365/366/365/364/363/362/361/36

なお、確率分布にはサイコロの目のように確率変数が離散的な値を取る場合と、連続する値を取る場合があります。

  • 離散型の確率分布:二項分布、ポアソン分布など(サイコロの目など、確率変数がとびとび)
  • 連続型の確率分布:正規分布、指数分布など(ある人の身長・体重など、確率変数の小数点以下をいくらでも細かく取れる場合)
ポアソン分布

単位時間中に平均でλ 回発生する事象が、ちょうど k 回(k は0を含む自然数)発生する確率をグラフに取ると、λ = k となる時にピークが来るようなグラフになる。

例:1時間に5人の利用者があるATMで、実際に1時間にATMを利用した人数の分布。

指数分布

単位時間中に平均でλ 回発生する事象が、「次に発生するまでの時間」の分布。

例:1時間に5人の利用者があるATMで、次にATMを利用する人が来るまでの時間の分布。

カイ二乗分布

独立に標準正規分布に従う k 個の確率変数 X1, …, Xk をとる。 このとき、統計量   の従う分布のことを自由度 k のカイ二乗分布と呼ぶ。この分布は自由度 k に応じて下図のような形をとる。

実際に様々な観測データを取得した場合、その分布には誤差が含まれるため、理論的に求められる分布と完全には一致しない。例えば、サイコロの各目の出る確率は1/6であるが、だからといってサイコロを6回振ったら各目が1回ずつ出るわけではない。フル回数を多くすればおおよそ1/6ずつに近い分布になると思われるが、均等に1/6ずつにはならない。

こういった時に「実際の観測データが理論値の分布にほぼ等しいとみなせるかどうか」を分析する際に、カイ二乗分布が用いられる。(この分析方法のことを「カイ二乗検定」とよぶ)

確率と統計(2)

この記事での学習内容 ITパスポート 基本情報 応用情報

度数分布表、ヒストグラム、代表値、ばらつき、相関関係、回帰直線、分散分析、検定など統計分析の手法を理解する。

用語例:中央値(メジアン)、最頻値(モード)、平均値、標準偏差、分散、相関係数、推定、回帰分析、帰無仮説、有意水準、カイ二乗検定

統計

ある集団に関するデータを集めてその分布を調べ、数値化して集計することを統計といいます。

統計を取り、様々な分析手法(表やグラフを活用する)を用いると、その集団の性質や特徴をつかむことが出来ます。

度数分布表

度数分布表は統計の基礎資料となるものです。

例えば、15人が受けた試験の得点を10点刻みで採点し、結果を次のようにまとめたとします。

上の表のように、データ全体の発生範囲をいくつかの階級に分け、それぞれの階級にデータがいくつ分布しているかを示す表のことを、度数分布表といいます。

ヒストグラム

ヒストグラムはデータ分布の状況を見るために作られる図解です。
度数分布表を棒グラフにしたもので、連続した数値を区分ごとに分けて、横軸の目盛とします。

ヒストグラムにおいて、それぞれの範囲に属するデータの件数を「度数」といいます。ある区分に集中してデータが分布する場合、その区分を中心とした山形のグラフになります。

正規分布

正規分布は、データが平均値を中心として+ーに対象に分布した状態のことです。

一般的に、ある事象について一定数以上のデータを抽出して統計と取ると正規分布になり、そのヒストグラムは左右対称の釣鐘型になると言われています。

ポアソン分布

ポアソン分布は、発生確率の低い事象で見られる確率分布です。
例えば、電話における単位時間中の着呼数、工場における不良品の発生数などがポアソン分布に従うと言われています。

単位時間中に平均でλ 回発生する事象が、ちょうど k 回(k は0を含む自然数)発生する確率をグラフに取ると、λ = k となる時にピークが来るようなグラフになる。

例:1時間に5人の利用者があるATMで、実際に1時間にATMを利用した人数の分布。

指数分布

指数分布は発生階数の低い事象で見られる確率分布です。指数分布は信頼度の計算などでよく使われます。(信頼度:機械の部品が故障しない確率)

指数分布はポアソン分布と関係していて、電話における単位時間内の着呼数がポアソン分布の時、着呼間隔は指数分布になります。

単位時間中に平均でλ 回発生する事象が、「次に発生するまでの時間」の分布。

例:1時間に5人の利用者があるATMで、次にATMを利用する人が来るまでの時間の分布。

カイ二乗分布

独立に標準正規分布に従う k 個の確率変数 X1, …, Xk をとる。 このとき、統計量   の従う分布のことを自由度 k のカイ二乗分布と呼ぶ。この分布は自由度 k に応じて下図のような形をとる。

実際に様々な観測データを取得した場合、その分布には誤差が含まれるため、理論的に求められる分布と完全には一致しない。例えば、サイコロの各目の出る確率は1/6であるが、だからといってサイコロを6回振ったら各目が1回ずつ出るわけではない。振る回数を多くすればおおよそ1/6ずつに近い分布になると思われるが、均等に1/6ずつにはならない。

こういった時に「実際の観測データが理論値の分布にほぼ等しいとみなせるかどうか」を分析する際に、カイ二乗分布が用いられる。(この分析方法のことを「カイ二乗検定」とよぶ)

統計の指標

統計の指標として、平均、メジアン、モード、レンジなどの値がよく用いられます。これらの値のことを「代表値」といいます。

代表値とは、多数あるデータの値を一つの数値で代表させた値です。

平均データの合計値をデータの個数で割った値
メジアン中央値。データを大小順に並べた時に中央の位置に来る値
モード最頻値。データ中に存在する個数が最も多い値
レンジ範囲。データの最大値と最小値の差

以下の度数分布表があった場合、各代表値は以下のようにして求めます。

平均

データの合計値:10+30+40×2+50×4+60×3+70×2+80+90 = 810
データの個数:15
平均:810 ÷ 15 = 54

メジアン

個々のデータを昇順(小さい順)に並べ、中央に来る値を見る。

中央に来る値は8番目の値なので、メジアンは50。

なお、集計データが偶数個のときはメジアンは2つの中央値の平均を使う。

例:10, 30, 40, 50, 70, 80 の6つのデータのメジアン
3番めと4番目が2つの中央値になるので、(40+50) ÷ 2 =45

モード

得点の中で出現度数が最も高い値は50 (4回) なので、モードは50

なお、最頻値が複数ある場合はそれら全てがモードとなる。

レンジ

得点の最大値:90
得点の最小値:10
レンジ: 90 – 10 = 80

散布度(ばらつきの度合い)

データの分布の特性は代表値だけでは表しきれません。
例えば、以下のようなケースで代表値として平均値を採用する場合、下記の2つのケースはどちらも平均値は10で変わりません。

  • ケースA:0,10,20
  • ケースB:5,10,15

しかし、データのばらつき度合いが異なります。このばらつきの度合いを示すのが散布度です。

代表的な散布度には分散と標準偏差があります。

分散は以下の式で求めます。

Σ( データの値ー平均値 )2

これに基づいて、先ほどの2つのケースの分散を求めます。

  • ケースA:0,10,20
    ( 0 – 10 )2 + ( 10 – 10 )2 +( 20-10 )2 =100 + 0 + 100=200
  • ケースB:5,10,15
    ( 5 – 10 )2 + ( 10 – 10 )2 +( 15-10 )2 =25 + 0 + 25=50

標準偏差

正規分布の形は、母集団の平均値と、母集団の分散から求めた標準偏差で決まります。

分散とはデータのばらつきを表す値で、標準偏差は分散のルート(√ )です。

平均をμ (ミュー)、標準偏差をσ (シグマ) と表すと、正規分布では約68%のデータが μ ± σ の範囲に収まり、約95%のデータが μ ± 2σ の範囲に収まります。
 

回帰直線

散布図(*1)のデータに、できるだけ一致する曲線を求める分析を「直線回帰分析」と呼びます。
直線回帰分析では、最小二乗法と呼ばれる方法が、一般的には使われます。
これは、実際のデータの値と、直線上の値の差の二乗が最小になる直線を求める分析方法です。直線は「傾き(*2)」と「y切片(*3)」と呼ばれる2つの値で定まります。

回帰直線は、実際のデータとは一致しません。データの分布によっては回帰直線と一致する度合いが大きかったり小さかったりします。
データの分布が回帰直線と一致する度合いを「相関」といいます。回帰直線に一致するほど「相関が強い」といいます。
相関の強さを数値で示したものが「相関係数」です。相関係数は-1~1までの値を取ります。

(*1)散布図:2つの属性値の相関関係を表したグラフ(例:身長と体重の相関など)

(*2)傾き:xが1増加した時のyの変化量を表す値。傾きがプラスの場合は右上がりの直線、マイナスのときは右下がりの直線となる。絶対値が大きいほど傾きは急。

(*3)y切片:直線とy軸の交点でのyの値。y切片が大きいほど、直線はグラフの上方に位置する。

標本調査

調査対象の件数が多い場合、対象全てを調査することが難しい場合があります。

このような場合には、調査対象の中から一部を取り出して調査を行い、全体を推定します。
このような分析を標本調査と呼びます。

例)テレビ視聴率、世論調査など

数値計算

この記事での学習内容 基本情報 応用情報

連立一次方程式の解法など、数値計算に関する基本的な内容を理解する。

用語例:行列、対数、掃出法、近似解法、収束、誤差

単項式、多項式、次数

単項式は、数値や文字の「掛け算」だけで造られた式のことです。2x や 3b などは単項式です。

多項式は単項式の足し算、引き算の形式で造られた式です。3x-2b と言った式が多項式の例です。多項式の中にある単項式は多項式の「項」と呼びます。

次数は、単項式の場合掛け算されている「文字の個数」です。3xy という式の場合、掛け算されている文字はx,y なので次数は2、x3 の次数は3となります。
多項式の場合は、一番次数の高い項の次数がその式の字数です。
x2+y という式の場合、x2 の次数2が一番高いので、この式の次数は2となります。

方程式、1次方程式

方程式とは、x , y といった「未知数」を含む等式のことです。未知数は「まだ分かっていない数」のことで、xやy といった文字で表します。

一次式とは、未知数の2乗以上を含まない式のことです。一元一次式は未知数が1つの一次式、二元一次式は未知数が2つの一次式です。

1次方程式とは、未知数の2乗以上の関係を含まない等式のことです。

連立一次方程式

連立方程式とは、同時に成立する複数の方程式です。方程式を組み合わせることにより、複数の未知数の解を求めることが出来ます。

連立方程式の名称は、未知数の数と次数によって決まります。

未知数の数が2個ならば2元連立方程式、3個ならば3元連立方程式となります。

つまり、連立一次方程式とは、複数の未知数を含む複数の1次方程式です。

連立一次方程式の解法

「連立一次方程式を解く」とは、与えられた方程式を全て同時に成立させる未知数の値を求めることです。数学の問題を解く方法のことを「解法」といいます。

連立方程式の解法には、加減法、代入法、等置法などがあります。連立一次方程式はこうした解法を用いて式を1元1次方程式の形にしていき、複数ある未知数を一つ一つ順番に確定していきます。

行列

行列とは、数学用語では、数値や変数を長方形に並べたものという意味になります。行列では横の並びを行、縦の並びを列と呼びます。下図の a , b , c , d などを行列の要素、あるいは成分といいます。

行列の要素を数値などで具体的に記述せずに、一般化して文字で表す場合、要素の右側に要素の位置を示す「添え字」を付けます。
上の図の「b12」であれば、最初の1は行番号、つぎの2が列番号を表します。

なお、行列の中で行数と列数が等しいものを「正方行列」といいます。

行列の和

行列同士の和は、各行列の同じ添字の要素同士を足し算します。
*下図では数値の右下に添え字を付けていますが、計算の説明のために例外的につけています。

行列の差

行列同士の差は、各行列の同じ添字の要素同士を引き算します。

行列の積

行列の積は、行方向と列方向を掛けたものを足して要素とします。行列の要素が1以外の場合、行列A×行列Bと行列B×行列Aの計算結果は異なります。

また、行列の積を「行列A×行列B」で求める場合、下図のように行列Aの列数と行列Bの行数が一致している必要があります。

例えば、行列Aが3行2列の行列だった場合、行列Bは2行n列でないと、積を求めることは出来ません。

行列による連立方程式の表記

連立一次方程式を行列の積を用いて表すことが出来ます。

対数

対数とは、ある数x は、ある数y を何回か掛け合わせた値であるとすると、そのかけ合わせた回数のことを言います。
数式で表すと、x = ya の a を「y を底とするx の対数」といい、 a = logy(x) と表します。
例)8 = 23 なので、log28 = 3

特に底を10とした対数のことを常用対数とよんでいます。

対数グラフ

通常のグラフでは、1, 2, 3, …と言うように、横軸も縦軸も順番に数が増えていきます。このようなグラフは少しずつ変化する値を描く場合などには有効です。

これに対して、2倍、4倍、8倍…と倍々で変化する値を描く場合などはすぐに縦軸が大きな値になって描けなくなってしまいます。

そこで、縦軸だけ対数を使うと、縦の変化量を抑えることが出来ます。このような、片側を対数としたグラフのことを「片対数グラフ」といいます。(両方対数としたグラフは「両対数グラフ」)

素因数分解

素数とは、1とその数自身以外に正の約数がない、1より大きな自然数です。

100以下の素数は、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 の25個です。

素因数分解とは、ある正の整数を十数の掛け算の形に分解することです。

例) 78 = 2 × 3 × 13

素因数分解にまつわる法則として、「2つの異なる素数p, q の積である、ある合成数Nが与えられた時、合成数N飲みから、元の素因数p, q を求めることは非常に困難」というものがあります。
この法則を利用し、安全性の根拠としている暗号化技術として、RSAという方式があります。

 

数値解析

この記事での学習内容 基本情報 応用情報

二分法、補間法、オイラー法など、近似解を数値的に求める考え方や計算過程で生じる誤差を理解する。

用語例: 数値積分、シンプソン法、ニュートン法、絶対誤差、相対誤差、丸め誤差、打切り誤差

数値解析とは、物理学、数学、工学などの科学分野の問題を、方程式を解くのではなく、数値計算を行なって解の近似値を求める手法のことです。

数値解析は、コンピュータを使った様々なシミュレーションなどに用いられています。数値計算、実用解析などとも呼ばれます。

二分法

二分法は、方程式の一つの実数の解を求める時に、解を含む区間を二分して中間点を求め、二分したどちら側に解が入るかを判定し、再度範囲を二分して判定する作業を、何度も何度も繰り返して、解の値を求めていく方法です。

方程式 f(x) = 0 の解を求める時に使用される代表的な数値解析方法の1つで、解のおおよその値を知っていることが前提です。

ニュートン法

ニュートン法は、グラフの形がなだらかに変化している場合に有効な方法です。

下図の様にグラフの形がなだらかな場合、ある値の接線とx軸の交点を取ると、もとの値より、グラフのx軸の交点に近づきます。
これを繰り返して、 f(x) = 0 の解を求める方法です。

補間法

補間法とは、グラフ上の複数の点を通る多項式の曲線で、xの値からyの値を計算することです。

補間法には何種類かの計算方法がありますが、代表的な方法として、ラグランジュ補間法やスプライン曲線などがあります。

ラグランジュ補間法

すべての点を通過する数式を求める方法。データの点数が増えると、曲線の振れ幅が大きくなってしまうという欠点がある。

スプライン曲線

ラグランジュ補間法の欠点を補うために、データを一定の区分で区切った上で、近似する曲線を予測していく方法。

誤差

数値解析で求めた解の値は、あくまでも近似値です。本島の海の値である「真値」との差があり、この差を「誤差」と呼びます。

数値解析の誤差には、絶対誤差、相対誤差、打切り誤差があります。

絶対誤差、相対誤差

真の値(真値)と測定値や近似値との差を誤差といい、この時
絶対誤差=測定値(近似値)- 真値
相対誤差=絶対誤差 ÷ 真値
となっています。

例えば、真値が1000mmで、測定値が998mmだった場合、
絶対誤差は、998 - 1000 = -2mm、
相対誤差は、 -2mm ÷ 1000mm = -0.02 = -2%
となります。

丸め誤差、打切り誤差

計算の結果を指定した桁数で収めるために、最下位の桁を切り捨て、切り上げ、四捨五入などをすることで生じる誤差を「丸め誤差」といいます。

また、計算を途中で打ち切ってしまう場合も真の値とは誤差が出ることになります。この途中で打ち切った時に出る誤差を「打切り誤差」といいます。打切り誤差の例としては、円周率の計算などがあります。

 

 

 

数式処理

この記事での学習内容 基本情報 応用情報

コンピュータを用いて、数式を記号的に代数処理する数式処理システムとそのアルゴリズムを理解する。

用語例: 因数分解、微分、積分

「数式処理」とは、数値の代わりに文字列を用いて計算式を記号的に処理することです。数値の代わりに用いる文字列を「代数」と呼びます。

具体的な例としては、計算式を分解して積の形に変換する「因数分解」、時間とともに変化する関数の増減を調べる「微分」、図形の面積や立体の体積などを微小な要素の集まりとして計算する「積分」などがあります。

コンピュータ内部でこのような処理を行うときには、数式処理を行います。

数式処理

コンピュータでは、代数を利用することで数式を記号的に処理することが出来ます。数値のみを扱う電卓とは異なり、コンピュータでは方程式をそのままコンピュータで扱うことが出来ます。

因数分解や、微分、積分の計算を行う際に、数式処理が行われっます。

因数分解

因数分解とは、下図や多項式・行列などといった計算式を分解し、因数(計算式)を積の形にすることです。

因数分解の公式
  1.  a2 ± 2ab + b2 =  ( a ± b )2
  2.  a2 – b2 = ( a + b )( a – b )
  3.  x2 + ( a + b )x + ab = ( x + a )( x + b )
  4.  acx2 + ( ad + bc )x + bd = ( ax + b )( cx + d )
  5.  a3 + b3 = ( a + b )( a2 – ab + b2 )
  6.  a3 – b3 = ( a – b )( a2 + ab + b2 )

微分

微分とは、時間の経過に伴って変化する関数の増減の度合いを求めることです。曲線のグラフでは、接線の傾きを求めることに相当します。

例えば、家から駅まで歩く場合を考えます。家から駅まで1時間かけて5キロの道のりを歩いた場合、時速5kmで歩いたことになります。
しかし、実際には常に時速5kmで歩いていたわけではなく、この時速5kmはあくまでも平均時速でしかありません。

このような場合に、実際の歩いた時間と移動距離をグラフに取り、とある時点での歩行速度を求めるような場合に、微分を用います。

なお、ニュートン法で接線の傾きを求める際にも微分が用いられています。

積分

積分とは、図形の面積や体積などを求める方法です。

長方形や三角形であれば公式を使えば面積を求めることが出来ますが、曲線のグラフの一部分のように、曲線で囲まれた部分の面積を求めるといった場合に、積分を用います。

例えば、先述の家から駅まで歩く場合をグラフにした時、横軸に時間、縦軸に速度を表したグラフの場合、積分を使うことで、一定時間に移動した距離を求めることが出来ます。

グラフ理論

この記事での学習内容 基本情報 応用情報

グラフ理論の基本的な概念とその応用を理解する。

用語例: 無向グラフ、有向グラフ、完全グラフ、重み付きグラフ

グラフ理論

点と点を結ぶ集合であるグラフの性質についての理論をグラフ理論といいます。(ここでいうグラフは、一般的な「グラフ」とは別物)

グラフとは、いくつかの接点(ノード)と呼ばれる点があり、それをある規則に基づいて結んだ線(枝:ブランチ)の集合です。
1つの接点(ノード)に付いている線(枝:ブランチ)の数を次数といいます。

現実世界の様々な要素を節点に置き換えて、その関係性を分析する際に使用されます。

鉄道の路線図などのように、節点同士の距離などに重点を置かず、節点同士のつながり方に重点が置かれます。
また、つながり方の向きを考えるグラフを「有向グラフ」、向きを考えないグラフを「無向グラフ」といいます。

グラフの次数

グラフの次数は以下のような特性を持っています。

  • すべての次数の合計は必ず偶数個になる。(ループしているノードは2本として数える)
  • 次数が奇数になるノードの数も必ず偶数個になる。

グラフアルゴリズム

グラフを探索するアルゴリズムで、探索の仕方によって幅優先順探索法と深さ優先順探索法があります。

幅優先順探索法

探索の優先順位を横方向にした探索法で、根から始め、左から右へ浅い方から探索します。

探索順は、節の数値が探索順となります。

深さ優先順探索法

探索の優先順位を縦方向にした探索方法です。探索の仕方によって、さらに3種類に別れます。

先行順

親→左の子→右の子の順で探索をします。

中間順

左部分木→親→右部分木の順で探索をします。

後行順

左部分木→右部分木→親の順で探索をします。

待ち行列理論

この記事での学習内容 ITパスポート 基本情報 応用情報

待ち行列理論の構成要素、考え方、M/M/1モデルにおける計算、乱数を利用したシミュレーションを理解する。

用語例: サービス時間、到着間隔、平均到着率、平均サービス率

待ち行列モデル

我々の生活の中では、銀行のATMや行政の窓口、商店のレジなど色々なところで行列が作られています。この待たされる行列のことを待ち行列と呼びます。この顧客がサービスを受けるために行列に並ぶ時の、待っている人の人数や待ち時間などを解析するための理論を待ち行列理論といいます。

この理論の中で、特に顧客とサービス窓口、待合室からなるシステムを「待ち行列モデル」として扱っています。

待ち行列モデルには種類がありますが、この種類を表す方法として、1953年にケンドール氏によって提案されたケンドール記号があります。ケンドール記号はA/B/Cという形式で表され、
A:到着時間の分布の種類
B:窓口を利用する時間(サービス時間)の分布
C:窓口の数
となります。

到着時間の分布の種類は、殆どの事象はランダムに到着するので、記号は M を使います。(マルコフ過程のM)

サービス時間の分布は、サービス時間が短い場合が多く、サービス時間が長い場合はそれほど多くないといった事象が一般的で、指数分布のグラフを取ります。

サービス時間の分布が指数分布に従っている場合は、記号はMと表します。

窓口の数は、ネットワークやCPUを待ち行列理論で扱う場合は、窓口が1つのモデルが良く使われます。

これに従って、銀行ATMや売店のレジなどの待ち行列モデルで、窓口が一つのモデルをケンドール記号で表すと、M/M/1となり、「M/M/1モデル」と呼ばれます。

M/M/1モデルでの計算

M/M/1モデルでの、平均待ち時間などを求めるための必要な計算式は下記のとおりです。

  • 平均到着率: λ (ラムダ)
    単位時間あたりに到着する顧客の数
  • 平均到着時間: ta (time arrival)
    ta = 1 / λ
  • 平均サービス率: μ (ミュー)
    単位時間に窓口が処理できる件数
  • 平均サービス時間: ts (time service )
    窓口における一人にかかるサービス時間
    ts = 1 / μ
  • 平均利用率: ρ (ロー)
    窓口をどれだけ利用しているかの割合で0~1の値。
    ρ = λ × ts または ρ = λ / μ
    ρが1以上になってしまう場合、到着時間よりも処理時間が長いことになり、待ち行列が延々と伸び、いつまでたってもサービスが受けられない状況を表します。
  • 平均待ち時間: tw (time wait)
    待ち行列に並んでからサービスが開始されるまでの時間
    tw = ρ / (1 – ρ) ×ts
  • 平均応答時間:T
    行列に並んでから、窓口でのサービスが完了するまでの時間
    T = tw + ts

例:とある行政の窓口で、1時間あたり10人の利用者があり、その窓口では1時間で15人の利用者に対応できる場合の平均待ち時間、平均応答時間を求める。

  1. 文章から、単位時間は1時間とし、λ = 10、μ=15となる。
  2. 平均サービス時間を求める。ts=1/μ なので、
    ts=1/15 (=4分)
  3. 平均利用率を求める。ρ = λ / μ なので、
    ρ = 10 / 15 = 2/3
  4. 平均待ち時間を求める。tw = ρ / (1 – ρ) ×ts なので、
    tw = (2/3) / (1 – 2/3) ×1/15 =(2/3) / (1/3) × 1/15 = 2 × 1/15 =2/15 となり、2/15時間=8分。
  5. 平均応答時間を求める。T = tw + ts なので、
    1 / 15 + 2 / 15 =3 / 15 となり、3/15時間=12分。

 

最適化問題

この記事での学習内容 基本情報 応用情報

最適化問題とは何か、線形計画法、PERT、最短経路問題などの考え方を理解する。

用語例: 動的計画法

最適化問題

制約のある中で、目的とする関数(目的関数)の解が最大(あるいは最小)となる値を求める問題を最適化問題といいます。

目的関数や制約関数によって幾つかの種類にわけられます。

線形計画法(LP法)

目的関数と制約関数が一次式(直線)で表現できる問題です。線形計画問題の中には、生産などで原材料の使用量などの制約のある中から、最大限の製品をいくつ作れるかを求める、線形計画法などがあります。

非線形計画法

目的関数あるいは制約関数が一次式でない場合の問題です。ニュートン法などの開放があります。

動的計画法

動的計画法は、問題全体を細かい部分問題に分割し、分割された問題の最適解を解いていくことによって、これらの結果を集めて全体の解を導く方法です。

例:最短経路問題。PERTのクリティカルパスを求めるのは動的計画法の一種。