انجمنصفحه اولجستجوی انجمن

[mohammadjavadkho]

(۲۱ بهمن ۱۳۹۱ ۰۵:۴۱ ق.ظ)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.

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

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

[maneshth]

(۲۱ بهمن ۱۳۹۱ ۱۱:۳۹ ق.ظ)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.

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

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

والا من که هنوز به حدی نرسیدم که بخوام نظر علمی از خودم بدم اینو با جستجو در اینترنت به دست آوردم.اینم لینکش :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

تمرینات حل شده ای که در دانشگاه ایالتی oregan داده شده

[osho]

سوال ۴۳ باید n بار dfs بزنی که مرتبه ان از فلوید n^3 است کمتره.

[ali007]

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

به نظر من n بار dfs برابره n^2+e و برای گرافهای متراکم برابر n^4 ....که از فلوید بیشتره

[osho]

اولا n^ 4 نمی شود اگر متراکم باشد می شود n^3 چون در گراف متراکم تعداد یالها n^2 میشه و اگر در n ضرب بشه میشه n^3 .
تازه در الگوریتم فلوید فقط میشه دور را تشخیص داد اینکه چه جوری می خواهی دور ها را بررسی کنی که طول زوج دارند باز هم باید به اندازه n در قطر گراف سرچ کنی. 

[mahdiii]

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

بله n^4 نمی شود. اگر تعداد یالها کم باشد مثل درخت می شود n(v+e) که همان ۲^on است و اگر متراکم باشد (در بدترین حالت کامل) می شود (v+e)n یعنی n^3

[ali007]

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

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

[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']

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

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


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

[mahdiii]

(۲۱ بهمن ۱۳۹۱ ۰۸:۵۹ ب.ظ)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']

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

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


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

قسمت اولشو که خیلیا من جمله من با مثال رد کردیم. حالا هر کی می خواد بگه درست. وقتی با مثال نقض رد بشه خوب رد شده دیگه اما بخش دوم کجا طول یکی از این نویسه ها میشه ۱؟!!! شما چجوری هافمنو می سازی؟
اول ۱۰و۳۰ انتخاب میشه که میشه ۴۰ و بعدش ۳۰ با ۳۰ میشه ۶۰ و در نهایت میشه ۱۰۰ این طوری طول همه میشه دو

[osho]

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

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

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

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

[golabijat]

سلام دوستان
سوال الگوریتم بهینه برای پیدا کردن دور زوج کدوم یکی میشد ؟
فکر کنم n بار BFS میشد نه؟

[ali007]

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

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

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

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

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

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

[osho]

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

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

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

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

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

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

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

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

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

فکر کن من تو حرف همو نمی فهمیم به کتاب جدید ۶۰۰ مسله دکتر قدسی رجوع کنید جواب اونجا است.

[golabijat]

[/quote]
فکر کن من تو حرف همو نمی فهمیم به کتاب جدید ۶۰۰ مسله دکتر قدسی رجوع کنید جواب اونجا است.
[/quote]

دوست عزیز کدوم صفحش؟

[osho]

فکر کن من تو حرف همو نمی فهمیم به کتاب جدید ۶۰۰ مسله دکتر قدسی رجوع کنید جواب اونجا است.
[/quote]

دوست عزیز کدوم صفحش؟
[/quote]
کتاب حالا دمه دست ندارم ولی فصل ۶ را بخون تست ها شو نگاه کن نمونه این سوال رو می بینی .که طول زوج منظور تعداد یال ها است نه وزن گراف.