Combinatorics Workshop: Day 4 (07.12.13)

Latest News, Announcements, and Forum Rules
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
Combinatorics Workshop: Day 4 (07.12.13)

Unread post by Phlembac Adib Hasan » Fri Dec 06, 2013 6:57 pm

প্রথম দুই চ্যাপ্টারের প্রবলেম/এক্সারসাইজ অনেক বেশি। এছাড়া নেক্সট চ্যাপ্টারে যাওয়ার আগে এই দুই চ্যাপ্টারের বিষয়গুলো ক্লিয়ার হওয়া অতীব জরুরী। তাই আজকে ব্রেক। রেস্ট নাও, এক্সারসাইজ যেগুলো করার বাকি করতে শুরু করো। আগামীকাল থেকে ডিস্ট্রিবিউশন নিয়ে কাজ শুরু হবে।
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
nishat protyasha
Posts:33
Joined:Tue Sep 17, 2013 12:02 am
Location:Sylhet, Bangladesh.

Re: Combinatorics Workshop: Day 4 (07.12.13)

Unread post by nishat protyasha » Fri Dec 06, 2013 9:02 pm

I didn't understand the "Algorithm" of page-21. Please explain it .

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Combinatorics Workshop: Day 4 (07.12.13)

Unread post by Phlembac Adib Hasan » Sat Dec 07, 2013 6:14 pm

nishat protyasha wrote:I didn't understand the "Algorithm" of page-21. Please explain it .
উত্তর দিতে দেরি হওয়ার জন্য দুঃখিত। আমার নেট শেষ।

অ্যালগোরিদম হচ্ছে কিছু কম্পিউটেশনাল স্টেপের সমষ্টি। কোন একটা ইনপুট নিয়ে এই কম্পিউটেশনাল স্টেপগুলো সম্পাদন করলে কিছু নির্দিষ্ট আউটপুট পাওয়া যায়। যেমন ধর quick-sort. এটা সর্টিং এলগো। কিছু সংখ্যা এতে ইনপুট দেওয়া হয়। আর আউটপুট হিসেবে সংখ্যাগুলো ছোট থেকে বড় বা বড় থেকে ছোট ক্রমে সাজানো হয়ে বের হয়।
এখানের এল্গোতে ইনপুট হিসেবে একটা AAAABB-র কোন একটা রিঅ্যারেঞ্জমেন্ট দেওয়া হচ্ছে। আর আউটপুট হিসেবে পাওয়া যাচ্ছে AAABBB-র consistently dominated নয় এমন একটা সিকুয়েন্স। এবং প্রতিটা ইনপুটের জন্য প্রতিটা আউটপুট ইউনিক। যেমন- AAAABB-র জন্য আউটপুট BAAABB. আর অন্য কোন ইনপুটের জন্য BAAABB আউটপুট হিসেবে পাওয়া যাবে না। এভাবে প্রমাণ করা হয়েছে AAAABB-র মোট রিঅ্যারেঞ্জমেন্টসংখ্যা আর AAABBB-র consistently dominated নয় এমন সিকুয়েন্সসংখ্যা সমান, অর্থাৎ ১৫টি। AAABBB-র টোটাল রিঅ্যারেঞ্জমেন্ট ২০টি। তাই A-dominated sequence ২০-১৫=৫টি।

এখানের অ্যালগোর ব্যাখ্যা: ইনপুট সিকুয়েন্সের বামের প্রথম ঘর থেকে শুরু করে ডানে যেতে যেতে ক্ষুদ্রতম সেগমেন্টটি নির্ণয় করো, যাতে A-র সংখ্যা B-থেকে বেশি। এই সেগমেন্টের A-র স্থানে B আর B-র স্থানে A বসাও। ইনপুটের বাকি স্ট্রিঙটা অপরিবর্তিত রাখ।
যেমন- ABAAAB-তে ক্ষুদ্রতম সেগমেন্ট ABA.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
nishat protyasha
Posts:33
Joined:Tue Sep 17, 2013 12:02 am
Location:Sylhet, Bangladesh.

Re: Combinatorics Workshop: Day 4 (07.12.13)

Unread post by nishat protyasha » Sat Dec 07, 2013 10:05 pm

ভাইয়া আমি এটা মোটামুটিভাবে বুঝেছি কিন্তু বইয়ের প্রথম উদাহরন-'AAAABB changes to BAAABB" এই জায়গাটি বুঝতে পারছিনা। এটি একটু বুঝিয়ে দিলে ভাল হয়।

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Combinatorics Workshop: Day 4 (07.12.13)

Unread post by Phlembac Adib Hasan » Sun Dec 08, 2013 1:47 pm

এই স্ট্রিং-এর জন্য ক্ষুদ্রতম সেগমেন্ট A. এটাকে বদলে বানানো হল B. বাকি স্ট্রিং অর্থাৎ AAABB অপরিবর্তিত থাকলো। এইভাবে হয় BAAABB
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
nishat protyasha
Posts:33
Joined:Tue Sep 17, 2013 12:02 am
Location:Sylhet, Bangladesh.

Re: Combinatorics Workshop: Day 4 (07.12.13)

Unread post by nishat protyasha » Sun Dec 08, 2013 8:35 pm

ক্ষুদ্রতম সেগমেন্ট নির্ণয় করার পদ্ধতিটাই আসলে আমি বুঝতে পারছিনা। AAAABB তে এটা A হলে, ABAAAB তে এটা A নয় কেন ?

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Combinatorics Workshop: Day 4 (07.12.13)

Unread post by Phlembac Adib Hasan » Sun Dec 08, 2013 10:31 pm

আমিই ভুল করেছি। ABAAAB-তেও A-ই ক্ষুদ্রতম, ABA না।
BAAAAB-তে BAA ক্ষুদ্রতম।
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
nishat protyasha
Posts:33
Joined:Tue Sep 17, 2013 12:02 am
Location:Sylhet, Bangladesh.

Re: Combinatorics Workshop: Day 4 (07.12.13)

Unread post by nishat protyasha » Sun Dec 08, 2013 11:20 pm

ABAAAB তে ক্ষুদ্রতম সেগমেন্ট A হলে ABAABA( B27* b,P-22 ) তে এটা A হওয়ারই কথা। তাহলে এটা পরিবর্তিত হয়ে B হবে। এতে পুরো স্ট্রিংটা হবে BBAABA. কিন্তু বইয়ে এটার উত্তর দেয়া আছে BABABA. আসলে ব্যাপারটা কি ? নাকি আমিই ভুল।

Post Reply