![]() ![]() |
科目一覧へ戻る | 2025/03/27 現在 |
開講科目名 /Course |
データ構造とアルゴリズム/Data Structures and Algorithms | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
時間割コード /Course Code |
S1405850_S1 | ||||||||||||||||||||
開講所属 /Course Offered by |
システム工学部/Faculty of Systems Engineering | ||||||||||||||||||||
ターム・学期 /Term・Semester |
2025年度/Academic Year 第1クォーター/1Q | ||||||||||||||||||||
曜限 /Day, Period |
火/Tue 1 | ||||||||||||||||||||
開講区分 /Semester offered |
前期/the former term | ||||||||||||||||||||
単位数 /Credits |
2.0 | ||||||||||||||||||||
学年 /Year |
2,3,4 | ||||||||||||||||||||
主担当教員 /Main Instructor |
菅間 幸司 | ||||||||||||||||||||
科目区分 /Course Group |
_ | ||||||||||||||||||||
授業形態 /Lecture Form |
講義 | ||||||||||||||||||||
教室 /Classroom |
北1号館A101/北1号館A101 | ||||||||||||||||||||
開講形態 /Course Format |
|||||||||||||||||||||
ディプロマポリシー情報 /Diploma Policy |
|
教員名 /Instructor |
教員所属名 /Affiliation |
---|---|
菅間 幸司 | システム工学部(教員) |
授業の概要・ねらい /Course Aims |
コンピュータの普及により,専門教育を受けていない者がアプリケーションプログラムを使うことは普通の事となり,プログラミングをすることさえ特別な事ではなくなっている.このような時代にあって,より専門的なプログラミング技法を習得することは,情報工学を学ぶ者にとって基本的専門性を身に付けることを意味している. 本講義では,プログラムの表層構造ではなく,その本質的構造(アルゴリズム)と,アルゴリズムによって操作する対象が持つべき構造(データ構造)を設計する方法について学ぶ.これらを通じて,一貫性のあるプログラムを作成する能力,他者の書いたプログラムを読解する能力,プログラムの実行過程をシミュレートする能力を涵養する. この講義は,コンピュータを用いた情報処理の基礎と応用技術を習得するためのものであり,特に,高度な情報処理の基礎として,データ構造とアルゴリズムについて理解することを目標としている. |
---|---|
到達目標 /Course Objectives |
各種データ構造とその特性の理解 ,および各種アルゴリズムとその特性の理解が行えることを最低限度の到達目標とし,このレベルに達した者を合格とする.さらに具体的問題に応じてデータ構造およびアルゴリズムの使い分けが適切に行えることを次の到達目標に設定し,このレベルに達した学生を優と評価する. |
成績評価の方法・基準 /Grading Policies/Criteria |
小テスト(75%)及び演習課題(25%) 毎回の授業の始めに,前回までの授業内容の範囲について,小テストを行います. また,毎回演習課題を課しますので,次週の授業までに提出してください. |
教科書 /Textbook |
資料配布による |
参考書・参考文献 /Reference Book |
大槻兼資(著)「問題解決力を鍛える!アルゴリズムとデータ構造」講談社,ISBN978-4-06-512844-2 ※講義では使用しません |
履修上の注意 ・メッセージ /Notice for Students |
プログラミングを行う課題のためには,Windows PCにWSL2を用いたubuntuの環境,MACの場合はHome Brewの環境が構築されていることが必要.インストールができてない人にはやり方を指導する. |
履修する上で必要な事項 /Prerequisite |
- 充電済みのPCとイヤホンを持参してください. (毎回の講義の後半で行う演習は,動画を視聴しつつ取り組んでいただきます.) - 筆記用具と紙の持参を推奨します. (小テスト受験時に,あると便利です.) |
履修を推奨する関連科目 /Related Courses |
情報応用1A, 情報応用1B |
授業時間外学修についての指示 /Instructions for studying outside class hours |
本授業の授業計画に沿って、復習3時間を毎週行ってください。さらに、授業内容に関連する課題に関する調査・考察を含めて、毎回の授業ごとに自主的学修を求めます。 |
その他連絡事項 /Other messages |
この科目は、SIの「アルゴリズム設計A/B」と内容の重なりがありますので、重複履修はできません. |
授業理解を深める方法 /How to deepen your understanding of classes |
毎回,前回までの内容の理解度を確認する小テストを行う.また,講義時間内に演習問題を課す. 【「アクティブ・ラーニング」実施要項 ⑪】 |
オフィスアワー /Office Hours |
日時 月曜3,4コマ 場所 A515 |
科目ナンバリング /Course Numbering |
S60012J11100S211,S60012J11100T212,S60012J11100U210 |
実務経験 /Practical Experience |
無 |
No. | 回(日時) /Time (date and time) |
主題と位置付け /Subjects and instructor's position |
学習方法と内容 /Methods and contents |
備考(担当) /Notes |
---|---|---|---|---|
1 | 1(4/15) | アルゴリズムとその解析 | 導入,オーダー記法 | 菅間/PC使用 |
2 | 2(4/22) | 基本的なデータ構造 | スタックとキューとリスト | 菅間/PC使用 |
3 | 3(5/2) | ソーティング1 | 簡単なソーティングアルゴリズム(選択法,挿入法,バブルソート) | 菅間/PC使用 |
4 | 4(5/13) | ソーティング2 | ヒープソート,シェル法 | 菅間/PC使用 |
5 | 5(5/20) | ソーティング3 | 高速なソーティングアルゴリズム(マージソート) | 菅間/PC使用 |
6 | 6(5/27) | ソーティング4 | 高速なソーティングアルゴリズム(クイックソート) | 菅間/PC使用 |
7 | 7(6/3) | 集合と探索1 | 2分探索と木,2分探索木 | 菅間/PC使用 |
8 | 8(6/10) | 集合と探索2 | 平衡木(AVL木) | 菅間/PC使用 |
9 | 9(6/17) | 集合と探索3 | ハッシュ法,開番地法と連鎖法 | 菅間/PC使用 |
10 | 10(6/24) | 文字列パターン照合 | KMP法,BM法 | 菅間/PC使用 |
11 | 11(7/1) | グラフ1 | グラフ構造 | 菅間/PC使用 |
12 | 12(7/8) | グラフ2 | グラフの探索 | 菅間/PC使用 |
13 | 13(7/15) | 組み合わせ最適化1 | 動的計画法 | 菅間/PC使用 |
14 | 14(7/22) | 組み合わせ最適化2 | 分枝限定法 | 菅間/PC使用 |
15 | 15(7/29) | まとめ | 全体の振り返り | 菅間/PC使用 |