۶۰۰ تست الگوریتم

میگم من به جواب سوال ۳.۷ اعتراض دارم. اگر درج در آخر لیست باشد ۳ تا اشاره گر باید عوض بشه نه ۴ تا.
(این موضوعش الگوریتم پیشرفته نیست ولی نزدیک‌ترین موضوع بود.)

max flow (Princeton 2001)

http://www.cs.princeton.edu/~wayne/cs423/lectures/max-flow-applications

min cost perfect matching LP

https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture11.pdf

تبدیل مسایل بهینه سازی و تصمیم گیری ان‌پی

http://courses.csail.mit.edu/6.006/spring11/lectures/lec25.pdf

تلفظ!

clique  [kliːk]

جلسه دوم: مسایل ان‌پی

مروری بر الگوریتم کارشناسی! (چون بقیه‌اش خیلی آسون بود!)

2-SAT

Construct the implication graph of the instance, and find its strongly connected components using any of the known linear-time algorithms for strong connectivity analysis.

Check whether any strongly connected component contains both a variable and its negation. If so, report that the instance is not satisfiable and halt.

Construct the condensation of the implication graph, a smaller graph that has one vertex for each strongly connected component, and an edge from component i to component j whenever the implication graph contains an edge uv such that u belongs to component i and v belongs to component j. The condensation is automatically a directed acyclic graph and, like the implication graph from which it was formed, it is skew-symmetric.

Topologically order the vertices of the condensation. In practice this may be efficiently achieved as a side effect of the previous step, as components are generated by Kosaraju's algorithm in topological order and by Tarjan's algorithm in reverse topological order.[7]

For each component in this order, if its variables do not already have truth assignments, set all the terms in the component to be false. This also causes all of the terms in the complementary component to be set to true.

http://en.wikipedia.org/wiki/2-satisfiability

دور اویلری:

Fleury's algorithm is a straightforward algorithm for finding Eulerian paths/tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian. A version of the algorithm, which finds Euler tour in undirected graphs follows.

Start with any vertex of non-zero degree. Choose any edge leaving this vertex, which is not a bridge (i.e. its removal will not disconnect the graph into two or more disjoint connected components). If there is no such edge, stop. Otherwise, append the edge to the Euler tour, remove it from the graph, and repeat the process starting with the other endpoint of this edge.

Though the algorithm is quite simple, it is not often used, because it needs to identify bridges in the graph (which is not a trivial thing to code.) Slightly more sophisticated, but easily implementable algorithm is presented below.

***

Cycle finding algorithm

This algorithm is based on the following observation: if C is any cycle in a Eulerian graph, then after removing the edges of C, the remaining connected components will also be Eulerian graphs.

The algorithm consists of finding a cycle in the graph, removing its edges and repeating these steps with each remaining connected component. It has a very compact code with recursion:

'tour' is a stack

find_tour(u):

for each edge e=(u,v) in E:

remove e from E

find_tour(v)

prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),

where u is any vertex with a non-zero degree.

**

Algorithm for undirected graphs:

1)Start with an empty stack and an empty circuit (eulerian path).

- If all vertices have even degree - choose any of them.

- If there are exactly 2 vertices having an odd degree - choose one of them.

- Otherwise no euler circuit or path exists.

2)If current vertex has no neighbors - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.

3)Repeat step 2 until the current vertex has no more neighbors and the stack is empty.

Note that obtained circuit will be in reverse order - from end vertex to start vertex.

http://en.wikipedia.org/wiki/Eulerian_path

http://www.algorithmist.com/index.php/Euler_tour

http://www.graph-magics.com/articles/euler.php

مولفه‌های قویاً همبند گراف:

http://en.wikipedia.org/wiki/Strongly_connected_component#Algorithms

http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

http://en.wikipedia.org/wiki/Path-based_strong_component_algorithm

اولی رو من سر کلاس گفتم، دومی رو استاد سر کلاس گفتند و سومی رو هم بلد نیستم! :))

tractability:

Tractable Problem: a problem that is solvable by a polynomial-time algorithm. The upper bound is polynomial.

Intractable Problem: a problem that cannot be solved by a polynomial-time algorithm. The lower bound is exponential.

البته سه نوع مسأله به وجود می‌آید:

– Problems with known polynomial-time algorithms.

– Problems that are provably intractable (proven to have no polynomial-time

algorithm).

– Problems with no known polynomial-time algorithm but not yet proven to be

intractable.

در ضمن نمی‌شود با اثبات اینکه خروجی نمایی است ثابت کرد که الگوریتم هم نمایی است.

http://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf

تحلیل سرشکن (پشته)

نحوه‌ی ساخت پشته از پایین به بالا

http://cs.stackexchange.com/questions/11415/how-to-perform-bottom-up-construction-of-heaps

در انتهای آرایه برگها هستند که پدر هیچ گره‌ی دیگری نیستند. حداکثر ارتفاع یک عدد در درخت پشته، log i است که i تعداد عناصر موجود در سمت راست آن در نمایش آرایه است.

