اخبار فناوری و شبکه

وقتی که گوشی هوشمند هر حرکت شما را ردیابی می کند

اگر دارای یک گوشی هوشمند اندرویدی یا یک آی‌فون هستید احتمال این که هر حرکت شما مکان به مکان و این که دقیقا چه زمانی آنجا بوده اید، ردیابی شود وجود دارد.

ادامه مطلب ...

Ali پنج‌شنبه 3 دی 1394 ساعت 08:08

0 نظر

9 ویژگی خوب که iOS می‌تواند از اندروید الگو بگیرد

اگر بخواهیم انصاف به خرج بدهیم، باید اعتراف کنیم که در چند سال گذشته گوگل بر روی تجربه کاربری اندرویدی و بهبود محیط کلی سیستم‌عامل حسابی وقت گذاشته و اکنون آن فاصله‌ای که با تجربه کاربری از یک دستگاه iOS بدست می‌آمد را بسیار کم کرده است.

ادامه مطلب ...

Ali چهارشنبه 2 دی 1394 ساعت 19:11

0 نظر

الگوریتم کراسکال

در نظریه گراف، الگوریتم کراسکال الگوریتمی برای یافتن یک زیرگراف فراگیر همبند با کمترین وزن در یک گراف وزن‌دار است (در یک گراف وزن دار، به هر یال وزنی نسبت داده شده‌است). همچنین این الگوریتم برای یافتن کوچکترین درخت فراگیر در یک گراف وزن دار استفاده می‌شود.

به عنوان مثال فرض کنید یک شبکه راه آهن که تعدادی شهر را به یکدیگر متصل می‌کند در دست احداث است می‌خواهیم با داشتن هزینه ${c_{ij}}$ مربوط به احداث خط مستقیم بین شهرهای ${v_i},{v_j}$ شبکه را طوری طراحی کنیم که مجموع هزینه‌های ساخت به کمترین مقدار خود برسد. با در نظر گرفتن هر شهر به عنوان یک راس از گراف وزن دار با وزن‌های $w({v_i},{v_j})={c_{ij}}$ مسئله به یافتن یک زیر گراف فراگیر همبند با کمترین وزن در یک گراف منجر می‌شود.

فرض کنید وزن‌ها نامنفی هستند بنابراین می‌توانیم تصور کنیم که زیر گراف فراگیر با کمترین وزن یک درخت فراگیر $T$ از $G$ است حال الگوریتم زیر را برای این کار ارائه می‌دهیم.

محتویات

الگوریتم کراسکال

یال پیوندی $e_1$ را طوری انتخاب کن که وزن آن کوچکترین مقدار موجود باشد.
اگر یال‌های انتخاب شده‌اند یال را از میان به گونه‌ای انتخاب کن که:
- زیرگراف با یال‌های ${e_1},{e_2},{...},{e_{i+1}}$ بدون دور باشد.
- از میان یال‌های مشمول شرط (الف) وزن ${e_{i+1}}$ دارای کمترین مقدار ممکن باشد.
در صورتی که مرحله ۲ دیگر قابل اجرا نیست توقف کن.

برنامهٔ Graph Explorer

دانلود سورس از لینک زیر

http://www.programyar.com/?p=5183%7B%7Bسخ}}

نمونه‌ای از خروجی برنامه:

مثال

