情報処理のWeb教科書―IPA情報処理試験対策のお供に！

情報に関する理論―形式言語と有限オートマトンの状態遷移図など

トップ 情報処理の知識体系 テクノロジ系 基礎理論 情報に関する理論

情報に関する理論として、形式言語と有限オートマトンの状態遷移図などの解説や演習問題をまとめています。

▲記事トップへ

目次

以下は目次リンクになります。

2. 符号理論
3. 文字の表現
5. 形式言語
6. オートマトン
9. AI
10. コンパイラ理論

もっと知識を広げるための参考
更新履歴

2. 符号理論

符号理論について見ていきます。

ハフマン符号化方式

ハフマン符号化方式は、発生確率が分かっている記号群を符号化したとき、1記号当たりの平均符号長が最小になるように割り当てる方式です。

詳細

3. 文字の表現

文字コードについて見ていきます。

文字符号化方式

文字符号化方式とは、読み方は「もじふごうかほうしき」。 英語で「character encoding scheme」、略して「CES」といいます。 文字とそれに割り振られた数値の対応をまとめたコード化体系のことです。 省略して符号化方式という場合もあります。

ASCIIコード

ASCIIコードとは、大文字小文字のアルファベット・数字・記号類・制御コードを7ビットで表現する文字コードです。

EUC

EUCとは、Extended UNIX Codeの略で、拡張UNIXコードといわれる文字コードです。 複数のバイト幅を用いて漢字のような膨大な数の文字でも扱うことができるようになっている文字コードです。

JISコード

JISコードとは、Japan industrial standardsの略で、ISOコードに片かなを考慮して日本で制定したコードです。 1バイト系(JIS X 0201)は7ビットの7単位コードと片かなも組み込んだ8ビットの8単位コードがあります。

JISコードの例

二つの文字“A”と“2”をこの順にJISコードで表すと次のようになります。

JISコードの例

2つの文字“A”と“2”をこの順にJISコードで表したものは、「01000001　　00110010」になります。

シフトJISコード

JISコードとは、文字の1バイト目を見るだけで漢字か半角英数字かわかる文字コードです。

Unicode

Unicodeとは、すべての文字を16ビット(2バイト)で表現し、1つの文字コード体系で多国語処理を可能にしようとする文字コードです。

UCS-2

UCS-2とは、Universal multi-octet Character Set 2の略で、ISO/IEC 10646（JIS X 0221）のBMP（Basic Multilingual Plane：基本多言語面）として採用され、1文字を2バイトで表現する文字コードです。

文字の表現に関連したIPA情報処理試験の過去問

以下では文字の表現に関連したIPA情報処理試験の過去問とその解説をまとめています。

5. 形式言語

形式言語は、プログラミング言語のように特定の目的のために意図的に作られた言語のことをいいます。

BNF

リンク先にBNFとはどのような記法かをまとめています。情報処理のBNFとはどんなものか理解したい、意味はもちろん、記法例や問題つきで解説されていると助かるという方におすすめのコンテンツです。

詳細

逆ポーランド記法

逆ポーランド記法について見ていきます。

ポーランド記法

ポーランド記法とは、演算子をそのオペランドの前(または後)に置く表記法をいいます。 演算子を後におく記法を逆ポーランド記法ともいいますが、単にポーランド記法ということも多いようです。 たとえば、「a＋b」は「ab＋」となります。

ポーランド記法は、評価の容易さと括弧などの区切りを用いずに式を一意的に表記できることなどから、言語プロセッサで利用されています。

逆ポーランド記法

逆ポーランド表記法とは、ポーランド記法の後置表記法のことをいいます。

逆ポーランド記法は、演算子を演算対象の後ろに記述する記法です。 たとえば、「A+B*C」という式の場合「ABC*+」というように、あるいは式Y＝(A－B)×CをYAB－CX＝と表記します。

逆ポーランド記法の例

