بایگانی دسته‌ها: الگوریتم

Volunia ،گوگل را به مبارزه دعوت می کند

Massimo Marchiori استاد ریاضیات دانشگاه پادوا ایتالیا با توسعه  الگوریتم جستجو گوگل و بهینه کردن آن موتور جستجو خود را به نام volunia.com. را تا پایان سال جاری آماده سازی خواهد کرد که «گوگل» را به چالش خواهد کشاند.در فیلمی که در سایت مذکور نشان داده می شود Massimo Marchiori در حالی که با تخته وایت برد روی صندلی پارک نشسته است توضیح می دهد:»که گوگل در سرویس جدید خود موسوم به گوگل پلاس فقط 10 درصد ازدیدگاههای نوین رادیکالی که در زمینه جستجو بهینه در مرورگرهای آینده بکار میرود را عملی کرده است.»

این وب سایت به کاربران خود اجازه می دهد که در نسخه آزمایشی (بتا) با ثبت نام در این سایت سطح دسترسی «Power User» داشته باشند و موتور جستجو فوق را که  به 12 زبان راه اندازی شده است را آزمایش کنند.(قابل توجه برنامه نویسان) او همچنین در مصاحبه ی که هفته گذشته با شبکه آنلاینCorriere della Sera انجام داده بود گفته است که Volunia رقیب اصلی گوگل خواهد شد.او در ادامه مصاحبه خود گفته است اگر چه گوگل شرکت بسیار عظیم در این مقوله است که 100 ها مهندس در 24 ساعت شبانه روز در آنجا مشغول فعالیت هستند ؛اما با توجه به این اطلاعات من فکر می کنم با ارائه این موتور جستجو جدید بتوانیم با گوگل رقابت جدی داشته باشیم.

Marchiori عضو هیئت مدیره تیم برنرز لی کنسرسیوم شبکه جهانی وب (W3C) است وبر روی بستر های نرم افزاری مورد نیاز برای تنظیمات حریم خصوصی (P3P) و زبان  Ontology وب (OWL) کار کرده است. الگوریتم جستجو  او در یک کنفرانس در کالیفرنیا در سال 1996، که توسط لری پیج 23 ساله در آن شرکت شده بود ارائه شد.  که بعدها به الگوریتم پیج رنک گوگل سیستم نام گذاری شد.گفتنی است که سرورها جدید این موتور جستجو توسط Sardinia وTiscali آماده سازی شده است.

او همچنین گفت ساخت این موتور جستجو با همکاری 20 دانشجو وی و با کمک مالی دولت و شرکت مخابراتی Pireddu انجام شده است.

برای خواندن اطلاعات تکمیلی به این پیوند مراجعه کنید.

Advertisements

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

کتاب طراحی الگوریتم نوشته نئو پولیتان -مرجع اصلی(به زبان فارسی)

دانلود(Pdf)

 

 

به توان رساندن با استفاده از جمع های متوالی

در عمل به توان رساندن، مثلا 4 به توان دو، عدد 4 در خودش ضرب می شود. اما خود عمل ضرب هم این طور است که عملوند اول به میزان عدد عملوند دوم ، جمع می شود،مثلا حاصل ضرب دو عدد 6 در 3 را می توان به صورت جمع های متوالی 6 + 6 +6 محاسبه کرد.  در متدهای زیر، به توان رساندن یکبار با  استفاده از عملگر ضرب خود #C انجام شده، و بار دیگر در تابع MyPower برای ضرب کردن از متد خودفراخوان Multiply بهره برده ایم. ر استی این ابتکار خودم هستش :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace powerRecursive
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Number 1 :\t");
            int n = Int32.Parse(Console.ReadLine());
            Console.Write("Number 2 :\t");
            int m = Int32.Parse(Console.ReadLine());
            Console.WriteLine("Power {0} ^ {1} : {2}", m, n, Power(n, m));

            Console.WriteLine("\nMultiply {0} * {1} : {2}", m, n, multiply(n, m));

            Console.WriteLine("\nMy Power {0} ^ {1} : {2}", m, n, MyPower(n, m));
        }

        static int multiply(int a, int b)
        {
            int result = 0;

            if (b != 0)
            {
                result += a + multiply(a, b - 1);
            }

            return result;
        }

        public static int MyPower(int a, int b)
        {
            int Pow = 1;
            if (b != 0)
            {
                Pow = multiply(Pow, multiply(a, MyPower(a, b - 1)));
            }
            else
            {
                Pow = 1;
            }
            return Pow;
        }

        public static int Power(int a, int b)
        {
            int Pow = 1;
            if (b != 0)
            {
                Pow *= a * Power(a, b - 1);
            }
            else
            {
                Pow = 1;
            }
            return Pow;
        }
    }
}

