• 検索結果がありません。

I222 計算の理論 (Theory of Computation) Report (4)

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "I222 計算の理論 (Theory of Computation) Report (4)"

Copied!
1
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 1 ページ )

全文

(1)

I222

計算の理論

(Theory of Computation) Report (4)

2007

年度

II-1

期

(10,11

月) 担当: 上原 隆平

([email protected])

出題

(Propose): 11

月

2

日

(金) (November 2 (Fri))

提出

(Deadline): 11

月

9

日

(金)

講義終了時

(November 9 (Fri), 10:50)

注意

(Note):

レポートには氏名，学生番号，問題番号，解答を，すべて手書きで書くこと．

(Do not forget to handwrite your name, student ID, problem numbers, and answers on your report.)

Problem 1:

以下の命題は正しいか？正しいなら正しいことを証明し，正しくないなら反証せよ．(Is each

of them correct or wrong? If it is correct, prove it. If it is wrong, produce counterevidence.)

1. 10n

2

+ 5n + 3 = O(n

2

) (1 point) 2. log n = O(n) (1 point)

3. n = O(log n) (1 point)

4.

スターリングの公式によると，n!

∼ √ 2πn (

n

e

)

n

である．関数

f (n) = √ 2πn (

n

e

)

n

とする．こ のとき

f(n) = O(n

n

)

である．(Stirling’s formula tells us

n! ∼ √

2πn (

n

e

)

n

. Let f (n) be a function defined by f (n) = √

2πn (

n

e

)

n

. Then, f (n) = O(n

n

).)(2 points)

参照

今ダウンロードする ( PDF - 1 ページ - 26.14 KB )

関連したドキュメント

実函数の計算理論

Lipschitz continuous ordinary differential equations are polynomial-space complete.. A computable ordinary differential equation which possesses no

2. On the Computation of the Efficient Frontier

An easy-to-use procedure is presented for improving the ε-constraint method for computing the efficient frontier of the portfolio selection problem endowed with additional cardinality

第１章　積算基準

⑥ニューマチックケーソン 職種 設計計画 設計計算 設計図 数量計算 照査 報告書作成 合計.. 設計計画 設計計算 設計図 数量計算

1AFermatproblemsolvedbyFrenicle NewUpperBoundsforTaxicabandCabtaxiNumbers

It is possible that other known 5-way solutions, if they have small splitting factors, may produce smaller 6-way solutions than Rathbun’s upper bound.. Using the list of 5-way

Geometry & Topology Monographs Volume 5 (2002) Four-manifolds, geometries and knots

Theorem 8.2 If π is torsion free and virtually poly-Z of Hirsch length 4 then it is the fundamental group of a closed smooth 4 -manifold M which is either a mapping torus of a

Locally realcompact and HN-complete spaces

It is known that a space is locally realcompact if and only if it is open in its Hewitt-Nachbin realcompactification; we give an external characterization of HN- completeness

However, a major challenge is the computation of the probability density function of the solution

When dealing with both SDEs and RDEs, the main goals are to compute, exact or numerically, the solution stochastic process, say x(t), and its main statistical functions (mostly mean,

4. V -Cat is locally presentable if V is so

A cocomplete monoidal closed category is said to be locally λ-bounded as a closed category if its underlying ordinary category is locally λ-bounded and, in addition, the functors A ⊗