科目ナンバー

SE-IG2-8A31

履修条件・関連科目等

　1年次の「数学A、B」、「線形代数1、2」、「情報基礎数学」、「Cプログラミング初級、演習」の内容を十分理解していて欲しい。

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

　コンピュータを用いて問題を解くためのアルゴリズムやデータ構造について基礎的な概念や技法を学ぶ。情報工学科の２年次後期以降の様々な科目の基礎科目であり、計算機で問題を効率的に処理するためのアルゴリズム開発ができるようになることをめざす。

科目目的

　　数理情報学の基礎として位置づけられている科目であり，プログラム作成の上で最も基礎となるデータ構造とアルゴリズムの基礎を学び、解法を適切に選ぶための理論を身に付け、問題解決力を養う。また，解法やそれを選択した理由などを他者に説明できる能力も身に付ける。

到達目標

　計算量の概念、基本的なアルゴリズム、およびそれらのアルゴリズムを効率的に実現する基礎的なデータ構造を理解し、使いこなせるようになることを目指す。

授業計画と内容

第 1回　アルゴリズムと計算量
第 2回　基本的なデータ構造（配列、リスト、キュー）
第 3回　基本的なデータ構造（木、2分木、2-ヒープ）
第 4回　探索のアルゴリズム（線形探索、2分探索）
第 5回　木を用いた探索（2分探索木、平衡木）
第 6回　整列アルゴリズム（挿入ソート、選択ソート）
第 7回　整列アルゴリズム（比較を使ったソートの計算量，クイックソート）
第 8回　比較を用いた最良の整列アルゴリズム（ヒープソート、マージソート）
第 9回　比較を用いない整列アルゴリズム
第10回　グラフの定義とデータ構造
第11回　グラフの概念と性質
第12回　グラフの探索（深さ優先探索、幅優先探索）
第13回　強連結性
第14回　マッチング

到達度によって、講義の内容が変更されることがある。

授業時間外の学修の内容

その他

授業時間外の学修の内容（その他の内容等）

　講義内容を忘れないうちに、その週に講義された内容に含まれる例題や演習課題などを、自分で必ずノートに書いて解いてみることを勧める。例題を手作業で解くことによって、アルゴリズム内の場合分けの理由や構造を理解することができる。アルゴリズムを実現するプログラムを作成し、動作確認をするためには、このような作業ができることが必要である。講義内でも演習は行うが、授業時間外でもアルゴリズムの動作確認を行って欲しい。

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける／授業時間に限らず、manabaでフィードバックを行う

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

その他

授業におけるICTの活用方法（その他の内容等）

必要に応じて，Webexミーティング等を用いて双方向型の学び及び自主学習支援を実施する．具体的にはその都度指示する．

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

資料を講義で配布する。
参考書：Seymour Lipschutz著：渡邉　均 訳、マグロウヒル大学演習　離散数学、オーム社，改訂2版、3470円

その他特記事項

参考URL