تبدیل یک عبارت ریاضی Infix به Postfix

دوستان عزیز در چند پست قبلی، مطلبی با همین عنوان به اشتباه منتشر شد، که در حفیفت محاسبه ی عبارت ریاضی Postfix بود، در این مطلب تبدیل یک عبارت ریاضی Infix(میان وندی) را به یک عبارت Postfix (پیشوندی) که به زبان  #C نوشته شده می بینید :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Collections;// برای استفاده از استک

namespace infixToPostfix
{
    class Program
    {
        static void Main(string[] args)
        {
            InfixToPost obj = new InfixToPost();

            obj.Convert("a+b*c-d");
            //resutl is abc*+d-
        }
    }

    class InfixToPost
    {
        Stack S = new Stack();

        public void Convert(string x)
        {
            string output = "";
            for (int i = 0; i = priority(c))
                        output += S.Pop();
                    S.Push(c);
                }
                else if (c == '(')
                {
                    S.Push(c);
                }
                else if (c == ')')
                {
                    while (!S.Peek().Equals('('))
                        output += S.Pop();
                    S.Pop();
                }
                else
                    output += c;
            }
            while (S.Count!=0)
                output += S.Pop();
            Console.WriteLine("THE INFIX = " + x);
            Console.WriteLine("THE POSTFIX = " + output);
        }
        public int priority(object x)
        {
            if (x.Equals('+') || x.Equals('-'))
                return 1;
            else if (x.Equals('*') || x.Equals('/'))
                return 2;
            else
                return 0;
        }
    }
}

محاسبه ی یک عبارت ریاضی Postfix

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Collections;

namespace postFixCalulate
{
    class Program
    {
        static void Main(string[] args)
        {
            string a = "123*+";
            PostFixCal obj = new PostFixCal();
            float result=obj.Calulate(a);

            Console.WriteLine(result);
            //resutl is 7

        }
    }

    class PostFixCal
    {
        Stack stack = new Stack();
        string members;

        public float Calulate(string term)
        {
            members = term;

            for (int i = 0; i < members.Length; i++)
            {
                if (Char.IsDigit((char)members[i]))
                {
                    stack.Push(members[i].ToString());
                }
                else
                {
                    double y2 = Convert.ToDouble(stack.Pop());
                    double y1 = Convert.ToDouble(stack.Pop());
                    double z = 0;
                    switch ((char)members[i])
                    {
                        case '+':
                            z = y1 + y2;
                            break;
                        case '-':
                            z = y1 - y2;
                            break;
                        case '*':
                            z = y1 * y2;
                            break;
                        case '/':
                            z = y1 / y2;
                            break;
                    }
                    stack.Push(z);
                }
            }

            return Convert.ToSingle(stack.Peek());
        }
    }
}

مرتب سازی لیست پیوندی در #C

در زیر کد مرتب سازی لیست پیوندی یک طرفه را می بینید:

        public void SortList()
        {
            Node a, b, c, e = null;
            Node save;

            while (e != firstNode.next)
            {
                c = a = firstNode;
                b = a.next;

                while (a != e)
                {
                    if (a.data > b.data)
                    {
                        if (a == firstNode)
                        {
                            save = b.next;
                            b.next = a;
                            a.next = save;

                            firstNode = b;
                            c = b;
                        }
                        else
                        {
                            save = b.next;
                            b.next = a;
                            a.next = save;

                            c.next = b;
                            c = b;
                        }
                    }
                    else
                    {
                        c = a;
                        a = a.next;
                    }

                    b = a.next;

                    if (b == e)
                    {
                        e = a;
                    }
                }
            }
        }

