(۲۱ بهمن ۱۳۹۱ ۰۵:۴۱ ق.ظ)maneshth نوشته شده توسط:  بچه ها لطفا یه نگاه به استدلال زیر بندازید.
b) If all characters occur with frequency less than 1/3 then the Huffman code has no codeword.of length 1.
True. Suppose this is not the case. Let x be a node corresponding to a single character with f(x) < 1/3
such that the encoding of x is of length 1. Then x must not merge with any other node till the
end. Consider the stage when there are only three leaves: x, y and z left in the tree. At the last
stage y, z must merge to form another node so that x still corresponds to a codeword of length 1.
But, f(x)+f(y)+f(z) = 1 and f(x) < 1/3 implies f(y)+f(z) > 2/3. Hence, at least one of f(y)
or f(z), say f(z), must be greater than 1/3. But then these two cannot merge since f(x) and f(y)
would be the minimum. This leads to a contradiction.

c) If some character occurs with frequency more than 2/5, then there is guaranteed to be a codeword of length 1.
True. Let s be the symbol with the highest frequency f(s) > 2/5 and suppose that it
merges with some other symbol during the process of constructing the tree and hence does not
correspond to a codeword of length 1. To be merged with some node, the node s and some other
node x must be the two with minimum frequencies. This means there was at least one other node
y (formed by merging of other nodes), with f(y) > f(s) and f(y) > f(x). Thus, f(y) > 2/5 and
hence f(x) < 1/5.

با این حساب هر دو درستن

(۲۱ بهمن ۱۳۹۱ ۱۱:۳۹ ق.ظ)mohammadjavadkho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۵:۴۱ ق.ظ)maneshth نوشته شده توسط:  بچه ها لطفا یه نگاه به استدلال زیر بندازید.
b) If all characters occur with frequency less than 1/3 then the Huffman code has no codeword.of length 1.
True. Suppose this is not the case. Let x be a node corresponding to a single character with f(x) < 1/3
such that the encoding of x is of length 1. Then x must not merge with any other node till the
end. Consider the stage when there are only three leaves: x, y and z left in the tree. At the last
stage y, z must merge to form another node so that x still corresponds to a codeword of length 1.
But, f(x)+f(y)+f(z) = 1 and f(x) < 1/3 implies f(y)+f(z) > 2/3. Hence, at least one of f(y)
or f(z), say f(z), must be greater than 1/3. But then these two cannot merge since f(x) and f(y)
would be the minimum. This leads to a contradiction.

c) If some character occurs with frequency more than 2/5, then there is guaranteed to be a codeword of length 1.
True. Let s be the symbol with the highest frequency f(s) > 2/5 and suppose that it
merges with some other symbol during the process of constructing the tree and hence does not
correspond to a codeword of length 1. To be merged with some node, the node s and some other
node x must be the two with minimum frequencies. This means there was at least one other node
y (formed by merging of other nodes), with f(y) > f(s) and f(y) > f(x). Thus, f(y) > 2/5 and
hence f(x) < 1/5.

با این حساب هر دو درستن

دوست عزیز میشه منبع این استدلالتون رو هم بگید؟

(۲۱ بهمن ۱۳۹۱ ۰۲:۴۸ ب.ظ)osho نوشته شده توسط:  سوال ۴۳ باید n بار dfs بزنی که مرتبه ان از فلوید n^3 است کمتره.

(۲۱ بهمن ۱۳۹۱ ۰۳:۲۹ ب.ظ)osho نوشته شده توسط:  اولا n^ 4 نمی شود اگر متراکم باشد می شود n^3 چون در گراف متراکم تعداد یالها n^2 میشه و اگر در n ضرب بشه میشه n^3 .
تازه در الگوریتم فلوید فقط میشه دور را تشخیص داد اینکه چه جوری می خواهی دور ها را بررسی کنی که طول زوج دارند باز هم باید به اندازه n در قطر گراف سرچ کنی. 

(۲۱ بهمن ۱۳۹۱ ۰۳:۲۹ ب.ظ)osho نوشته شده توسط:  اولا n^ 4 نمی شود اگر متراکم باشد می شود n^3 چون در گراف متراکم تعداد یالها n^2 میشه و اگر در n ضرب بشه میشه n^3 .
تازه در الگوریتم فلوید فقط میشه دور را تشخیص داد اینکه چه جوری می خواهی دور ها را بررسی کنی که طول زوج دارند باز هم باید به اندازه n در قطر گراف سرچ کنی. 

(۲۱ بهمن ۱۳۹۱ ۰۸:۵۹ ب.ظ)laleh13 نوشته شده توسط:  [quote='arashitc2' pid='160904' dateline='1360380053']
[quote='mahdiii' pid='160853' dateline='1360363197']
[quote='mohammadjavadkho' pid='160408' dateline='1360333126']
[quote='amin_2994' pid='160389' dateline='1360331690']
[quote='mohammadjavadkho' pid='160139' dateline='1360322741']