پس در مجموع زمان O(n) است پس زمان سرشکن هر عمل O(1) است. (مشابه مثال خرس! می‌توانیم بگوییم که هر بار نصف گره‌های باقیمانده برگ هستند.)

مثال خرس: یک خرس در غار خود گوشت‌های با اندازه‌های 1,...,n دارد و هر روز یا یک گوشت فرد را کامل می‌خورد یا یک گوشت زوج را نصف می‌کند و نصف آن را می‌خورد. خرس اگر هر روز گوشت بخورد زنده می‌ماند. خرس چقدر عمر می‌کند؟

جواب: تحلیل سرشکن زمان 2 را برای هر گوشت می‌دهد. (تعداد روزهایی که خرس را زنده نگه می‌دارد.) پس خرس 2n روز زنده می‌ماند.

T(n) = n+T(n/2) = n(1+1/2+1/4+...) = 2n

(تصاعد هندسی)

سوالهای کنکور دکتری (نرم افزار)

http://www6.sanjesh.org/Download/Doctora93Q/2354.pdf

اصلاً معلوم نیست کیا سوالها رو طرح کردن که! :)

ولی الآن یک سوال برای من پیش اومد اینکه سوالهای الگوریتم رو ما باید جواب بدیم؟ کلش ۴۵ تا سواله ولی ۲۰ تای اولش الگوریتمه! (در ضمن چطوری اونهایی که درس پردازش موازی نگرفتن می‌خوان سوالی مثل سوال 20 رو جواب بدن؟)

حداقل این شد که این اتفاقات اخیر من را مطمئن کرد که نمی‌خواهم توی شریف بمونم. فقط می‌مونه اینکه برم خارج یا برگردم امیرکبیر. با توجه به اینکه دومی آسون‌تر به نظر می‌رسه شاید اون بهتر باشه.

الآن سایت سنجش رو نگاه کردم دیدم نوشته الگوریتم و ساختمان داده مرور درس‌های کارشناسیه! :)) به جز این استعداد تحصیلی و زبان هم باید امتحان بدیم.

حالا فعلاً که سایت آموزش قطعه ولی وقتی وصل شد چک می‌کنم چی به چیه.

تست‌ها رو هم زدم بعد دیدم که جواب ندارن! :)) حالا یا می‌گردم جوابش رو پیدا می‌کنم یا خودم حل می‌کنم میذارم یا کلاً یادم میره! :)

نوشتن عدد در مبنای فیبوناچی

در این سوال هدف نوشتن یک عدد با ارقام ۰ و ۱ است که iامین رقم از سمت راست اگر ۱ باشد یعنی Fi (عدد فیبوناچی i-ام) واحد به عدد اضافه می‌شود.

مبنای فیبوناچی را می‌توان به صورت یکتا به دست آورد اما اینجا مهم نیست کدام یک از این حالت‌ها ساخته شود. (در حالت عادی می‌توان هر عدد را به چند صورت در مبنای فیبوناچی نوشت.)

می‌خواهیم طوری عدد را بسازیم که زمان یک واحد افزایش و کاهش عدد به صورت سرشکن ثابت باشد. (در صورت سوال گفته درج و حذف که احتمالاً منظورش این بوده است که عدد را به صورت یک رشته در نظر بگیریم، هر چند باز هم معنی حذف و درج با افزایش و کاهش متفاوت است)

حل:

برای کاهش و افزایش یک عدد در مبنای فیبوناچی، چون دو عدد اول در فیبوناچی ۱ هستند، حالتی که یکی از دو رقم ۰ باشد (هنگام افزایش) یا ۱ باشد (هنگام کاهش) به سادگی می‌توانیم با تغییر این بیت عدد را بسازیم.

(این داستان ادامه دارد...)

تحلیل سرشکن (amortized analysis)

اینجا هدف این است که هزینه‌ی یک عمل را بدون توجه به ورودی به دست بیاوریم. مثلاً اگر یک شمارنده بیتی داشته باشیم، هزینه‌ی هر بار زیاد کردنش میشه هزینه‌ی شمردن تا عددی که الآن توی شمارنده هست:

ولی اگر بخواهیم مستقل از مقدار فعلی شمارنده به دست بیاوریم، زمانش O(1) می‌شود.

روش‌های تحلیل سرشکن:

روش انبوهه (aggregate): جمع هزینه‌ی کل اعمال تقسیم بر تعداد اعمال

روش حسابداری (accounting): یک مخزن پول (تعداد اعمال) داریم و برای هر عمل یک هزینه داریم.

روش تابع پتانسیل (potential function): یک تابع پتانسیل تعریف می‌کنیم و هزینه‌ی هر عمل را به صورت cost+pot(i)-pot(i-1) تعریف می‌کنیم.

... (اینترنت قطع بود خودم تنهایی خوندم! منبع اسلایدهای الگوریتم پیشرفته)