جمع بندی الگوریتم های sort

به عنوان جمع بندی برای الگوریتم های مرتب سازی فکر کردم شاید بد نباشد که لینک دانلود full code های مربوط به انواع مرتب سازی را در این مطلب بگذارم.البته همه ی این ها در سایت مرجع که در مطالب قبل گفته شد موجود است.

Bubble sort-1

2-Heap sort

3-Insertion sort

4-Merge sort

5-Quick sort 

6-Selection sort

7-Shell sort

برای دستیابی به کد مرجع کافی است به program.cs کد مراجعه نمایید و برای اجرای برنامه به داخل پوشه ی bin بروید و در پوشه ی Release به فایل اجرایی ( .exe ) دسترسی دارید.

الگوریتم های sort در c#(قسمت هفتم)

ترجمه و آماده سازی: بهنام منتظر
7-Shell sort:
بالاخره نوبت به هفتمین الگوریتم مرتب سازی(هفتمین خوان) رسید.مرتب سازی لایه ای یک مرتب سازی است که با کاهش رشد یا همان ارتقا کار می کند و در واحد های برنامه نویسی خام بیشتر به عنوان مرتب سازی شانه ای شناخته شده است. این الگوریتم با پیمایش های متعدد بر روی لیست کار می کند و در هربار پیمایش مجموعه داده هایی با اندازه های یکسان را به وسیله ی مرتب سازی درجی مرتب می کند.با هر پیمایش که در لیست صورت می گیرد مجموعه ی داده های مرتب شده بیشتر و بیشتر می شود تا مجموعه شامل کل لیست شود.(هر چه اندازه مجموعه ها بیشتر شود ، تعداد مجموعه هایی که باید مرتب شوند کمتر می شود.)

آیتم هایی که در هر مجموعه هستند ترجیحا به هم متصل نیستند،اگر n مجموعه داشته باشیم هر مجموعه از آیتم های n تا در میان تشکیل شده است.به عنوان مثال اگر 3 مجموعه داریم مجموعه ی اول شامل المان هایی است که در مکان های 1، 4، 7 و … قرار دارند.مجموعه ی دوم شامل المان هایی است که در مکان های 2، 5، 8و… قرار دارند.و مجموعه ی سوم شامل المان هایی است که در مکان های 3، 6، 9 و… قرار گرفته اند. اندازه ی مجموعه هایی که برای هر تکرار استفاده می شوند تاثیر اساسی بر بازده مرتب سازی دارد.

مرتب سازی لایه ای 5 برابر سریع تر از مرتب سازی حبابی است و اندکی بیش از دو برابر مرتب سازی درجی ( نزدیک ترین) رقیبش است. مرتب سازی لایه ای از مرتب سازی ادغامی ،پشته ای و سریع عمدتا آهسته تر است ولی الگوریتم ساده ی مرتبت به آن ،آن را به گزینه ای مناسب برای مرتب سازی لیست ها با آیتم های کمتر از 5000 تا «به غیر از جاهایی که سرعت خیلی مهم است «تبدیل کرده است.همچنین برای مرتب سازی های تکراری با آیتم های کمتر بسیار مناسب است.

Read the rest of this entry

الگوریتم های sort در c#(قسمت ششم)

ترجمه و آماده سازی: بهنام منتظر

6-Selection sort:

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

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

اگر شما بنا به دلایلی می خواهید از مرتب سازی انتخابی استفاده کنید،سعی کنید از لیست هایی با بیش از 1000 آیتم و یا لیست های مرتب سازی که تکرار می شوند با بیش از 200 آیتم استفاده نکنید.

Read the rest of this entry

الگوریتم های sort در c#(قسمت پنجم)

ترجمه و آماده سازی: بهنام منتظر

5-Quick sort:

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

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

