Slide 10 / スライド10

Introduction to Information
and Communication
Technology (a)
10th week: 2.5 Problem solving using a computer
Kazumasa Yamamoto
Dept. Computer Science & Engineering
Introduction to ICT(a) 9th week
1
Notice
 This lecture is one of the experimental “bilingual”
lectures on the “Super Global University” program.
 This lecture is given in JAPANESE using English slides.
Introduction to ICT(a) 9th week
2
Floating point numbers (1) (review)
 Decimal & Binary integer number
 (10)10 = (1010)2
( 1 0 )10
( 1 0 1 0 )2
1 × 101 + 0 × 100
1 × 23 + 0 × 22 + 1 × 21 + 0 × 20
 Fixed point number
 (1.25)10 = (1.01)2
( 1. 2 5 )10
( 1. 0 1 )2
1 × 100 + 2 × 10-1 + 5 × 10-2
1 × 20 + 0 × 2-1 + 1 × 2-2
Introduction to ICT(a) 9th week
3
浮動小数点数（１）（先週の復習）
 10進整数と2進整数
 (10)10 = (1010)2
( 1 0 )10
( 1 0 1 0 )2
1 × 101 + 0 × 100
1 × 23 + 0 × 22 + 1 × 21 + 0 × 20
 固定小数点数
 (1.25)10 = (1.01)2
( 1. 2 5 )10
( 1. 0 1 )2
1 × 100 + 2 × 10-1 + 5 × 10-2
1 × 20 + 0 × 2-1 + 1 × 2-2
Introduction to ICT(a) 9th week
4
Floating point number (2) (review)
 Floating point number
 (11.25)10 = (1.125)10×101 = (1011.01)2 = (1.01101)2×23
mantissa exponent
mantissa exponent
 (0.1)10 = (0.00011001100110011001100110011...)2
≒ (1.10011001100110011001101)2×2-4
 “mantissa” is (equal to) 24bit (float) and 53bit (double)
 (1/3)10 = (0.333333...)10 ≒ (0.333333)10
 (0.333333)10 + (0.333333)10 + (0.333333)10 = (0.999999)10
 (0.0001100110011001101)2×(1010)2
= (0.0001100110011001101)2×((1000)2 + (10)2)
= (0.1100110011001101)2 + (0.0011001100110011)2
= (1)2
Introduction to ICT(a) 9th week
5
浮動小数点数（２）（先週の復習）
 浮動小数点数
 (11.25)10 = (1.125)10×101 = (1011.01)2 = (1.01101)2×23
仮数部
指数部
仮数部
指数部
 (0.1)10 = (0.00011001100110011001100110011...)2
≒ (0.000110011001100110011001101)2
 仮数部はfloatで24bit相当、doubleで53bit相当
 (1/3)10 = (0.333333...)10 ≒ (0.333333)10
 (0.333333)10 + (0.333333)10 + (0.333333)10 = (0.999999)10
 (0.0001100110011001101)2×(1010)2
= (0.0001100110011001101)2×((1000)2 + (10)2)
= (0.1100110011001101)2 + (0.0011001100110011)2
= (1)2
Introduction to ICT(a) 9th week
6
Main points of this week
• Algorithm
• Data structure
• Programming
• “Algorithm + Data structure”
• Implementation of a procedure which solve the
problem, by using data structures
Introduction to ICT(a) 9th week
7
今回のポイント
 アルゴリズム
 データ構造
 プログラミング
 “アルゴリズム + データ構造”
 データ構造を用いて、問題を解く手順を実装すること
Introduction to ICT(a) 9th week
8
Algorithm
 “A self-contained step-by-step set of operations to
be performed” (Wikipedia)
 A procedure (operation) set to solve a problem
 Example: Euclidean Algorithm
 An efficient method for computing the greatest
common divisor (GCD) of two numbers
1. m, n (m ≧ n) as the input numbers
2. if n = 0 then output m and finish.
3. r ← the reminder of m divided by n
4. m ← n, n ← r
5. Go to Step 2.
Introduction to ICT(a) 9th week
9
アルゴリズム
 “問題を解くための手順を定式化した形で表現した
もの” (Wikipedia)
 例：ユークリッド（Euclid）の互除法
 最大公約数を効率良く求める方法
1. 入力 m, n (m ≧ n)
2. もし n = 0 なら、m を出力して終了
3. r ← m を n で割った余り
4. m ← n, n ← r
5. Step 2に戻る
Introduction to ICT(a) 9th week
10
Visualization of algorithms
 Algorithm Visualizer
 http://algo-visualizer.jasonpark.me/
 Let’s see the behavior of “Euclidean Algorithm”
 “Number Theory” → “Euclidean Algorithm”
Introduction to ICT(a) 9th week
11
アルゴリズムの視覚化
 Algorithm Visualizer
 http://algo-visualizer.jasonpark.me/
 “ユークリッドの互除法”を見てみよう
 “Number Theory” → “Euclidean Algorithm”
Introduction to ICT(a) 9th week
12
Data structure
 Variable
 a symbolic name associated with a value (“box model”)
 Array
 a systematic arrangement of similar objects, usually in rows and
columns (“sequence of the boxes”)
 Graph
 a set of vertices and edges
 Tree
 a connected graph without cycles
 Stack
 “Last-In-First-Out” data structure
 Queue
 “First-In-First-Out” data structure
 List
 an ordered sequence of values
Introduction to ICT(a) 9th week
13
データ構造
 変数
 値に対応するシンボル名 (“箱モデル”)
 配列
 同じ種類（型）のオブジェクト（データ。変数の“箱”）を連続して並
べたデータ構造
 グラフ
 頂点と枝で構成されるデータ構造
木
 循環のないグラフ
 スタック
 “Last-In-First-Out”なデータ構造
 キュー
 “First-In-First-Out”なデータ構造
 リスト
 値を系列で保持するデータ構造
Introduction to ICT(a) 9th week
14
Visual Programming Languages
 Scratch
 https://scratch.mit.edu/
 MOONBlock
 http://moonblock.jp/
 Programin
 http://www.mext.go.jp/programin/
 Viscuit
 http://www.viscuit.com/
 Google Blockly (Blockly Games)
 https://blockly-games.appspot.com/
Introduction to ICT(a) 9th week
15
ビジュアルプログラミング言語
 Scratch
 https://scratch.mit.edu/
 MOONBlock
 http://moonblock.jp/
 プログラミン
 http://www.mext.go.jp/programin/
 Viscuit
 http://www.viscuit.com/
 Google Blockly (Blockly Games)
 https://blockly-games.appspot.com/
Introduction to ICT(a) 9th week
16
Mini report of this week
 From “algorithm” to “programming”
 How order the commands?
 Let’s solve Google Blockly’s “Maze” as much as you
can!
 No.10 looks a little difficult.
 Paste the screenshot of the last question you solved on the
mini report.
 Today’s impression
Introduction to ICT(a) 9th week
17
今週のミニレポート
 「アルゴリズム」から「プログラム」へ
 どのように命令を並べれば良いか？
 Google Blocklyの「迷路」をできるところまでやって
みよう
 最後（10番目）は少し難しい
 解けた最後の問題のスクリーンショットをミニレポート
に貼って提出
 本日の感想
Introduction to ICT(a) 9th week
18

Download Report