منتدى طلاب جامعة الحديدة

أخي الزائر إن لم تكن عضواً في المنتدى فنحن ندعوك لكي تنظم إلينا وشكراً تحيات مدير المنتدى طارق البغوي

انضم إلى المنتدى ، فالأمر سريع وسهل

منتدى طلاب جامعة الحديدة

أخي الزائر إن لم تكن عضواً في المنتدى فنحن ندعوك لكي تنظم إلينا وشكراً تحيات مدير المنتدى طارق البغوي

منتدى طلاب جامعة الحديدة

هل تريد التفاعل مع هذه المساهمة؟ كل ما عليك هو إنشاء حساب جديد ببضع خطوات أو تسجيل الدخول للمتابعة.
منتدى طلاب جامعة الحديدة


2 مشترك

    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix )

    طارق البغوي
    طارق البغوي
    المدير العام للمنتدى
    المدير العام للمنتدى


    ذكر
    عدد الرسائل : 2833
    العمر : 36
    البلد : الجهورية اليمنية
    القسم والمستوى : خريج قسم الرياضيات 2010م
    المزاج : متقلب ( مزاج شاعر )
    أختر علم دولتك : المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Female10
      : المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) 15781610
    السٌّمعَة : 14
    نقاط : 985
    تاريخ التسجيل : 28/09/2007

    بطاقة الشخصية
    تخصصي: رياضيات
    المحافظة: الحديدة

    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Empty المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix )

    مُساهمة من طرف طارق البغوي الأحد ديسمبر 09, 2007 4:06 am

    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) :

    لو ألقينا نظرة على المصفوفة التالية التي تحوي 6 صفوف و6 أعمدة وتتكون من : 6x 6 = 36 عنصر :
    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Sparce_Matrix1

    سيتضح لنا من الوهلة الأولى أن أكثر عناصر هذه المصفوفة عبارة عن " أصفار " ؛ تسمى المصفوفة التي أكثر عناصرها أصفار بـمصفوفة الأصفار أو المصفوفة المتناثرة " Sparse Matrix " .. ومن الصعب علينا تحديد ما إذا كانت المصفوفة عبارة عن Sparse Matrix أو لا .. ولكن يتضح لنا ذلك عن طريق النظر ؛ ففي المصفوفة السابقة يوجد فقط 8 عناصر لا تساوي الصفر من أصل 36 عنصر ؛ بينما البقية كلها أصفار ..
    تستخدم الـ Sparse Matrix لتوفير المساحة في الذاكرة حيث نستطيع تخزين العناصر الغير مساوية للصفر فيها ففقط ؛ وذلك من خلال استخدام مصفوفة وحيدة لكل عنصر من عناصرها يوجد 3 صفات هي : الصف والعمود والقيمة الخاصة به ؛ ويتم ذلك عن طريق استخدامنا لـStructure يحوي هذه الصفات ؛ كالتالي :
    #define MAX_TERMS 10 /* maximum number of terms + 1 */
    typedef struct {
    int row ;
    int col ;
    int value ;
    } sparse;
    sparse a[MAX_TERMS] ;


    ولكن يجب أن نراعي هنا أن ترتيب العناصر في هذه المصفوفة الوحيدة سيكون تابع لأحد هذه الصفات وهو الصف " row " و لابد من أن يكون تصاعدياً ..
    ملاحظة : لتتعلم أكثر عن الـ Structures راجع هذا الدرس للأخ طلال : السجلات في سي " Structures in C "

    إذن .. يتضح لدينا أن تعريف الـ Sparse Matrix كما هو موجود في قاموسنا كالتالي :
    مصفوفة ذات بعد واحد تحوي الكثير من العناصر المتشابهة ، والتي غالباً ما تساوي صفر. ، لكل عنصر فيها ثلاث صفات : الصف ، العمود ، والقيمة التي تسند إليه .
    * Sparse_Matrix : a set of triples < row , col , value > , where row & column are integers & from a unique combination , & value comes from the set item .
    * Sparse_Matrix Create(max_row , max_col) ::= return a Sparse_Matrix that can hold up to max_item = max_row X max_col ,& whose maximum row size is max_row , & whose maximum column size is max_col.

    ومن هنا نستطيع إعادة رسم الـ Sparse Matrix كما في الشكل التالي :
    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Sparce_Matrix2
    حيث أن a[0].row تحتوي عدد الأسطر الكلي للمصفوفة الأصلية ( في هذا المثال = 6 ) , كذلك a[0].col فهي تحوي عدد الأعمدة الكلي للمصفوفة الأصلية ( في هذا المثال = 6 ) , وأيضاً a[0].value عدد العناصر الغير مساوية للصفر فقط ( في هذا المثال = 8 ) .
    ولكي نعرف رقم الصف لأي عنصر ننظر لـ Field row , وبالمثل إذا أردنا أن نعرف رقم العمود فننظر لـ Field col وستكون قيمة هذا العنصر مخزنة في Field value . والثلاثي < row , col , value > سيكون مرتب في المصفوفة على حسب الصفوف " تصاعدياً " كما ذكرنا سابقاً ..
    ولكن كيف نستطيع كتابة شيفرة لإنشاء هذه المصفوفة بلغة السي ؟ هذا ما سنعرفه ان شاء الله خلال الاسطر التالية : سنقوم بالبداية بإنشاء Structure مشابه للمذكور أعلاه .. وسنفترض في مثالنا الحالي أن المصفوفة مكوّنة من 3 صفوف و3 أعمدة ..
    وبعد ذلك نسمح للمستخدم بإدخال العناصر كمصفوفة عادية شريطة أن تكون أكثرها مساوية للصفر ونطبع المصفوفة بالطريقة التقليدية العادية :
    Part1:

    //------------------((( Sparse Matrix )))---------------
    #include
    #define MAX_TERM 10
    typedef struct {
    int row ;
    int col ;
    int val ;
    } sparse;

    int main()
    {
    sparse a[MAX_TERM]; // تعريف المصفوفة الصفرية
    int b[3][3] ; // تعريف مصفوفة عادية
    int i, j, count ;
    printf("Plz. Enter the element one by one with press Enter :n");
    for (i=0 ; i <3 ; i++ ) {
    for (j=0 ; j <3 ; j++ ) {
    scanf("%i",&b[i][j]) ;
    } // end j loop
    } // end i loop

    <div align=left><FONT face="Courier New" size=2><FONT color=#008000>//------------
    طارق البغوي
    طارق البغوي
    المدير العام للمنتدى
    المدير العام للمنتدى


    ذكر
    عدد الرسائل : 2833
    العمر : 36
    البلد : الجهورية اليمنية
    القسم والمستوى : خريج قسم الرياضيات 2010م
    المزاج : متقلب ( مزاج شاعر )
    أختر علم دولتك : المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Female10
      : المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) 15781610
    السٌّمعَة : 14
    نقاط : 985
    تاريخ التسجيل : 28/09/2007

    بطاقة الشخصية
    تخصصي: رياضيات
    المحافظة: الحديدة

    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Empty رد: المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix )

    مُساهمة من طرف طارق البغوي الأحد ديسمبر 09, 2007 4:18 am

    بسم الله الرحمن الرحيم
    تدوير المصفوفة المتناثرة ( Transposing a Sparse Matrix )


    بعد أن تعرفنا على المصفوفة المتناثرة ( مصفوفة الأصفار ) [ Sparse_Matrix ] نتعرف الآن على طريقة تدويرها ؛ ونعني بتدويرها: تبديل الصفوف بالأعمدة في السجل.
    بمعنى أن كل عنصر a[i][j] في المصفوفة المتناثرة سيؤول إلى العنصر b[j][i] في مصفوفة التدوير المقابلة لها. والشكل التالي يوضح التدوير للمصفوفة المتناثرة التي اعتمدناها في شرح الدرس السابق :
    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Sparce_Matrix3


    لنفكر قليلاً كيف يمكننا فعل ذلك بمصفوفة ذات بعد واحد ؟

    أول ما سنستنجد به هو ترتيب المصفوفة المتناثرة ؛ حيث أنها مرتبة ترتيباً تصاعدياً عن طريق الصفوف ..

    وهذا صحيح ولكن لنفكر للحظة كيف لنا استخدام هذا الترتيب التصاعدي في الصفوف كي نصل إلى ترتيب تصاعدي آخر ولكن عن طريق الأعمدة ؟


    لنرى معاً :

    لو قلنا أنه بما أننا فهرسنا مصفوفة الأصفار تصاعدياً باستخدام الصفوف ؛ فإننا سنستفيد من هذا الترتيب التصاعدي في عملية تدوير المصفوفة كما توضح الخوارزمية التالية :

    For each row i

    Take element < i , j , value > and store it as element < j , i , value > of the transpose ;



    لو جدنا في هذه الطريقة أن الترتيب سيبقى تصاعدياً ولكن من ناحية الأعمدة - حيث أننا في مصفوفة التدوير بدلنا الصفوف بالأعمدة - وبذلك لن نحصل على مصفوفة مرتبة ترتيباً تصاعدياً من ناحية الصفوف !؛ ولو طبقنا الخوارزمية السابقة على المثال الذي شرحنا عليه مصفوفة الأصفار ؛ فسنحصل على التالي :
    (0 , 0 , 15 ) ستصبح (0 , 0 , 15 )
    ( 0 , 3 , 22 ) ستصبح (3 , 0 , 22 )
    (0 , 5 , -15 ) ستصبح ( 5 , 0 , -15 )
    (4 , 0 , 91 ) ستصبح (0 , 4 , 91 )
    (5 , 2 , 28 ) ستصبح (2 , 5 , 28 )
    وهكذا


    النتيجة: مصفوفة مرتبة تصاعدياً من ناحية الأعمدة ، بينما نحتاج إلى مصفوفة التدوير مرتبة تصاعدياً من ناحية الصفوف كما ذكرنا ذلك !!

    الطريقة التي ستوصلنا إلى ترتيب تصاعدي جديد عن طريق الصفوف ، هي تثبيت العمود إبتداءاً من أصغر قيمة (صفر) والدوران حوله بجميع القيم الممكنة للصفوف (ابتداءاً من صفر إلى عدد الصفوف الكلي المخزن في a[0].row من مصفوفة الأصفار) ، وهكذا لكل عمود على حدة ..

    ربما تساعدك الخوارزمية التالية لمعرفة ديناميكية الحل :

    For all elements in column j

    Place element < i , j , value > in element < j , i , value > ;

    لعمل ذلك ، سنستخدم Tow For Loops & If statement ولا ننسى أن نستخدم عداد جديد "currentb مثلاً " للفهرسة ، كما توضح الشيفرة التالية:
    <div align=left><FONT face="Courier New" color=#008000>//-----
    avatar
    محمد عبده حنينة
    عضو جديد
    عضو جديد


    ذكر
    عدد الرسائل : 9
    العمر : 36
    البلد : اليمن
    القسم والمستوى : مستوى ثاني معلم حاسوب
    المزاج : كورة
    العضوية : 39
      : المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) 15781610
    السٌّمعَة : 0
    نقاط : 0
    تاريخ التسجيل : 21/12/2007

    بطاقة الشخصية
    تخصصي: حاسوب
    المحافظة: الحديدة

    المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) Empty رد: المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix )

    مُساهمة من طرف محمد عبده حنينة الأربعاء ديسمبر 26, 2007 9:02 pm

    شكرا للمشرفه شيماء المحويتي على الجهود الطيبه

      الوقت/التاريخ الآن هو الخميس مارس 28, 2024 8:36 am