2010-02-28

離散 很猶豫要不要提出的一個問題 = =



就是再生成函數


除法定律:若皆可微分,則

微分 x/(1-x)^2=1+x/(1-x)^3
可是我微分 會是
x/(1-x)^2=[(1-x)^2 * 1]- [x * 2 * (1-x) ] / (1-x)^4
=(1-x) - 2x /(1-x)^3
=(1-3x)/(1-x)^3

2010-02-27

今天99台大數學考題

A=
[1 2 3 4 5]
[6 7 8 9 10]
[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]
求det(A-I)
感覺不難....可是沒想到 囧

2010-02-26

台大數學

題目連結在這:http://www.lib.ntu.edu.tw/exam/graduate/93/93452.pdf

想請問1~5題是TFTFT?

另外請問第六、七題應該怎麼解?

感謝~

2010-02-25

L(x,y) 為 x loves y
請問要怎麼用上面proposition表達這件事?
"x對戀人y說: nobody but you"

for some y, L(x,y) <--> [(for all z, L(x,z)<-->z=y)]

請問是這樣嗎?

[離散]Recurrence Relations

The problem examines a given convex polygon of n sides -that is, a polygon of n sides that satisfies the property: For all point P1 P2 within the interior of the polygon, the line segment joining P1 and P1 also lies within the interior of the polygon.
Given a convex polygon of n sides, Euler wanted to count the number of ways the interior of the polygon could be triangulated(Subdivided) by drawing diagonals that do not intersect.

for a convex polygon of n >= 3 sides, let t(n) count the number of ways the interior of the polygon can be triangulated by drawing non intersecting diagonals.

a)Define t(2) = 1 and verify that t(n+1) = t(2)t(n)+t(3)t(n-1) + ....+t(n)t(2)

請問助教這一題的題意到底在問什麼??

我進不到題目裡面

謝謝助教

線代 證明

Let A and B be n*n matrices with property Ax=Bx for all x屬於Rn Show that A=B

這題不太會有大大會證明嗎

pai 提到...
感覺上是這樣因為所有x屬於Rn都可讓Ax=Bx取x=e_i, for i=1 to n也就是 Ae_i=Be_i =>A_i=B_i=>A和B的每一行都一樣所以A=B

若拙 提到...
我發覺 好像也不是這樣
耶假設A=[(0,-1),(0,1)]B=[(0,1),(0,-1)]x=[1,1]
則Ax=Bx但是A 不等於 B 呢
因為x是行向量相加不代表A等於B
我的看法是 false
有大大其他看法嗎?

[線代]Row Operations

Row operations on a matrix A can change the linear dependence relations among rows of A

ex

[1 1 1 1] [1 1 1 1]
[2 2 2 2] ~[0 0 0 0]
[1 2 3 4] [0 1 2 3]

原本2 3 列LI 之後變成 LD 所以是 true嗎 ?

另外請問
Let A be m*n matrix with m>n and b be an m*1 vector then Ax=b may have multiple solution
這應該是true吧 ?

2010-02-24

線代 ,cayley-hamilton



這題有人會詳解嗎?
謝謝

[線代]矩陣的rank問題

A:m*n

A具左反<->rank(A)=n

即A要行獨立

又A行獨立時 Ax=b 未必有解 若有解則必唯一

--
請問 Ax=b未必有解 可以用A之行空間之維度若未到達m 則有些b不在CS(A)中 這樣解釋

可是如果用A具左反來看 令A之左反為B

則 Ax=b -> x=Bb 這樣是錯在哪裡呢 看起來都可以得到x阿...

雖然自己舉例也可以看到矛盾

例如A=[1,0;0,1;0,0]

Ax=[0,0,1]^t本應無解

可是取A之左反等於A^t

則A^tAx = x = A^tb = [0,0]

列完式子 看起來變成Ax=b的近似解了 = =

請問左反對求解的意義是什麼呢 ?

