خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة
نظراً لأهمية دائم مصفوفة في العديد من التطبيقات مثل التوافقيات و نظرية البيان و إيجاد المعاملات الواحدية في بيان موجه و حساب حلقات هاملتون في بيان و نظرية التلوين والإحصاء والاحتمالات وغيرها، دأب الباحثون بالبحث عن صيغ تحليلية لحساب القيمة الدقيقة لدائم مصفوفة إلا أن حساب هذه الصيغ صعب للغاية و ذلك...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Arabic |
| Published: |
Tishreen University
2018-12-01
|
| Series: | مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| Online Access: | http://journal.tishreen.edu.sy/index.php/bassnc/article/view/5044 |
| _version_ | 1797410264975409152 |
|---|---|
| author | أحمد الكردي |
| author_facet | أحمد الكردي |
| author_sort | أحمد الكردي |
| collection | DOAJ |
| description |
نظراً لأهمية دائم مصفوفة في العديد من التطبيقات مثل التوافقيات و نظرية البيان و إيجاد المعاملات الواحدية في بيان موجه و حساب حلقات هاملتون في بيان و نظرية التلوين والإحصاء والاحتمالات وغيرها، دأب الباحثون بالبحث عن صيغ تحليلية لحساب القيمة الدقيقة لدائم مصفوفة إلا أن حساب هذه الصيغ صعب للغاية و ذلك نظرا للكلفة الحسابية العالية لدى تطبيقها عند حساب دائم مصفوفة. و كما هو الحال في المحدد فإنه لا توجد طرائق فعالة لحساب دائم مصفوفة حتى وإن تركز تطبيق هذه الطرائق على مصفوفات (0,1) والتي تلعب دورا هاما جدا في نظرية البيان و الأشجار و لذلك لا تزال المسألة مفتوحة مما يجعلها مجالا هاما و أرضية خصبة للبحث. لهذه الأسباب، نصف في هذه المقالة، خوارزميتين جديدتين فعالتين لإيجاد دائم مصفوفة مربعة من المرتبة . تعتمد هاتان الخوارزميتان على البيان الموجه الموافق للمصفوفة . أخيرا، نبين من خلال بعض تجارب المحاكاة العددية فعالية كل من الخوارزميتين بلغة البرمجة C++ و نقارن النتائج الحاصلة بخوارزمية باكس و فرانكلين.
We describe in this paper two efficient algorithms for finding the permanent of a square matrix of order . These algorithms depend on the digraph corresponding to the matrix . Because of the importance of matrices permanents in several applications such as Combinatorics, Graph theory, Statistics and Probability, the researchers started to find closed and analytical forms for computing the permanent of matrix. But computing the permanent is a difficult problem. For these reasons, in this paper, we describe two efficient algorithms for finding the exact value of the permanent of a square matrix of order . These two algorithms depend on the digraph corresponding to the matrix . Finally, some numerical experiments are carried out on an Compatible PC with C++ codes to illustrate the efficiency of the proposed algorithms. The obtained results have been compared with those obtained by the algorithm proposed by Bax and Franklin.
|
| first_indexed | 2024-03-09T04:27:25Z |
| format | Article |
| id | doaj.art-043fcf57bbfa419e9c7fce6ee2e28206 |
| institution | Directory Open Access Journal |
| issn | 2079-3057 2663-4252 |
| language | Arabic |
| last_indexed | 2024-03-09T04:27:25Z |
| publishDate | 2018-12-01 |
| publisher | Tishreen University |
| record_format | Article |
| series | مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| spelling | doaj.art-043fcf57bbfa419e9c7fce6ee2e282062023-12-03T13:38:40ZaraTishreen Universityمجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية2079-30572663-42522018-12-01301خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهةأحمد الكردي نظراً لأهمية دائم مصفوفة في العديد من التطبيقات مثل التوافقيات و نظرية البيان و إيجاد المعاملات الواحدية في بيان موجه و حساب حلقات هاملتون في بيان و نظرية التلوين والإحصاء والاحتمالات وغيرها، دأب الباحثون بالبحث عن صيغ تحليلية لحساب القيمة الدقيقة لدائم مصفوفة إلا أن حساب هذه الصيغ صعب للغاية و ذلك نظرا للكلفة الحسابية العالية لدى تطبيقها عند حساب دائم مصفوفة. و كما هو الحال في المحدد فإنه لا توجد طرائق فعالة لحساب دائم مصفوفة حتى وإن تركز تطبيق هذه الطرائق على مصفوفات (0,1) والتي تلعب دورا هاما جدا في نظرية البيان و الأشجار و لذلك لا تزال المسألة مفتوحة مما يجعلها مجالا هاما و أرضية خصبة للبحث. لهذه الأسباب، نصف في هذه المقالة، خوارزميتين جديدتين فعالتين لإيجاد دائم مصفوفة مربعة من المرتبة . تعتمد هاتان الخوارزميتان على البيان الموجه الموافق للمصفوفة . أخيرا، نبين من خلال بعض تجارب المحاكاة العددية فعالية كل من الخوارزميتين بلغة البرمجة C++ و نقارن النتائج الحاصلة بخوارزمية باكس و فرانكلين. We describe in this paper two efficient algorithms for finding the permanent of a square matrix of order . These algorithms depend on the digraph corresponding to the matrix . Because of the importance of matrices permanents in several applications such as Combinatorics, Graph theory, Statistics and Probability, the researchers started to find closed and analytical forms for computing the permanent of matrix. But computing the permanent is a difficult problem. For these reasons, in this paper, we describe two efficient algorithms for finding the exact value of the permanent of a square matrix of order . These two algorithms depend on the digraph corresponding to the matrix . Finally, some numerical experiments are carried out on an Compatible PC with C++ codes to illustrate the efficiency of the proposed algorithms. The obtained results have been compared with those obtained by the algorithm proposed by Bax and Franklin. http://journal.tishreen.edu.sy/index.php/bassnc/article/view/5044 |
| spellingShingle | أحمد الكردي خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| title | خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة |
| title_full | خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة |
| title_fullStr | خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة |
| title_full_unstemmed | خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة |
| title_short | خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة |
| title_sort | خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة |
| url | http://journal.tishreen.edu.sy/index.php/bassnc/article/view/5044 |
| work_keys_str_mv | AT ạḥmdạlkrdy kẖwạrzmytạnfʿạltạnlḥsạbdạỷmmṣfwfẗbạstkẖdạmnẓryẗạlbyạnạtạlmwjhẗ |