1- اگر یک المان و یا کمتر برای مرتب شدن در آرایه وجود داشته باشد،سریعا بر می گردد.

2-یک المان را از آرایه بر می دارد و به عنوان نقطه ی محوری قرار می دهد.»معمولا از المانی که در سمت چپ سایر المان ها قرار دارد استفاده می شود»

3-آرایه را به دو قسمت تقسیم می کند»یکی با مقادیر بزرگتر از نقطه ی محوری و دیگری با مقادیر کوچکتر از نقطه ی محوری».

4-به طور بازگشتی الگوریتم را برای دو نیمه دیگر تکرار می کند

Read the rest of this entry

الگوریتم های sort در c#(قسمت چهارم)

ترجمه و آماده سازی:بهنام منتظر

4-Merge sort 

چهارمین الگوریتم مرتب سازی که می خواهیم به شرح آن بپردازیم مرتب سازی ادغامی -Merge sort-است.مرتب سازی ادغامی لیست را به دو قسمت مساوی تقسیم می کند و آن را در دو آرایه جا می دهد.هر آرایه به صورت بازگشتی مرتب می شود،سپس آن ها را دوباره با یکدیگر ادغام می کند تا لیست نهایی مرتب شده را شکل دهند.

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

مرتب سازی ادغامی در مجموعه های بزرگ اندکی سریع تر از مرتب سازی پشته ای-Heap sort- است،ولی به خاطر آرایه ی دوم به حافظه ی دو برابر نسبت به مرتب سازی پشته ای نیاز دارند.این نیاز به حافظه ی اضافی مرتب سازی ادغامی را برای بسیاری از اهداف نا مناسب می کند»مرتب سازی سریع-Quick sort-در بیش تر مواقع گزینه ی مناسب تری است و مرتب سازی پشته ای-Heap sort-برای مجموعه های خیلی بزرگ مناسب تر است».

مرتب سازی ادغامی هم مانند مرتب سازی سریع ساختار بازگشتی دارد که آن را به گزینه ای نامناسب «برای برنامه هایی که روی دستگاه هایی با حافظه محدود اجرا می شوند» تبدیل می کند.

Read the rest of this entry

الگوریتم های sort در c#(قسمت سوم)

ترجمه و آماده سازی : بهنام منتظر

3-Insertion sort

سومین الگوریتم مرتب سازی که بررسی می کنیم الگوریتم مرتب سازی درجی (insertion sort) است. مرتب سازی درجی همان طور که از اسمش پیداست هر آیتم را در جای مناسب در لیست نهایی درج می کند.ساده ترین پیاده سازی این الگوریتم به 2 لیست نیاز دارد»یکی لیستی که آیتم های اولیه در آن قرار دارند و دیگری لیستی که آیتم های مرتب شده در آن قرار می گیرند».برای نگه داشتن حافظه در بیشتر جاهایی که این الگوریتم را پیاده سازی می کنند از یک مرتب سازی به جا استفاده می کنند که این گونه کار می کند که آیتم جاری را به پشت آیتم های مرتب سازی شده می برد و این جا به جایی را با عناصر قبل تا جایی ادامه می دهد که هر آیتم سر جای خودش قرار بگیرد.

تاثیر مرتب سازی درجی اندکی بیش از دو برابر مرتب سازی حبابی است .

مرتب سازی درجی یک انتخاب مناسب برای مرتب سازی لیست هایی با یک یا دو هزار آیتم و یا کمتر است. این الگوریتم به طور قابل توجهی از مرتب سازی لایه ای (Shell sort) ساده تر است البته با اندکی بازدهی پایین تر. در شرایط مشترک مرتب سازی درجی دو برابر سریع تر از مرتب سازی حبابی و 40 درصد از مرتب سازی انتخابی-Selection sort- سریعتر است.مرتب سازی درجی نباید برای لیست هایی با بیش از دو هزار آیتم یا مرتب سازی های تکراری برای لیست هایی با چند صد آیتم یا بیشتر استفاده شود. تکه کد سی شارپ Insertion sort به شکل زیر می باشد:

Read the rest of this entry