單純就 Ax=b 若A具左反B 則 BAx=x=Bb 所以 x=Bb這樣來看 就字面來看很像是有解

可是實際上並不是這樣...

還是說在A之rank未到達m時

且b不屬於CS(A)時

A之左反就是用來求近似解呢

排列組合





請問一下助教這題該怎麼證明?
麻煩了~

[離散] - 布林代數2

2.Suppose that(R,+,.)and(S,⊕,⊙) are two rings
with zero element Zr and Zs respectively.
Given a ring homorphism f:R→S,let K={aεR|f(a)=Zs}
Prove that
(a)(K,.,+) is a ring
(b)K is an ideal of R

謝謝

[離散]-CH11

PPT.cc縮圖服務

這一題的解法有個地方不太懂,題目要著兩種顏色

在鏡射的部份求得的數是 (5*2^3)

PPT.cc縮圖服務

課本答案:1/10(2^5+4*2+5*2^3)=8

我想法是這樣,那個2^3應該是1對應到1';2對應到2';3對應到3' 各2種著色所以:2^3

想請問一下,4和5這兩個點不也可以著色嘛?這樣是不是再乘2^2我知道這樣應該不對數字比不動還大

可是想法兜不過來 謝謝。
一、這題我想用rook poly.解, 想了一下好像還要考慮順序且符合R跟G都要出現1~6..





二、請問助教這題rook會什麼要除以二階~? (已解)


















三、請問下面哪些有partial ordering? 若是需找出maximal and minimal elements (已解)









謝謝

[線代] - eigenvalue

Find det(A) given that A has p() as its characteristic polynomail

a. p() = ^3 - 2^2 + + 5


老師解法:
假設A為nxn,因為p(
)=det(I-A)
→p(0) = det(-A) = (-1)^n det(A) = -5

我想問我一般
p()會令成det(A-I),這樣答案不是差的負號??

2010-02-23

[離散] - 布林代數

1. Suppose that (K. * , + )is a Boolean algebra and a is an atom of K.
Prove that a*b=0 or a*b=a for every b belongs K.

ps. 這邊的atom不知道是什麼

2. The following is a proof for a*0=0 in Boolean algebra (K,*,+),where a belongs K

a*0 = (a*0)+0 = (a*0)+(a*a')=a*(0+a')=a*a'=0

Prove a+1=1