سوال ۴۷ به نظر من هر دو غلط هستن.. یعنی گزینه یک

استدلال من هم این هستش:
واسه قسمت الف:
دو پنجم یعنی ۴۰ درصد
خب اگه فراوانی ما برای سه تا عنصر باشه : ۴۵و ۴۵ و۱۰
اونوقت یکی از عناصر با فراوانی ۴۵ طول بزرگتر از یک خواهد داشت ( امتحان کنید)


واسه قسمت ب :
یک سوم یعنی حدودا ۳۳/۳۳
خب اینجا هم اگه فراوانی عناصرمون باشن : ۳۰و ۳۰و ۳۰و۱۰
اونوقت یکی از عناصر با فراوانی ۳۰ طولش یک خواهد بود. ( اینو هم امتحان کنین)

(۲۱ بهمن ۱۳۹۱ ۰۸:۰۴ ب.ظ)ali007 نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۳:۲۹ ب.ظ)osho نوشته شده توسط:  اولا n^ 4 نمی شود اگر متراکم باشد می شود n^3 چون در گراف متراکم تعداد یالها n^2 میشه و اگر در n ضرب بشه میشه n^3 .
تازه در الگوریتم فلوید فقط میشه دور را تشخیص داد اینکه چه جوری می خواهی دور ها را بررسی کنی که طول زوج دارند باز هم باید به اندازه n در قطر گراف سرچ کنی. 

چجوری با dfs میشه دوری به طول زوج رو بدست آورد؟
اصلا dfs برای یال هایی با وزن متفاوت کار میکند؟ تو سوال که نگفته برای گراف بدون وزن یا با وزن یکسان؟

(۲۲ بهمن ۱۳۹۱ ۱۰:۲۲ ق.ظ)osho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۸:۰۴ ب.ظ)ali007 نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۳:۲۹ ب.ظ)osho نوشته شده توسط:  اولا n^ 4 نمی شود اگر متراکم باشد می شود n^3 چون در گراف متراکم تعداد یالها n^2 میشه و اگر در n ضرب بشه میشه n^3 .
تازه در الگوریتم فلوید فقط میشه دور را تشخیص داد اینکه چه جوری می خواهی دور ها را بررسی کنی که طول زوج دارند باز هم باید به اندازه n در قطر گراف سرچ کنی. 

چجوری با dfs میشه دوری به طول زوج رو بدست آورد؟
اصلا dfs برای یال هایی با وزن متفاوت کار میکند؟ تو سوال که نگفته برای گراف بدون وزن یا با وزن یکسان؟

در اینجا منظور از ظول زوج وزن گراف نیست منظور تعداد یال ها است.که اتفاقا با فلوید پیدا کردنش سخت است.

(۲۲ بهمن ۱۳۹۱ ۰۱:۱۲ ب.ظ)ali007 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۱۰:۲۲ ق.ظ)osho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۸:۰۴ ب.ظ)ali007 نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۳:۲۹ ب.ظ)osho نوشته شده توسط:  اولا n^ 4 نمی شود اگر متراکم باشد می شود n^3 چون در گراف متراکم تعداد یالها n^2 میشه و اگر در n ضرب بشه میشه n^3 .
تازه در الگوریتم فلوید فقط میشه دور را تشخیص داد اینکه چه جوری می خواهی دور ها را بررسی کنی که طول زوج دارند باز هم باید به اندازه n در قطر گراف سرچ کنی. 

چجوری با dfs میشه دوری به طول زوج رو بدست آورد؟
اصلا dfs برای یال هایی با وزن متفاوت کار میکند؟ تو سوال که نگفته برای گراف بدون وزن یا با وزن یکسان؟

در اینجا منظور از ظول زوج وزن گراف نیست منظور تعداد یال ها است.که اتفاقا با فلوید پیدا کردنش سخت است.

اتفاقا منظور از دوری به طول زوج دقیقا وزن یال هاست شما اگه فصل ۲۴ کتاب clrs بخونید که مربوط کوتاهترین مسیرهای تک مبدا یا کتاب طراحی الگوریتم سپاهان که خیلی قشنگتر همون فصلو گفته چندین بار اشاره کرده به این موضوع ..میخوام بدونم کدوم کتاب یا جزوه یا سوال کنکوری گفته که دوری به طول زوج منظور تعداد یالهاست؟؟؟؟؟

در ضمن همون فصل ۲۴ بخش الگویتم بلمن فورد گفته :
۱- برای وزن مثبت و منفی درست کار میکند.
۲-میتواند وجود دور با وزن منفی را تشخیص بدهد

این دو تا خاصیت بلمن فورد دقیقا مثل فلویده پس بنابراین میتواند به راحتی دوری به طول منفی تشخیص بده ولی اگه دوری به طول منفی نداشته باشد پس همه دوراش به طول مثبته..