تصویر	توضیحات
	یال‌های AD و CE کوتاه‌ترین یال‌های گراف هستند با طول ۵، یال AD به طور دلخواه انتخاب می‌شود، که به رنگ سبز نشان داده شده است.
	حالا CE کوتاه‌ترین یال است با طول ۵، در صورت انتخاب CE دور ایجاد نمی‌شود، پس یال CE به عنوان دومین یال درخت فراگیر انتخاب می‌شود.
	یال بعدی که باید انتخاب شود یال DF می‌باشد با طول ۶.
	در این مرحله کوتاه‌ترین یال‌ها AB و BE می‌باشند با طول ۷، در اینجا یال AB را به طور دلخواه برمی‌گزینیم. یال BD که در تصویر به رنگ قرمز نشان داده شده است، به این معنی است که در انتخاب‌های بعدی نمی‌توان این یال را انتخاب نمود، زیرا انتخاب این یال باعث ایجاد دور(ABD) در درخت فراگیر می‌شود.
	در ادامه، کوتاه‌ترین یال بعدی یعنی BE انتخاب می‌شود با طول ۷. در این مرحله یال‌های BC و DE و FE با رنگ قرمز نشان داده شده‌اند زیرا انتخاب هرکدام موجب ایجاد دور می‌شود.
	سرانجام الگوریتم با انتخاب یال EG با طول ۹ پایان می‌پذیرد و درخت پوشای کمینه ایجاد می‌شود.

اثبات

ثابت می‌کنیم هر درخت فراگیر $U$ با یال‌های ${e_1},{e_2},{...},{e_{v-1}}$ که با الگوریتم کراسکال ساخته شود یک درخت بهینه‌است.

از طریق تناقض: به ازای هر درخت فراگیر $T$ از $G$ به غیر از $U$ کوچکترین مقدار $i$ را به طوری که ${e_i}$ در $T$ نباشد با $f(t)$ نمایش می‌دهیم. اکنون فرض کنید که $U$ یک درخت بهینه نباشد و $T$ را به عنوان درخت بهینه در نظر بگیرید که در آن $f(t)$ دارای بزرگترین مقدار ممکن باشد. فرض کنید $f(t)=k$ این بدان معنی است که ${e_{k-1}},{...},{e_2},{e_1}$ هم در $T$ و هم در $U$ هستند؛ ولی ${e_k}$ در $T$ نیست پس شامل یک دور یکتای $C$ می‌باشد. فرض کنید ${{e^'}_k}$ یالی از $C$ باشد که در $T$ هست ولی در $U$ نیست. پس ${{e^'}_k}$ یال برشی ازT+ ${e_k}$ نیست؛ بنابراین ${T^'}=(T+{e_k}-{{e^'}_k})$ یک گراف همبند با $v-1$ یال بوده در نتیجه درخت فراگیر دیگری برای $G$ خواهد بود. روشن است که:

$w({T^'})=w(T)+w({e_k})-w({{e^'}_k})$