a+1 = a+ (a+a') = a+a' =1

ps.我這樣寫第二步就出來了.....如果考試要我直接證明a*0=0
我也寫不出這麼多步驟耶~~這超直觀

線代

Let A and B be n*n matrices and let C=AB. Prove if B is singular then C must be singular


這樣證明對嗎
存在x不等於0 使得 Bx=0
=> Cx=ABx
=> Cx=A*0
=> Cx=0
因為x不等於0
=>C 不可逆

線代

Let A and B be n*n matrices with property Ax=Bx for all x屬於Rn
Show that A=B

這題不太會有大大會證明嗎

線代 ,Show that no 2*2 matrices A and B exist that satisfy the matrix equation AB-BA=I

請問這裡這麼解阿?

Show that no 2*2 matrices A and B exist that satisfy the matrix equation AB-BA=I


用determine嗎? det(AB)=det(BA)
det(AB)-det(BA) =0
det(I)=1
矛盾

旦 det(AB-BA) 會等 det(AB)-det(BA) ?

離散~

、(97台大資工) Suppose that (R, +, ×) is a ring. Prove that if S包含R is finite, then (S, +, ×) is a ring if and only if for a, b S, a + bS and a×bS.


解答為We only need to show -a∈S for every a∈S...請問助教為什麼它只需要證明負元素屬於S就好? 跟課本Ch.9定理35證明有不一樣嗎?

二、In how many ways can 60060 be factored into three factors, each greater than 1, if the order of the factors is not relevant?

謝謝

2010-02-22

[線代]Quadratic form

(a)(8%)Find the standard form of the quadratic curve
3(x^2)+2xy+3(y^2)+6√2 x-10√2 y+10=0.

(b)(4%)Give the coordinates of the center and the vectors representing the
two principal axes of the curve.(the x'-axis must be 0<=θ<π/2 and
the y'-axis must be π/2<=θ<π)


我算到後來有個疑問
V(2):span={[-1 1]}
V(4):span={[1 1]}

但我在第二題我看座標轉軸的時候
不是要看P^t 為順還是逆嗎?

但我如果把上面的eigenvector照順序把成行的話
會發生奇妙的結果耶

[cos -sin]
[sin cos]

左上角應該要跟又下角一樣的值
我照我的說的順序擺不就兩個cos 竟然不同值
這樣不就不是旋轉矩陣了嗎?

還是一定要注意要把成旋轉矩陣

PS:這一題是台大今年的期末考題
有點難算 希望跟有算的一起對答案
因為我算的數字醜到爆...

FSM的問題

(i)What is the set generated by the following phrase-structure grammar? G=(V,T,S,P), V={0,1,S}, T={0,1}, P={S->01,S->0S1}

這題答案是:

{0^n1^n n>=1}


(ii)Construct a phrase-structure grammar to generate the set {1^n0 n>=0}

這題答案是:

G=(V,T,S,P), V={0,1,S}, T={0,1}, P={S->1,S->0,S->S0}

是這樣嗎?
如果有錯 請助教能多多教我一下

[離散]Graph

Let Kv(G)and Ke(G) represent the vertex connectivity and edge connectivity,
respectively, of a graph G.

show Kv(G)<= Ke(G)


沒看過證連通性的問題

請問助教要如何證明

謝謝

2010-02-21

代數

Let (F,+, *) be a field. Let char(F) denote the characteristic of F. If char(F) > 0, then char(F) must be prime.

請問助教這題該怎麼證明..?
感謝~

[離散] - 圖論 3


For the following graph, how many maximal cliques of size 3 are there,
and what is the size of maximum idependent sets?

答案是 8跟4嗎?

[離散] - 圖論 2

1. Suppose G=(V,E) where V = {(1,3),(1,4),(1,6),(2,3),(2,5),(2,7),(3,7),(4,6),(4,7),(5,6)}

(d)Is G = ({1,2,4,5},{(1,4),(2,5),(5,6)}) a subgraph of G?
(e)Is the subgraph of G induced by {2,4,5,6,7} biconnected?

可以解釋一下嗎?


2.Suppose G=(V1,E1),H=(V2,E2) G,H is isomorphic,which of the statements are correct?
(a)|V1|=|V2| and |E1|=|E2|
(b)If G has Hamiltonian path, H has HP.
(c)If G is not planar,H isn't.
(d)If G has a matching of size k, H has,too
(e)G and H has same chromatic number.



4.Explain why every n-vertex srongly connected digraph contains at least n arcs

何謂arcs??

2010-02-20

[線代] 三題題目請益 !

http://twpic.org/uploads2/77ada25e41.jpg

麻煩助教了~感謝 ︿︿!!

[線代] - 一些觀念

95中央 T or F

(f) Perspective projection is combined from the perspective and projection

transformations; the perspective projection is not linear transformation, but

perspective transformation is invertible.

→請問perspective transformation是什麼阿? Perspective projection?

(j) The columns of the change-of-coordinates matrix P are C-coordinate vectors of
C<-B
the vector in B.

→這題看不懂,後面那句到底是C轉B還B轉C~考試很怕英文不好會錯意


謝謝

[離散] - 圖論

上課筆記有一題: n個點{1,2,3,.........,n}

1.simple graph 個數?
2.三角形123 有幾個?
3.所有三角形有幾個?
4.平均一個graph的三角形有幾個?


另外,98中山電機

1.How many ways can the undirected complete graph be oriented into a directed graph?

2.Given two selected vertices S and T, how many paths of length n-1 with distinct vertices
from vertex S to vertex T are contained in the graph?

我圖論算個數都不太會.....不知道怎麼想
麻煩助教了,謝謝

離散

一、 請問這題答案是(c)(d)(e)嗎?








二、請問如果以面著色的正方形如下
那麼Ploya轉法這種從腰身中間穿越的C拍該怎麼令呢? (X_2 ^4?)










三、a小題答案為2^n-1, b小題答案為3^n-1, 請問c小題該如何說明?













謝謝

2010-02-19

小問題


請問這題的connected component
是不是有4個?作答時,是否把圖畫出來,
還是有什麼表示方法比較好呢?
An inner product is a scalar valued function on the set of ordered pairs of vectors, true or false ?
這句話是什麼意思呢?
麻煩解答了 感謝

Logic




完全不知如何下手

請助教指導

謝謝

2010-02-18

[離散] - 排列組合

1.Determine the number of four-element subsets of S = {1,2 ,3,......,15}

contaun no consecutive integers.


2. (1+x^2+x^4)^5 , how many terms are there? (是不是只能展開看有幾項~?)



3. The nuver of partitions of {1,2,3,4,5} into three blocks is [5 3]^t = 25

The total number of functions f: {1,2,3,4,5} -> {1,2,3,4} with |f({1,2,3,4,5})| = 3

is ?

ans: 4 x 25 x6 (看不懂)

[線代] 一題題目請益

A linear system Ax=b of m equations and n variables . State under what conditions will the linear system have solutions , a unique solution ,
and infinity many solutions ?
------------------------------------------------------------
請問這題是直接寫出3版課本的定理1-19嗎?!
還是說有其他需要補充的地方呢?!!
麻煩各位了~謝謝 !!!

2010-02-17

[線代] 三題小證明題

http://twpic.org/uploads2/5b5cf20a18.jpg

請教各位一下~~
上面這3題小證明
要如何寫才會來的比較適當及完整呢?!!!
麻煩各位了~謝謝 !!!!!

[離散]邏輯 if p then q else r

請問 if p then q else r

等價於(p->q)and(~p->r) 等價於 (p and q)or(~p and r)

最後那一個是怎樣推的呢 ?

2010-02-16

排列組合

a到z,26個英文字母排列,a要在b前面,b要在c前面,這種排列方法有幾種呢?

麻煩解答了 感謝

2010-02-15

[離散] 一些題庫

大家好, 新年快樂

問題一:
(97中興資管) How many strings of five decimal digitals which have exactly three digitals 9s?
答案是C5取3乘9平方, 解答意思似乎是選三個位置放9, 其餘位置的範圍為0~8有九個
請問它不用扣掉首項為零的strings嗎?
如..{00999,01999,...,08999, 09099,09199,...,09899, 09909,09919,...,09989, 09990,09991,...,09998}這些


問題二:請問後面的n-2代表什麼意思呢












問題三: (c)小題為什麼會有個係數3?












問題四: 下面的推導好像有錯..不知道在哪裡

(pq)[q(rˇq)]

(pq)[q(qr)]

[(pq)(qr)]q

(pr)q

(pˇr)q



謝謝

2010-02-14

[線代]求基底



請問要怎樣有系統的敘述 來解這一題呢

直接寫

V為一超平面 其法向量為(1,2,...,n) 所以dim(V)=n-1

取B={(1,-1/2,0...,0),(1,0,-1/3,0,...,0),...,(1,0,...,-1/n)}n-1個vectors屬於V

B:LI(要列成matrix 化成row echelon form 有有n-1個 pivot 這樣証嗎 ?)

則span(B)=V

B為V之一組basis

這樣寫可以嗎 ?

[線代]負定判斷


Q=[ 0 1 1 ]
[ 1 0 1 ]
[ 1 1 0 ]

Q on the subspace M={x: x1 + x2+ x3 =0}
is 正定 負定 不定?

請問這種是直接判斷Q是不是負定就好

還是要縮小定義域 檢查M的element在Q 會不會恆小於0

如果M的element在Q會恆小於0 可以說Q在M上負定嗎 ?

例如 取M的一組basis={[1,-1,0]^t,[1,0,-1]^t}

M中的任一vector可表成x=c1v1+c2v2

則x^tQx = -2c1^2-2c1c2 -2c2^2 = -2((c1-c2/2)^2+3c2^2/4) 恆小於0

所以可以說 Q 在 M負定嗎 ?

2010-02-13

[離散]Eular Formula證明

先令N表所有區域為成的邊數總和(涵無線區域及重複邊)

因為每個區域至少含三邊 所以 N>=3r

因為每個邊至多落在2個區域邊界上 所以N<=2e

請問為什麼不是剛好落在兩個region的邊界上 所以N=2e 呢 ... ?

我看老師的筆記 算圍成region邊數的方法

似乎是要繞一圈耶

x----y----z

像這樣只有一個無限區域圍成外面region的邊數似乎要算成4個@@


x
\
y---z
|\ |
| t |
| |
w---v




這樣圍成外面region 和圍成裡面region的邊數都是6

2010-02-12

[離散] 排列組合

In how many ways can a gambler draw five cards from a standard deck and get

(c) a full house


我答案寫:

(c) (13,2)*(4,3)(4,2) → 答案是: (13,1)*(4,3)*(12,1)*(4,2)

我的想法是從1~13抽兩個點數出來,再挑花色,
可是答案跟我差了2!


答案應該是錯的吧~?
因為挑出來的2點沒有先後次序


這是題庫班第3-36頁題目


[離散]計數問題-直線方程式




2010-02-11

不知道為什麼沒辦法空格
我用以下表示
(n,r) = n 取 r 的組合

想問下面如何用組合證法證
(n,r)* (r,k ) = (n,k)* (n-k,r-k)

離散數學的勘誤表及考題資訊已更新

  1. 新增98離散數學各校試題配分表
  2. 更新97-98離散數學試題詳解勘誤

2010-02-10

請問
(p-1)!= ? mod p
假設 P是質數

2010-02-09

線性代數的勘誤表及考題資訊已更新

  1. 新增98線性代數各校試題配分表
  2. 更新98線性代數試題詳解勘誤

[離散]rooted ordered tree

How many rooted ordered tree on n vertices?

請問這題要怎樣算呢 ?

如果是求 binary tree 個數的話就是 C_n

這題答案是 C_n-1

rooted ordered tree 似乎就不限binary tree 了

關係

u = { 1 , ... , n }r on all subsets of u by ArB, if A不包含於B 且 B不包含於A.Hom many order pairs are there in this relation ?


麻煩解答了 感謝

線代模擬考



恩 一些很弱的問題 QQ
搞不太懂上來詢問一下

2.(a)polynomials if degree exactly 3
不是vector space是因為 -x^3 +X^3 有可能是0 不在degree 3的範圍是這樣嗎?

n次多項式空間(=< 0="">det(A)=0.


16.考markov chain但是A根本不是機率矩陣阿
我一直以為要行相加為1才可以用說 我這想法是錯的嗎?
雖然我硬算算出來是1 1沒錯 但是是不是其實根本不用想這麼多

21 題是給線 跟平常看到的給點不一樣 是找線中的點帶進去算嗎?
可是我這樣算答案差很多說 請問要怎麼想比較好?

2010-02-08

離散[ASAP]

Show that the system of congruences x=a1(mod m1) and
x=a2(mod m2) has a solution if and only if gcd(m1,m2) | a1-a2.

解遞迴-特徵方程式的問題

http://img504.imageshack.us/img504/3284/dsc03168ub.jpg

我對非齊次解裡的特徵解還是有一些不了解
如上圖裡
1.%(d0+d1 n+d2 n+.....)?
上面式子裡?那個位置是該看原本方程式裡的哪邊決定呢
%那位置老師上課說要看出現的次數~是要看根出現幾次就寫n次方嗎
括號內要怎麼看出要令幾項d呢
2.
像圖中
(1)為什麼會少一項呢 (2)中有假設d0和d1 可是(1)中只有假設一個?
(3)中有令到n的2次方 請問如何看要令到幾次方及哪些可以省略 這題裡好像省略d0和d1
(4)裡也有省略 要如何看呢

麻煩助教了
上課這裡有點聽得不太清楚
似懂非懂的

2010-02-07

離散遞迴

For n >= 1, let an be the number of ways to write n as an ordered sum of positive integer where each summand is at least 2.

這題不知道該怎麼列式子才正確
應該是an=a_n-1+a_n-2
還是要an=a_n-2+a_n-3
麻煩助教了..

機率部分

想請問一下助教這題應該怎麼解..是要用無窮等比去表示嗎?因為好像沒有規定範圍..
麻煩助教指導了~感謝。

2010-02-06

NPcomplete

it takes exponential number of steps to solve any NP complete problem in worst case?

順便請問助教 NP complete這部份怎麼讀比較好.....@@


另外,給一個graph,求connectivity和edge-connectivity是什麼意思?


感謝回答

幾題離散問題



請問一下這幾題要怎樣解呢
29.是不是先將3000個信封分成25包 則每包有120個
然後解 120x1 + 120x2 + 120x3 +120x4 = 3000
150<=120xi<=1000
然後變成 x1+x2+x3+x4 = 25,2<=xi<=8
變成解(x^2+...+x^8)^4的[x^25]呢 ?
然後35題則是相當於四人取四個不同球 可重複取的方法數 ?
或者說是四個不同球放入四個不同箱子 可空箱之方法數

2010-02-05

Floyed











想請問一下助教,遇到這題題目,他最後要我們求的到底是最後求出矩陣的第一行(代表A1可到的點),還是說找整個矩陣?

麻煩助教解釋一下了..感謝

2010-02-04

組合問題[ASAP]

In how many ways can two dozen identical robots be assigned to
four assembly lines with
(a) at least three robots assigned to each line?
(b) at least three, but no more than nine, robots assigned to each line?

幾個小問題

看到一題:
1.how many paths length 4 are there in K7?
這題的path應該是指5個點的path吧?
假設考試時,忘了是哪種定義,可以自己假設lenght長度為4
是4個點的path嗎?
也就是在不確定的題目裡面,可以自己假設嗎......

2.還有,題目問求 largest value entries in matrix A是指在A的第一行裡面最大的元素
還是指A矩陣所有元素裡面最大的?

3.what formulas will make the nonlinear transformation into matrix transformation?

4.in what situation will you use compute a least square solution through a QR factorization?

5.請問min cut的定義是? 在做 flow network時,有時候不大確定要怎麼切....

麻煩解答了 感謝

確定一下觀念

1.kn complete graph   n:even => 不具共同邊的HC個數為:n/2取floor
2.kmn bipartite m-n=1 => hpath個數為:(n )^2

麻煩助教指導了~感謝

2010-02-03

[離散]等價關係判斷


請問這題要怎樣解呢 @@ ?

2010-02-01

幾題問題





1.A={1.2.3.4.5.6}B=A*Adefine relation R on B as follow: (a,b)R( x,y) if and only if ( a-b)=( x-y)Compute the partition of B, B/R.
2.
[-2 7]
[-3 7]和
[2 1]
[-1 3] 是否相似?
滿多題的@@
麻煩解答了 感謝

圖論


請問這題要如何證明呢?
麻煩解答了 感謝

[離散]台大資工





請問這題是問有偶數個1的二元n序列有幾個嗎 ?

答案就是 2^(n-1)個吧 ?

[離散]Catalan number 之變形

令A(x)為a_n之生成函數
請問一下a_n = a_2*a_n-1 + a_3*a_n-2 + ... + a_n-1*a_2
a_2 = 1

這個要怎樣推導出 A(x)的多項式形式呢...

台大數學









想請問一下助教,
這題的BCDE應該要怎麼看?
不太懂他要表達的意思..
感謝。