シラバス参照

授業情報/Class Information

科目一覧へ戻る 2022/12/02 現在

基本情報/Basic Information

開講科目名
/Course
離散アルゴリズム特論/lgorithms for discrete mathematics
時間割コード
/Course Code
S221002008
ナンバリングコード
/Numbering Code
開講所属
/Course Offered by
理工学研究科/
曜日コマ
/Day, Period
火/Tue 2
開講区分
/Semester offered
前期/first semester
単位数
/Credits
2.0
学年
/Year
1,2,3
主担当教員
/Main Instructor
別宮 耕一/BETSUMIYA KOICHI
科目区分
/Course Group
大学院(博士後期課程) 安全システム工学専攻
教室
/Classroom
必修・選択
/Required/Elective
選択
授業形式
/Class Format
講義科目
メディア授業
/Media lecture

担当教員情報/Instructor Information

教員名
/Instructor
教員所属名
/Faculty/Department
別宮 耕一/BETSUMIYA KOICHI 理工学研究科/
難易度(レベル)
/Level
レベル5
対応するDP
/DP
DP1・DP2・DP3
授業としての具体的到達目標
/Concrete arrival target as the class
○数理構造、特に離散構造をもつ数理構造をコンピュータで処理するためのアルゴリズムを理解する。
○アルゴリズムを実際に活用して、離散構造に関する問題を解決する。
授業の概要
/Summary of the class
離散構造、組合せ構造をコンピュータで処理する際に、まず遭遇する困難はいわゆる「組合せ爆発」と呼ばれる現象である。これは離散構造、組み合わせ構造を扱う際に、考えられる場合の数があまりに巨大なため、それらを現実的な時間のなかでコンピュータで処理することが不可能になる現象をいう。暗号理論はこの現象を活用して情報を保護している。
こうした現象を回避して、コンピュータで離散構造や組み合わせ構造に関する問題を解くための効率のよいアルゴリズムが知られている。本講義ではそうしたアルゴリズムを解説する。
授業の内容予定
/Contents plan of the class
概ね、以下の内容で講義を行います。
第1回 ガイダンスと準備(基礎事項の確認)
第2回 多変数代数方程式
第3回 グレブナ―基底を理解するための準備
第4回 単項式順序
第5回 イデアルの基底
第6回 割り算アルゴリズム
第7回 多変数方程式の解法アルゴリズム
第8回 高速離散フーリエ変換
第9回 高速多倍長演算アルゴリズム
第10回 量子コンピュータの原理
第11回 量子回路モデル
第12回 量子フーリエ変換
第13回 素因数分解問題
第14回 素因数分解問題に対する量子アルゴリズム
第15回 まとめ
授業の進行状況により、シラバスと実際の内容と異なる場合には。その都度説明します。
成績評価方法及び採点基準
/A scholastic evaluation method and marking standard
数回の課題に対する得点の合計で評価する。
予習及び復習等の内容
/Contents such as preparations for lessons and the review
各回の講義で課される課題をこなすことを通して復習を行う。課題をこなすためには、各回の講義に対して、最低でも各1時間程度必要となる。
予習としては、次回扱う対象がどうしたらコンピュータで処理できるかを検討し、まとめておく。
教材・教科書
/The teaching materials, textbook
使用しない。
参考文献
/bibliography
講義中に適宜指示する。
留意点・予備知識
/Point to keep in mind, back ground
特になし。
授業内容に関する質問・疑義等
/Question, doubt about class contents
オフィスアワーの時間帯で受け付けます。金曜日16:00~17:00
Eメールアドレス・HPアドレス
/E-mail address, HP address
メールアドレスは次の通りです。ただし、Aは@に置き換えてください。
betsumiAhirosaki-u.ac.jp
学問分野1(主学問分野)
/Discipline 1
B12:解析学,応用数学およびその関連分野
学問分野2(副学問分野)
/Discipline 2
B11:代数学,幾何学およびその関連分野
学問分野3(副学問分野)
/Discipline 3
J60:情報科学、情報工学およびその関連分野
地域志向科目
/Local intention subject
なし
授業形態・授業方法
/Class form, class method
講義形式で行う。
科目ナンバー
/The subject number
メディア授業による著作物利用の有無について
/Whether or not copyrighted works are used in media classes
無/Nothing
その他
/Others
特になし。
No. 回(日時)
/Time (date and time)
主題と位置付け(担当)
/Subjects and instructor's position
学習方法と内容
/Methods and contents
備考
/Notes
該当するデータはありません

科目一覧へ戻る