بایگانی مهر ۱۳۹۳ :: مباحث الگوریتمی

۶ مطلب در مهر ۱۳۹۳ ثبت شده است

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

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: