離散システム [J3][ハイ]

開講年度

2025年度

開講学期

前期

科目名

離散システム

授業種別

講義

科目名（英語）

Discrete Systems

授業情報(授業コード・クラス・授業形態)

A1800060 離散システム [J3][ハイ]

担当教員

真鍋義文

単位数

2.0単位

曜日時限

火曜3限

キャンパス

新宿　遠隔

教室

.、A-1161教室

学位授与の方針

1 基礎知識の修得 10 ％
2 専門分野の知識・専門技術の修得 80 ％
3 汎用的問題解決力の修得 10 ％
4 道徳的態度と社会性の修得 0 ％

具体的な到達目標

組み合わせ最適化問題に対して、分岐限定法・動的計画法・ヒューリスティックスを用いて解くことができる。与えられた言語を受理する有限オートマトン、プッシュダウンオートマトンの設計ができる。与えられた有限オートマトン、プッシュダウンオートマトンが受理する言語が求められる。与えられた言語を生成する文脈自由文法、正規文法、正規表現の設計ができる。与えられた文脈自由文法、正規文法、正規表現が生成する言語が求められる。

受講にあたっての前提条件

集合・写像・ブール関数・グラフ理論に関する基礎的知識を必要とする。

授業の方法とねらい

離散的な構造を持つシステムに関する解析・設計・最適化の理論と技術について学ぶ。
本講義の第１回ー第１３回はハイブリッドで実施する。希望する受講生は遠隔（同時双方向）での受講を許可する（事前申請不要）。

AL・ICT活用

クリッカー・タブレット等ICTを活用した双方向授業

第1回

授業形態

ハイブリッド

事前学習

集合・グラフ理論の復習を行う。

3.5時間

授業内容

離散システムとは：
離散的な構造を持つシステムの解析手法の概要を学ぶ。

事後学習・事前学習

言語・語に関する基本的な定義を復習する。

3.5時間

第2回

授業形態

ハイブリッド

授業内容

有限オートマトン：
有限オートマトンの定義および有限オートマトンが受理する言語について学ぶ。

事後学習・事前学習

有限オートマトンの定義の復習を行う。

3.5時間

第3回

授業形態

ハイブリッド

授業内容

有限オートマトンの構築：
与えられた言語を受理する有限オートマトンの設計法を学ぶ。

事後学習・事前学習

有限オートマトンの構築法の復習を行う。

3.5時間

第4回

授業形態

ハイブリッド

授業内容

正規表現：
正規表現の定義および正規表現が表す言語について学ぶ。

事後学習・事前学習

正規表現の復習を行う。

3.5時間

第5回

授業形態

ハイブリッド

授業内容

プログラミング言語の正規表現：
プログラミング言語で使われる正規表現について学ぶ。

事後学習・事前学習

プログラミング言語の正規表現の復習を行う。

3.5時間

第6回

授業形態

ハイブリッド

授業内容

形式文法：
形式文法の定義および形式文法が生成する言語について学ぶ。

事後学習・事前学習

形式文法の復習を行う。

3.5時間

第7回

授業形態

ハイブリッド

授業内容

形式文法のクラス間の関係：
形式文法のクラスの定義、および有限オートマトンとの関係について学ぶ。

事後学習・事前学習

形式文法のクラス間の関係の復習を行う。

4時間

第8回

授業形態

ハイブリッド

授業内容

プッシュダウンオートマトン：
プッシュダウンオートマトンの定義およびプッシュダウンオートマトンが受理する言語について学ぶ。

事後学習・事前学習

プッシュダウンオートマトンの復習を行う。

4時間

第9回

授業形態

ハイブリッド

授業内容

計算量の理論（１）：ランダウの記号
オーダーの表記法および解析法を学ぶ。

事後学習・事前学習

オーダーの表記法の復習を行う。

4時間

第10回

授業形態

ハイブリッド

授業内容

計算量の理論（２）：NP完全性
NP完全性の定義とその意味について学ぶ。

事後学習・事前学習

NP完全性の復習を行う。

4時間

第11回

授業形態

ハイブリッド

授業内容

ヒューリスティックアルゴリズム：
焼きなまし法などのヒューリステッィクアルゴリズムの概要を学ぶ。

事後学習・事前学習

ヒューリスティックアルゴリズムの復習を行う。

4時間

第12回

授業形態

ハイブリッド

授業内容

分枝限定法：
組み合わせ最適化問題を解くための分枝限定法を学ぶ。

事後学習・事前学習

分枝限定法の復習を行う。

4時間

第13回

授業形態

ハイブリッド

授業内容

動的計画法：
組み合わせ最適化問題を解くための動的計画法を学ぶ。

事後学習・事前学習

総まとめの復習を行う。

4時間

第14回

授業形態

対面

授業内容

学修到達度の確認（授業内試験）

事後学習・事前学習

試験でできなかったところの復習を行う。

4時間

第15回

授業形態

遠隔（オンデマンド）

授業内容

試験の講評・フィードバックを行う。

事後学習

試験でできなかったところの復習を行う。

3.5時間

成績評価の方法

筆記試験と毎回の講義中の課題提出で行う。

・筆記試験(A)：１００点満点でに行う。
・課題(B)：１−１３回目において毎回２０点満点で行い、合算する（２６０点満点）。

AとBを9:1の割合で評価した結果をA+,A,B,C,D,Fの６段階で評価し、D以上を合格とする。

受講生へのフィードバック方法

オンデマンド授業となる第１５回に、KU-LMS に全体の講評をアップロードする。

教科書

指定教科書なし

参考書

Michael Sipser著　「計算理論の基礎　原著第３版　１　オートマトンと言語」　共立出版

オフィスアワー

木曜日３限、新宿A-1572で行う。
上記以外については事前にメールでアポイントメントを取って実施。
メールアドレス：jt13455@ns.kogakuin.ac.jp

受講生へのメッセージ

実務家担当科目

実務経験の内容

通信会社の研究所での勤務の経験がある教員が、アルゴリズム研究の経験を活かし、効率的なアルゴリズムの構成について講義する。

教職課程認定該当学科

システム数理学科／情報科学科

その他の資格・認定プログラムとの関連

シラバス情報