科目名[英文名]
アルゴリズム序論   [Introduction to Algorithms]
区分	工学部専門科目等	選択必修		単位数	2
対象学科等		対象年次	2～4	開講時期	前学期
授業形態	前学期	時間割番号	022805
責任教員 [ローマ字表記]
宮代 隆平   [MIYASHIRO Ryuhei]
所属	工学部	研究室		メールアドレス

概要

この授業では，実行速度が「速い」プログラムを書けるようになるための基本的な事柄を学んでいきます． まず，プログラムの速さとは，どのように定義されるのでしょうか． 速いCPUで動かしたらプログラムが速く動くのは当たり前ですが，ここでは「計算量」という概念を学び，与えられたプログラムに対して“そのプログラムの速度”を導けるようにします． これを学ぶことにより，コンパイル・実行すること無しにプログラムの速さ／遅さが判断できるようになります． またプログラムを書くための便利なツールである「データ構造」を学びます． 例えば，配列にクラス100人の身長が入力されている時，平均身長を出すのは簡単です． これを，配列を使わず全く別々の変数に身長が入力されていたらどうでしょうか． プログラムを書くのは極端に面倒になります． データ構造とは，複数のデータをまとめて扱う手法で，配列もその一種です． 配列は便利な道具ですが，他にもデータ構造はたくさんあり，それらをうまく使うとプログラムをシンプルに書くことができます． 実際に与えられた問題をプログラミングする際には，その問題をどのように解くかを自分で考えなくてはいけません． 問題を解く手順を「アルゴリズム」といいます． ソートなどのシンプルな問題に対しては，既にたくさんのアルゴリズムが提案されています． それらを知っておくことにより，複雑な問題に応用できるようにします．

到達基準

この授業が終わったとき，以下が達成されていることが目的となります． １．与えられたアルゴリズム（プログラム）を見て計算量（速度）を導けること ２．簡単な問題に対して，適切なデータ構造（配列を使うか，その他，…）を用いて速いアルゴリズム（プログラム）を作れること

授業内容

以下のキーワードを扱っていきます．（この他にも扱う事柄はあります） ・プログラムの速さ： オーダー，計算量 ・基本的なアルゴリズム： ソート，探索 ・基本的なデータ構造：配列，リスト ・続基本的なデータ構造およびそれを使ったアルゴリズム：スタック，キュー，ハッシュ，ヒープ 初回の授業では，成績の付け方などについても触れます．

履修条件・関連項目

特定のプログラミング言語を習得するための授業ではありませんが，必要な部分はC言語で解説します． 情報工学科1年次で開講された授業における程度のC言語の習得を前提とします． 他学科から履修を希望する学生に対しては，初回の授業でテストを行い，またレポートを課す． その結果により履修の可否を判定するので，初回の授業に出席すること．

テキスト・教科書

授業にて毎回プリントを配布します．

参考書

特に指定しませんが，より深く勉強したい場合は「データ構造」「アルゴリズム」などをタイトルにした参考書（たくさんあります）を参考にするとよいでしょう． 授業中にいくつか紹介する予定です．

成績評価の方法

「毎回の小テストの合計：レポート：期末テスト＝１：１：１」で採点します． 詳細は初回の授業にて説明します．

教員から一言

今後プログラミングをしていく上での基礎体力となる部分です． 毎回出席して，自分の手で小テストの問題を解いていきましょう．

キーワード

計算量，アルゴリズム，データ構造

オフィスアワー

授業終了時

備考１

授業に必要な連絡は，授業中もしくはEDEN掲示板上で行います．

備考２

参照ホームページ

開講言語

日本語

語学学習科目

更新日付

2018/03/20 16:47:32