ولی در الگوریتم کراسکال ${e_k}$ به عنوان یالی با کمترین وزن طوری انتخاب شده‌است که زیرگراف $G$ با یال‌های ${e_k},{...},{e_2},{e_1}$ بدون دور باشد. چون زیرگراف $G$ با یال‌های ${{e^'}_k},{...},{e_2},{e_1}$ زیر گرافی از $T$ است. بنابرین ان هم بدون دور است و نیتجه می‌گیریم که:

$w({{e^'}_k})$ ≥ $w({{e}_k}),$

پس

$w({{T^'}})$ ≤ $w({{T}}),$

پس ${T^'}$ هم یک درخت بهینه خواهد بود در صورتی که داریم:

$f({T^'})>k=f(T)$

که این با $T$ انتخاب در تناقض است. بنابرین $T=U$ و در نتیجه $U$ یک درخت بهینه‌است.

شبه کد الگوریتم کراسکال

مسئله:یک درخت پوشای می نیمم مشخص کنید.

ورودی:عدد صحیح n>=۲، عدد صحیح مثبت m و یک گراف بدون جهت و وزن دار و متصل شامل n گره و m لبه. گراف با یک مجموعه E که شامل لبه‌های گراف همراه با وزن‌های آنها است نشان داده می‌شود

خروجی:مجموعه‌ای از لبه‌ها F در یک درخت پوشا مینیمم

* Void kruskal (int n , int m ,
* set _of_edges E,
* set_of_edges & F)
* {
* index i, j;
* Set_pointer p , q ;
* edge e;
* Sort the m edges in E by weight in nondecreasing order ;
* F=∅;
* initial(n);          //زیر مجموعه غیر الحاقی n مقدار دهی
* While(number of edges in F is less than n-1){
* e= edge with least weight not yet considered;
* i, j = indices of vertices connected by e ;
* p=find(i);
* q=find(j);
* if(!equal(p,q)){
* merge(p,q);
* add e to F ;
* }
* }
* }

هرگاه n-1 لبه در F وجود داشته باشد، از حلقه whileخارج می‌شویم؛ زیرا در اینصورت، n-1 لبه در یک درخت پوشا وجود خواهد داشت

void sort(struct krus ed[],int m)
{
  struct krus temp;
  for (int i=۰;i<m;i++)
  for (int j=i+1;j<m;j++)
  if (ed[j].weight<ed[i].weight)
  {
  temp=ed[i];
  ed[i]=ed[j];
  ed[j]=temp;
  }
}

Ali چهارشنبه 2 دی 1394 ساعت 19:04

0 نظر

الگوریتم پریم

الگوریتم پریم، الگوریتمی در نظریه گراف‌ها است که زیردرخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا می‌کند یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف می‌یابد که درختی را تشکیل می‌دهند که همه رئوس را شامل می‌شود در حالیکه مجموع وزن همه آن یال‌ها کمینه شده‌است. این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد وسپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. ازاین رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته می‌شود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.

محتویات

شرح الگوریتم

این الگوریتم مرتب سازی درخت را که از یک یال شروع شده‌است، افزایش می‌دهد تاجائی که همه رئوس وارد درخت شوند.

این الگوریتم را به طور خلاصه می‌توان چنین شرح داد:

ورودی: یک گراف همبند وزن دار با مجموعه رئوس V و یالهای E
مقدار دهی اولیه: {V_new = {x که V_new مجموعه رئوس درخت پوشای کمینه در حالت آغازین را نشان می‌دهد و x یک راس دلخواه است (نقطه شروع) و
{} = E_new که E_new بیانگر مجموعه یالهای این درخت است.
حلقه زیر را تا وقتی که V_new = V تکرار کن:
- یال (u,v) را با وزن کمینه انتخاب کن به طوری که u در V_new قرار داشته باشد ولی v عضوی از این مجموعه نباشد (اگر چند یال باوزن یکسان وجود دارند یکی را به دلخواه انتخاب کن)
- راس v را به V_new و یال (u , v) رابه E_new اضافه کن.
خروجی :V_new و E_new درخت پوشا. کمینه را توصیف می‌کنند.

نکته: الگوریتم پریم را به این صورت نیزمی توان بیان کرد:ابتدا گره ای به دلخواه انتخاب شود و سپس از بین یالهای متصل به آن یالی با کمترین وزن انتخاب می شود به گونه ای که حلقه ایجاد نشود.در هر مرحله یالی انتخاب می شود که حتماً یکی از دو سرآن جزو مسیر جواب بوده و وزن حداقل داشته باشد.پس درالگوریتم پریم دو محدودیت در هر مرحله داریم یکی آن که جنگل ایجاد نشود و دوم آنکه حلقه پدید نیاید.

از آنجا که درالگوریتم پریم درهرمرحله فاصله هر گره با گره های قبلی مقایسه می شود پس بدیهی است که ازمرتبه (n2)Ѳ می باشدکه n تعداد رئوس گراف است.

هزینه زمانی

یک پیاده سازی ساده، استفاده از نمایش گراف به صورت ماتریس مجاورت است که درآن به دنبال آرایه‌ای از وزنها باشیم و یال‌های با وزن کمینه را به مجموعه خود بیفزائیم. این روش (O(V^۲ زمان می‌برد. الگوریتم پریم بااستفاده از داده ساختار هیپ دودوئی ساده و نمایش فهرست مجاورت می‌تواند در زمان (O(E log V اجرا شود که در آن E تعداد یالها و V تعداد رئوس است. استفاده از مدل پیچیده تری به نام هیپ فیبوناچی باعث می‌شود این زمان تا حد (O(E + V log V کاهش یابد. سرعت این روش به خصوص زمانی آشکار می‌شود که در گراف رابطه (E = ω(V بین رئوس و یالها برقرار باشد.

مثال

شکل	شرح
	این شکل گراف وزن دار اصلی را نشان می‌دهد. اعداد کنار هر یال بیانگر وزن آن یال هستند.
	راس D به طور دلخواه به عنوان نقطه ی شروع انتخاب شده‌است. رئوس A، B، E، F همگی با یالی به D متصل هستند. A نزدیک ترین راس به D است بنابراین همراه با یال AD برای درخت انتخاب می‌گردد.
	راس بعدی که انتخاب می‌شود باید نزدیک ترین راس به A یاD باشد. فاصله B از D برابر ۹ و فاصله آن از A برابر ۷ است. فواصل E وF نیز به ترتیب ۱۵ و ۶ می‌باشد. راس F کمترین فاصله را دارد بنابراین این راس و کمان DF را انتخاب می‌کنیم.
	الگوریتم مشابه بالا ادامه می‌یابد و راس B که فاصله اش از A برابر ۷ است انتخاب می‌شود.
	در این حالت انتخاب ما بین C، E، G می‌تواند صورت گیرد. فاصله C از B برابر ۸، فاصله E ازآن برابر ۷ و فاصله G از F نیز ۱۱ است. مشاهده می‌شود که E نزدیک ترین راس است پس آن را همراه با کمان BE انتخاب می‌کنیم.
	در اینجا تنها رئوس C و G باقی‌مانده‌اند. فاصله C از E برابر ۵ و فاصله G از آن ۹ است پس C انتخاب می‌شود و کمان CE نیز همزمان با آن وارد درخت می‌گردد.
	تنها راس باقی‌مانده G است که چون فاصله اش از E کمتر از فاصله اش تا F می‌باشد، یال EG را انتخاب می‌کنیم.
	در پایان همه رئوس انتخاب شده‌اند و درخت پوشای کمینه با رنگ سبز نشان داده شده‌است که وزنی برابر ۳۹ دارد.

شبه کد الگوریتم پریم

مسئله:یافتن کوچکترین درخت پوشا.

ورودی: عدد صحیح n>=2و یک گراف بدون جهت و وزن دار و پیوسته شامل n گره . گراف توسط یک آرایه دو بعدی w که سطر ها و ستونهایش ار 1 تا n شاخص دهی شده اند نشان داده می شود که در ان [w[i][j معرف وزن لبه بین گره i ام و گره j ام است .

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

* void prim( int n,
*       const  number w[][],
*        set_of_edges  & F)
* {
*  index i, vnear;
*  number min ;
*  edge e;
*  index nearest[2..n];
*  number distance[2..n];
*  F = ∅ ;
*  for ( i = 2; i<=n;i++){
*    nearest[i] = 1 ;               
*    distance[i] = W[1][i];
*  }
*  repeat (n-1 times ){
*   min=∞;
*   for(i=2; i<=n; i++){
*     if(0≤ distance[i] <min ){
*       min = distance [i];
*       vnear = I  ;
*      }
*    e= edge connecting vertices indexed  by vnear and nearest[vnear  ];
*    add e to F ; 
*    distance[vnear]= -1
*    for ( i=2 ; i<= n ;i++)
*      if(W[i][vnear] <distance[i]){
*        distance[i] = w[i][vnear];
*        nearest[i] = vnear;
*       }
*     }
*   }

اگر در لحظه شروع {y={v1 باشد،لذا [nearest[i با 1 و [distance[i با وزن لبه بین v1 و vi مقدار دهی اولیه میشود.همانطوری که گره ها به Y اضافه میشوند،این دو ارایه برای ارجاع گره جدید در Y به نزدیکترین گره خارج از Y ، بهنگام (update)میشوند.برای معین کردن گره ای که باید به Y اضافه شوند ،در هر تکرار ،شاخصی که مقدار distance[i]1 ان مینیمم است را محاسبه می کنیم. این شاخص را vnear می نامیم. با مقداردهی [distance[vnear به1- ، گره با شاخص vnear به Y اضافه می گردد . الگوریتم بالا این روال را پیاده سازی میکند

if (y!=0)

{

   p+=e.weight;
     cout<<"("<<e.v1<<","<<e.v2<<") => W :"<<e.weight<<"\t";
      set[e.v1]=0;
      set[e.v2]=0;
        fe++;
        }
        else
              break;
  }
  return p;

 }

منبع: ویکی پدیا

Ali چهارشنبه 2 دی 1394 ساعت 19:03

0 نظر

درخت های پو شای کمینه

فرض کنید طراح شهری می خواهد چند شهر معین را با جاده به هم وصل کند، به قسمی که مردم بتوانند از هر شهر به شهر دیگر بروند. اگر محدودیت بودجه ای در کار باشد ، ممکن است طراح بخواهد این کار را با حداقل مقدار جاده کشی انجام دهد.

برای این مسئله دو الگوریتم حریصانه متفاوت : پریم و کروسکال بررسی می شود.

هر یک از این الگوریتم ها از یک ویژگی بهینه محلی استفاده می کند.

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

پیچیدگی زمانی این دو الگوریتم:

(T (n) = 2 ( n – 1) ( n – 1) Є θ ( n²

Ali چهارشنبه 2 دی 1394 ساعت 19:01

0 نظر

راهبرد عقبگرد

از تکنیک عقبگرد برای حل مسائلی استفاده می شود که در آن ها دنباله ای از اشیاء از یک مجموعه مشخص انتخاب می شود، به طوری که این دنباله ، ملا کی را در بر می گیرد.

یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.

هدف از مسئله n وزیر ، چیدن n مهره وزیر در یک صفحه شطرنج است ، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.

عقبگرد حالت اصلاح شده ی جست و جوی عمقی یک درخت است.

الگوریتم عقبگرد همانند جست و جوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می شوند که گره امید بخش باشدو در آن گره حلی وجود نداشته باشد.

Ali چهارشنبه 2 دی 1394 ساعت 19:00

0 نظر

تحلیل و بررسی الگوریتم کروسکال

عمل اصلی: یک دستور مقایسه.

اندازه ورودی : n ، تعداد رئوس و m تعداد یال ها.

نکته: الگوریتم کروسکال همواره یک درخت پوشای کمینه تولید می کند.

اثبات : اثبات از طریق استقرا با شروع از مجموعه ای تهی از یال ها آغاز می شود.

void kruskal ( int n , int m,set _ of _ edges E,set _ of _edges & F )
index i , j ;
set _pointer p , q;
edge e ;
sort the m edges in E by weight in
nondecreasing order;
F = Ø ;
intitial (n) ;
while( number of edges in F is less than n-1){
e = edge with least weight not yet
considered ;
i , j = indices of vertices connected by e;
p = find (i) ;
q = find (i) ;
if (! equal ( p, q )) {
merge ( p , q ) ; add e to F ;
}

Ali چهارشنبه 2 دی 1394 ساعت 19:00

0 نظر

تحلیل الگوریتم پریم

void prim ( int n,const number W[ ] [ ],set_ of_edges & F )
{
index i , vnear;
number min;
edge e;
index nearest [2..n];
number distance [2..n];
F = Ø ;
for ( i = 2 ; i ≤ n ; i ++) {
narest [i] = 1 ;
distance [i] = W [1] [i] ;
}
repeat ( n-1 times ) {
min = ∞ ;
for ( i = 2 ; i < = n ; i ++)
if ( 0 ≤ distance [i] < min ) {
min = distance [i] ;
vnear = i ;
}
e = edge connecting vertices indexed by near and nearest [ vnear ] ;
add e to F ;
distance [ vnear ] = -1 ;
for ( i = 2 ; i ≤ n ; i ++)
if ( W[i] [ vnear ] < distance [i]) {
distance [i] = W [i] [ vnear ] ;
nearest [i] = vnear ;
}
}
}

Ali چهارشنبه 2 دی 1394 ساعت 18:59

0 نظر

باید این نکته را هم به خاطر داشته باشیم که زنان نیز نقشی اساسی در تکنولوژی دارند. در طول تاریخ زنانی بودند که با نوآوری‌های خود تحولی را در دنیای تکنولوژی به وجود آورده‌اند. ادامه مطلب ...

Ali شنبه 21 آذر 1394 ساعت 15:36

0 نظر

اگر شما عاشق کامپیوتر هستید، کمی استعداد طراحی و گرافیکی دارید و از انجام کارهای خلاقانه لذت می برید، این شغل مناسب شماست. طراح وب از خلاقیت و مهارت های فنی خود برای ایجاد و طراحی وب سایت ها استفاده می کند. ادامه مطلب ...

Ali سه‌شنبه 17 آذر 1394 ساعت 21:23

0 نظر

کتاب‌های علمی‌تخیلی که آینده را دقیق پیش بینی کرده‌اند

هنگامی که مری شلی در سال 1818 کتاب «فرانکشتاین» را نوشت علم در ابتدای کشف قلمرو جدید احیا بافت های مرده از طریق برق بود. اگرچه روش های اولیه ناپخته بودند اما مسیر را برای پیشرفت های پزشکی آینده مانند پیوند اندام همان گونه که در رمان مری شلی به آن اشاره شده بود، هموار کردند.

ادامه مطلب ...

Ali سه‌شنبه 17 آذر 1394 ساعت 20:05

0 نظر

«لایف‌پرینت»؛ چاپگر بی سیم با پشتیبانی از واقعیت افزوده

افزون بر چاپ عکس های عادی، لایف‌پرینت با استفاده از فناوری واقعیت افزوده هایپر فوتو می تواند یک ویدئو را در هر عکس چاپ شده جای دهد و از عکس های اپل لایو، ویدئوهای واین، فرمت GIF، و ویدئوهای دوربین های گو پرو نیز پشتیبانی می کند.

ادامه مطلب ...

Ali سه‌شنبه 17 آذر 1394 ساعت 20:03

0 نظر

Ali یکشنبه 15 آذر 1394 ساعت 19:56

0 نظر

شعری از حمید مصدق

چه انتظار عظیمی نشسته در دل ما

همیشه منتظریم و کسی نمی آید

ادامه مطلب ...

Ali یکشنبه 15 آذر 1394 ساعت 09:56

0 نظر

از اینترنت 5G چه می‌دانید؟

اینطور فرض کنید که قادر خواهید بود یک فیلم سینمایی کامل را در عرض تنها 1 ثانیه در گوشی هوشمند خود دانلود نمایید. بله، اکنون دید بهتری نسبت به سال 2020 خواهید داشت!

ادامه مطلب ...

Ali چهارشنبه 11 آذر 1394 ساعت 19:14

0 نظر

من اینجا بس دلم تنگ است

ادامه مطلب ...

Ali یکشنبه 8 آذر 1394 ساعت 19:34

0 نظر

نظرسنجی

جدیدترین یادداشت‌ها

بایگانی

تقویم

جستجو

محتویات

الگوریتم کراسکال

برنامهٔ Graph Explorer

مثال

اثبات

شبه کد الگوریتم کراسکال

محتویات

شرح الگوریتم

هزینه زمانی

مثال

شبه کد الگوریتم پریم