ここでは、Y＝(A＋B)×(C－(D÷E))をポーランド記法で表してみる場合を考えます。 この場合、以下のように木で表現し、節から上に出るときにそこの記号を書いていくと便利です。

木を使ってポーランド記法に直す

最後に「Y＝」の部分を加えると以下が導かれます。

YAB＋CDE÷－×＝

逆ポーランド記法に関連したIPA情報処理試験の過去問

以下では逆ポーランド記法に関連したIPA情報処理試験の過去問とその解説をまとめています。

6. オートマトン

有限オートマトンの概念や状態遷移表、状態遷移図についてまとめていきます。

有限オートマトンとは

有限オートマトンとは、入力テープの記号を1つ読んでは、状態遷移表や状態遷移図に示されるモデルに従って状態を遷移します。

状態遷移図と状態遷移表

状態遷移図とは、状態の移り変わりを図で表したものです。 時間の経過や事象の発生に基づいて記述していきます。 なお、以下のように表形式で表す場合もあります。

文字列
空白数字符号小数点その他
　現　
　在　
　の　
　状　
　態　
 　a　
　b　
　c　
　d　 		　a　
　a　
　e　
　a　 		　b　
　b　
　b　
　e　 		　c　
　e　
　e　
　e　 		　d　
　d　
　d　
　e　 		　e　
　e　
　e　
　e　

有限オートマトンの状態遷移図の読み方

有限オートマトンの状態遷移図の読み方は、簡単です。

例えば、S1は初期状態を、S3は受理状態を表している場合に次に示す有限オートマトンが受理する入力例は1101になります。

【問3】有限オートマトン―平成21年春期応用情報技術者

S1⇒S2⇒S1⇒S3⇒S3

有限オートマトンの状態遷移表の読み方

例えば、以下の有限オートマトンの状態遷移図で110の入力をaから始めると、aが1の入力の場合、aの行の1の列にあるbに遷移します。

有限オートマトンの状態遷移表ー読み方１
01
aab
bcd
cab
dcd

そして、次の入力が1でbの行の1の列にあるdに遷移します。

有限オートマトンの状態遷移表ー読み方２
01
aab
bcd
cab
dcd

最後の入力は0でdの行の0の列にあるcに遷移します。

有限オートマトンの状態遷移表ー読み方３
01
aab
bcd
cab
dcd

最後にcになりました。aから始めましたが、b、c、dどこから始めても110の入力の場合cになります。

オートマトンに関連したIPA情報処理試験の過去問

以下ではオートマトンに関連したIPA情報処理試験の過去問とその解説をまとめています。

9. AI

AIとはをテーマに、AI（人工知能）の基本的な考え方、機械学習のwakeなど関連知識について見ていきます。

AI（人口知能）とは

AIとは、Artificial Interlligenceの略で人工知能と訳され1950年代の中頃から使われるようになった用語です。 AI（人口知能）の定義に関しては多くの見解が存在しますが、概ねのところ、知的な情報処理をコンピュータ上で実現するという点で一致しています。

AIの読み方

AIの読み方は「エーアイ」です。

Artificial Interlligenceの略

AIはArtificial Interlligence（アーティフィシャル インテリジェンス）の略です。

AIの研究テーマ

AI（人口知能）の研究テーマには機械学習やディープラーニングなど様々な分野があります。

AIの活用事例

たとえば、運転手が関与せずに、自動車の加速、操作、制御の全てをシステムが行うといった AI（人口知能）の活用事例が挙げられます。

AIロボット

身近な活用事例としては、犬型のAIペットロボットや会話するAIロボットが子供のおもちゃ、あるいは高齢者の見守りなどに活用されるようになってきています。

知的処理システム

知的情報処理システムは、人間が備えもつ知的な機能をコンピュータによって実現した情報処理システムです。 最も実用的なシステムとしては、自然言語インターフェース・パッケージやエキスパートシステムがあげられます。

知識工学

知識工学は、人間の知識をコンピュータシステムに埋め込むことでより高い機能および保守性を実現するのが目的とした学問です。 基盤科学として認知科学があり、知識ベースやエキスパートシステムなどに応用されています。

知識ベース

知識ベース（knowledge base）はナレッジマネジメントのための特殊なデータベースです。 知識の検索できるようにし、知識を組織化し、知識をコンピュータ上に集合させたものです。

エキスパートシステム

エキスパートシステムは、特定の問題に対して、専門家のような受け答えをする機械であり、人工知能研究から生まれたコンピューターシステムです。 1970年代に人工知能の研究者によって開発され、1980年代にわたって商業的に適用され、AIソフトウェアとして最初に成功を収めた形態です。

学習理論

学習理論は、科学や工学、情報学や社会学、文学や経済学、心理学や言語学など、多岐にわたる分野で活躍する理論です。

統計的学習理論・計算論的学習理論・情報論的学習理論、などがあげられ、機械学習の理論へのアプローチとなっています。

機械学習

AI（人口知能）における機械学習は、記憶したデータから特定のパターンを見つけ出すなどの、 人が自然に行っている学習能力をコンピュータにもたせるための技術です。

機械学習とAIの違い

機会学習は、AI（人口知能）という包括的な概念の中に含まれる概念です。

機会学習とディープラーニング

AIの概念に含まれる機械学習ですが、その機会学習に含まれる概念がディープラーニング（深層学習）です。

Weka

フリーの機会学習統合環境ソフトウェアにWekaがあります。 Wakeは、Waikato Environment for Knowledge Analysisの略でニュージーランドのワイカト大学で開発された機械学習（データマイニング）のオープンソースです。 ソースコードはJavaで書かれていて、GNU General Public Licenseでライセンスされています。

参考）Wekaの日本語情報、ダウンロード

Wakeの日本語情報とダウンロードについては、以下のURLにあります。

https://weka-jp.info/
https://weka-jp.info/how_to_start_weka/how_to_download/

ニューラルネットワーク

ニューラルネットワークは、脳機能に見られるいくつかの特性に類似した数理的モデルです。 入力層、出力層、隠れ層から構成され、層と層の間には、ニューロン同士のつながりの強さを示す重み「W」があります。

階層型ニューラルネットワーク

階層型ニューラルネットワークは、情報処理を行う単位であるユニットが複数の階層をなすように並び、入力層から出力層へ向かう1方向の信号伝達路である結合があるネットワークです。 層間結合はありますが、同一層内のユニット間の結合である層内結合はありません。

ディープラーニング

ディープラーニングとは、多層のニューラルネットワークによる機械学習手法です。 深層学習ともいいます。

大量のデータを人間の脳神経回路を模したモデルで解析することによって、 コンピュータ自体がデータの特徴を抽出、学習する技術です。

ディープラーニングの特徴

AIにおけるディープラーニングの特徴は、 ニューラルネットワークを用いて、人間と同じような認識ができるようにするという特徴があります。 人間の脳神経回路を模倣して、認識などの知識を実現する方法がディープラーニングです。

AIに関連したIPA情報処理試験の過去問

以下ではAI（人口知能）に関連したIPA情報処理試験の過去問とその解説をまとめています。

10. コンパイラ理論

コンパイラとは何か、コンパイラ理論、コンパイラによる最適化の仕組みついてまとめています。 無料でダウンロードできるc言語のコンパイラの紹介やコンパイラ言語とインタプリタ言語の違いなどをまとめています。

詳細

もっと知識を広げるための参考

更新履歴

更新履歴になります。

戻る

スポンサーリンク

情報処理の知識体系

各試験の問題と解説

ランダム出題・採点アプリ

プログラミング

スポンサーリンク

トップ / プライバシーポリシー

Copyright (C) 2010-2023 情報処理のWeb教科書. All Rights Reserved. Loarding…