• 0
ahmed.o.mohamed

هل يمكنك إيجاد جميع الإحتمالات !؟

سؤال

السلام عليكم

يبدو أن القسم نائم هذه الأيام, لذا بحثتُ البارحة في بقية الأقسام لعلي أجد سؤالا أو فكرة تستحق النقاش لأضعها هنا و بالتالي يستيقظ الأعضاء من هذا السبات العميق :D

فكرة السؤال الذي عثرتُ عليه جميلة جدا و هي إيجاد جميع الإحتمالات (و ليس عدد الإحتمالات) للأحرف و الأرقام الموجودة بين 000000000000 وحتى FFFFFFFFFFFF (الأحرف و الأرقام المُستخدمة هي تلك المُكونة لقاعدة الــ Hex).

لمعرفة التفاصيل : موضوع السؤال الأصلي.

تجدون في المشاركة الأخيرة مقدمة بسيطة للفكرة (إظهار جميع الإحتمالات الممكنة لــ ABCDEF, يوجد 46656 احتمال), و هذا الكود :

#include <stdio.h>#include <math.h>#include <stdlib.h>int main() {    int i, j, n = 6, p = 6;    char *Vect;    char **Liste;    FILE * File;    Vect = (char *) malloc(n * sizeof (char));    Vect = "ABCDEF";    Liste = (char **) malloc((int) pow((double) n, (double) p) * sizeof (char *));    for (i = 0; i < (int) pow((double) n, (double) p); i++) {        Liste[i] = (char *) malloc(p * sizeof (char));    }    File = fopen("RandomFile.txt", "w");    for (i = 0; i < (int) pow((double) n, (double) p); i++) {        for (j = 0; j < p; j++) {            Liste[i][j] = Vect[(i / (int) pow((double) n, (double) (p - (j + 1)))) % n];            fprintf(File, "%c", Liste[i][j]);        }        fprintf(File, "%s", "\n");    }    free(Vect);    for (i = 0; i < (int) pow(n, p); i++) {        free(Liste[i]);    }    free(Liste);    return 0;}

سأضع حل السؤال بعد الإنتهاء من نقاش الفكرة إن شاء الله.

بانتظار إبداعاتكم.

تم تعديل بواسطه مصطفى 36a2
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

70 إجابة على هذا السؤال .

  • 0

إذاً فلنبدأ ..

أشكرك على متابعة الموضوع أخي الفاضل :)

بانتظار آراء بقية الإخوة.

the inventor [email protected]

نعم, الخوارزمية لكلاسيكية للتباديل تنص على الآتي (و هي التي استخدمها الأخ مومو في محاولاته):

في كل مرة يتم تثبيت أحد أحرف الكلمة ثم يتم إظهار جميع الإحتمالات المُرافقة لذلك الحرف.

انظر المثال : الحرف ذو اللون الأزرق يُمثل بداية الإحتمال و الأحرف ذات اللون الأحمر تُمثل الإحتمالات المُرافقة له :

ABC, ACB

BCA, BAC

CBA, CAB

في المرة الأولى قمنا بتثبيت A و إظهار B و C ثم C و B و هي الإحتمالات المُرافقة لــ A ثم كررنا نفس العملية مع B و C.

يعني في المتال السابق لدينا عدد مرات التبادل هو 6 لان 2*3=6

و هنا تكمن إحدى أبرز مشاكل خوارزمية التبديل ..!

لأن الــ complexity factorial يحتاج إلى وقت لا نهائي للتنفيذ عند معالجة بيانات كبيرة (770 سنة من أجل n=20 !!) :

post-219439-064985300 1345248237_thumb.p

و بالتالي فإن الوقت المُستغرق للخوارزمية سيكون كارثيا بغض النظر عن التحسينات التي قد تطرأ عليها (ما لم يتغير التعقيد الزمني).

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

و هنا تكمن إحدى أبرز مشاكل خوارزمية التبديل ..!

لأن الــ complexity factorial يحتاج إلى وقت لا نهائي للتنفيذ عند معالجة بيانات كبيرة (770 سنة من أجل n=20 !!) :

post-219439-064985300 1345248237_thumb.p

عوضا عن ذلك انتظر الي 2025 الموعد المحدد (بمتوسط التوقعات الاحصائية) بولادة الحواسيب الكمية ( هنا التفاصيل عنها )والتي ستجعل من 770 اقل من 0.000770 ثانية

تم تعديل بواسطه أحمد الشنقيطي
إصلاح الرابط.
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
لأن الــ complexity factorial يحتاج إلى وقت لا نهائي للتنفيذ عند معالجة بيانات كبيرة (770 سنة من أجل n=20 !!) :

يعني أن ليس هناك حل لدلك الا ادا كان الحاسوب سريع جدا جدا

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

عوضا عن ذلك انتظر الي 2025 الموعد المحدد بولادة الحواسيب الكمية والتي ستجعل من 770 اقل من 0.000770 ثانية

هل لهذا علاقة بالــ Quantum Algorithm, مثل Shor's algorithm, Grover's algorithm and Deutsch–Jozsa algorithm ؟

يعني أن ليس هناك حل لدلك الا ادا كان الحاسوب سريع جدا جدا

الأصل أن العمليات المعقدة (تحتاج إلى سنوات للتنفيذ) يتم إجراءها على حواسيب فائقة السرعة (Supercomputer)

مثل الحاسوب الصيني الضخم Tianhe-1A (بالصينية 天河一号. بالعربية درب التبانة _ مجرتنا _), هذا الحاسب قادر نظرياً على اجراء كوادريليون حساب في الثانية (1 پـِتافلوپ) !!!

و هو من إنتاج مركز الحاسوب الفائق الوطني و تحت رعاية الجامعة الوطنية لتكنولوجيا الدفاع, يعمل على نظام تشغيل ليونكس و تبلغ ذاكرته 98304 GB و تصل سرعته إلى 1.206 پـِتافلوپس و يُستخدم في استكشاف النفط ومحاكاة الطائرات و قد وصلت تكلفته إلى 88.24 مليون دولار (من قال أنه توجد أزمة مالية ؟ :D)

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

هل لهذا علاقة بالــ Quantum Algorithm, مثل Shor's algorithm, Grover's algorithm and Deutsch–Jozsa algorithm ؟

نعم يتم تطبيق الخوارزميات الكمومية فى هذا النوع من الحواسيب الكمومية وهي تختلف مطلقا عن Classic Algorithms

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

للطرق التقليدية التي تم عرضها في الموضوع، يمكن تسريع الحصول على النتائج باستخدام تعليمات أسمبلي بدلاً من أوامر C/C++

ومثلاً كتابة برنامج مركزي يقوم بتوزيع المهام على برامج فرعية قد تكون موزعة على حواسب مختلفة، بالتالي يكون لديك distributed computing.

BOINC أحد الأمثلة على ذلك، وهو مستخدم في حساب checksums في مشروع freerainbowtables.com

إضافة: تنفيذ البرنامج كتطبيق x64 مهم جداً لتخفيض الوقت، فأحجام المسجّلات التي سيتم استخدامها في التعليمات سيتضاعف وبالتالي سيكون هناك قدرة على اختصار عدد التعليمات المطلوب تنفيذها.

تم تعديل بواسطه Xacker
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

يمكن تسريع الحصول على النتائج باستخدام تعليمات أسمبلي بدلاً من أوامر C/C++

هل تعتقد أن إدراج أوامر أسمبلي في كود C/C++ (باستخدام asm مثلا) سيزيد من سرعة البرنامج ؟

مثال ؟

مثلاً كتابة برنامج مركزي يقوم بتوزيع المهام على برامج فرعية قد تكون موزعة على حواسب مختلفة، بالتالي يكون لديك distributed computing.

لو كنا نعمل على حاسب يمتلك عدة معالجات سريعة فأظن أن استخدام أكثر من (Computing Element (CE عن طريق البرمجة المتوازية (parallel programming) سيكون مفيدا أيضا.

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم

باستخدام خوارزمية جديدة و بالاستعانة بالدالة write الموجودة في المكتبة unistd.h يُمكننا عرض جميع الإحتمالات المطلوبة في وقت وجيز شيئا ما (الملف التنفيذي في المرفقات باسم NumberOfPermutation_1) :

#include <stdio.h>
#include <unistd.h>
#define NB 12
char base[] = "ABCDEF0123456789";

void fonction(char tab[NB + 1], int rank) {
int i;
if (rank <= NB) {
for (i = 0; base[i] != '\0'; i++) {
tab[rank] = base[i];
fonction(tab, rank + 1);
}
for (i = 0; i < NB; i++)
write(1, &tab[i], 1);
write(1, "\n", 1);
}
}

int main() {
char tab[NB + 1];
int i;
for (i = 0; i < NB; i++)
tab[i] = base[0];
fonction(tab, 0);
return (0);
}

لكن بإلغاء التكرار و تطوير الخوارزمية السابقة, سيكون البرنامج أسرع بكثير (الملف التنفيذي في المرفقات باسم NumberOfPermutation_2) :

#include <stdio.h>
#define echanger(a, b) do {int temp=(a); (a)=(b); (b)=temp;} while (0)

char *suivant(char *p, int n) {
int i, j = n - 1, k = n - 1;
while (k > 0 && p[k - 1] > p[k])
k--;
if (k != 0) {
while (p[j] < p[k - 1])
j--;
echanger(p[k - 1], p[j]);
for (i = k, j = n - 1; i < j; i++, j--)
echanger(p[i], p[j]);
}
return k == 0 ? 0 : p;
}

int main() {
char mot[] = "ABCDEF";
size_t nb_lettres = (sizeof mot / sizeof *mot) - 1;
do
printf("%s\n", mot); while ((suivant(mot, nb_lettres)) != 0);
return 0;
}

يُمكننا تطوير الخوارزمية السابقة لتصبح أسرع و أقل تكلفة (راجع Knuth, tome 3), الملف التنفيذي في المرفقات باسم NumberOfPermutation_3 :

#include <stdio.h>
#define echanger(a, b) do {int temp=(a); (a)=(b); (b)=temp;} while (0)

void perm(char *t, int n, int k) {
int i;
if (k == n - 1)
printf("%s\n", t);
else
for (i = k; i < n; i++) {
echanger(t[k], t[i]);
perm(t, n, k + 1);
echanger(t[i], t[k]);
}
}

int main() {
char t[] = "ABCDEF";
perm(t, sizeof t / sizeof *t - 1, 0);
return 0;
}

توجد مقالة رائعة جدا للدكتور James McCaffrey بعنوان Série de tests: Permutations de chaînes, يمكنك الإطلاع عليها من خلال الرابط التالي:

فكرة جيدة, أعتقد أن الكود سيكون أسرع هكذا :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void faire_combi(char * str, char * tmp, int len, int ind) {
int i;
if (ind >= len) {
puts(tmp);
return;
}
for (i = 0; i < len; i++) {
if (str[i] > 0) {
char pt = str[i];
str[i] = -1;
tmp[ind] = pt;
faire_combi(str, tmp, len, ind + 1);
str[i] = pt;
}
}
}

void combinaisons(char * str) {
int len = strlen(str);
char * tmp = (char*) malloc(len + 1);
tmp[len] = '\0';
faire_combi(str, tmp, len, 0);
free(tmp);
}

int main() {
char str[] = "ABCDEF";
combinaisons(str);
return 0;
}

[email protected]

خذ إحدى الخوارزميات الثلاثة السابقة, ستكفيك.

أخيرا, ما رأيكم في تحويل الموضوع إلى نقاش فى بعض خوارزميات التبديل المتقدمة مثل خوارزمية Kenneth Rosen أو Addison-Wesley.

NumberOfPermutation_1.rar

NumberOfPermutation_2.rar

NumberOfPermutation_3.rar

تمام اخي احمد ولكن البرامج لا تحفظ العمل ولا يوجد زر للتوقف

تم تعديل بواسطه أحمد الشنقيطي
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

هل تعتقد أن إدراج أوامر أسمبلي في كود C/C++ (باستخدام asm مثلا) سيزيد من سرعة البرنامج ؟

مثال ؟

هذا سطر من أحد برامجك السابقة، وفيه التمثيل بالأسمبلي بالنتيجة


;for (i = k; i < n; i++) {
00F913F9 mov eax,dword ptr [k] ; 1 clk
00F913FC mov dword ptr [i],eax ; 1 clk
00F913FF jmp perm+5Ah (0F9140Ah) ; 1 clk
00F91401 mov eax,dword ptr [i] ; 1 clk
00F91404 add eax,1 ; 1 clk
00F91407 mov dword ptr [i],eax ; 1 clk
00F9140A mov eax,dword ptr [i] ; 1 clk
00F9140D cmp eax,dword ptr [n] ; 2 clk
00F91410 jge perm+0D1h (0F91481h) ; 1 clk
; do something
jmp 00F913F9 ; 1 clk
00F91481 ...
--------------------------------------------------------
; 11 clk

بينما في الأسمبلي فأنت تتعامل على مستوى مجرد أكثر

مثلاً أنا وجدت أني لا أحتاج للاحتفاظ بقيمة المتغير i

فلماذا أحجز له dword في الذاكرة وفي كل مرة أقرأ وأكتب القيمة فيها؟ ببساطة أستخدم المسجل eax بدلاً عن حجز مكان في الذاكرة وعندما أنتهي منه فلا تهمني القيمة فيه.

أيضاً n و k لا أحتاج لتمريرها كقيم في الذاكرة وإنما أمرر القيم في المسجلات، وأوفر أيضاً 1 clock.


;for (i = k; i < n; i++) {
mov eax, dword ptr [k] ; 1 clk
jmp @F ; 1 clk
_loop: inc eax ; 1 clk
@@: cmp eax, dword ptr [n] ; 2 clk
jge _end ; 1 clk
; do something
jmp _loop ; 1 clk
_end
--------------------------------------------------------
; 7 clk


; ESI = n, passed to func
; EDI = k, passed to func
;for (i = k; i < n; i++) {
mov eax, edi
jmp @F
_loop: inc eax
@@: cmp eax, esi ; 1 clk
jge _end
; do something
jmp _loop
_end
--------------------------------------------------------
; 6 clk


echanger(t[k], t[i]);
01021412 8B 45 08 mov eax,dword ptr [t]
01021415 03 45 10 add eax,dword ptr [k]
01021418 0F BE 08 movsx ecx,byte ptr [eax]
0102141B 89 4D EC mov dword ptr [temp],ecx
0102141E 8B 45 08 mov eax,dword ptr [t]
01021421 03 45 10 add eax,dword ptr [k]
01021424 8B 4D 08 mov ecx,dword ptr [t]
01021427 03 4D F8 add ecx,dword ptr [i]
0102142A 8A 11 mov dl,byte ptr [ecx]
0102142C 88 10 mov byte ptr [eax],dl
0102142E 8B 45 08 mov eax,dword ptr [t]
01021431 03 45 F8 add eax,dword ptr [i]
01021434 8A 4D EC mov cl,byte ptr [temp]
01021437 88 08 mov byte ptr [eax],cl
01021439 33 C0 xor eax,eax
0102143B 75 D5 jne perm+62h (1021412h)


; edi = k
mov esi, eax ; esi = i
mov ebx, dword ptr [t] ; ebx = t
mov al, byte ptr [ebx+edi]
mov ah, byte ptr [ebx+esi]
mov byte ptr [ebx+esi], al
mov byte ptr [ebx+edi], ah

قس على ذلك على باقي أجزاء البرنامج، وبما أن البرنامج سيقوم بتنفيذ عملية طويلة جداً فالفرق الزمني المختصر سيكون كبير أيضاً.

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

تمام اخي احمد ولكن البرامج لا تحفظ العمل ولا يوجد زر للتوقف

البرنامج يعرض الإحتمالات الممكنة على الشاشة فقط, يُمكنك استبدال printf بــ fprintf لحفظ المعلومات في ملف نصي كما فعلتُ سابقا.

بالنسبة لزر التوقف, فالكود مكتوب في بيئة الــ Console لذا لن تجد أزراراً أو ما شابه, لكن يُمكنك كتابة الكود في بيئة الــ GUI إن أردت, فالخوارزميات جاهزة لديك ! :)

بما أن البرنامج سيقوم بتنفيذ عملية طويلة جداً فالفرق الزمني المختصر سيكون كبير أيضاً.

هذا ما كنت أتوقعه, حتى لو أدرجنا بعض أوامر الأسمبلي في كود C/C++ فعقبة السرعة ستظل موجودة ..

لكن أعتقد أن تنفيذ كود الأسمبلي على جهاز يملك عدة معالجات "سريعة" سيُحدث فرقا زمنيا ملحوظا.

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

هذا ما كنت أتوقعه, حتى لو أدرجنا بعض أوامر الأسمبلي في كود C/C++ فعقبة السرعة ستظل موجودة ..

طبيعي، ولكن بالنهاية السرعة التي ستحصل عليها من تنفيذ كود C/C++ ستكون أقل بضعفين أو أكثر من السرعة التي ستحصل عليها من التنفيذ بأوامر أسمبلي.

وهذا الفرق ليس بقليل.

لكن أعتقد أن تنفيذ كود الأسمبلي على جهاز يملك عدة معالجات "سريعة" سيُحدث فرقا زمنيا ملحوظا.

الأسمبلي قادرة على إحداث فرق ملحوظ في السرعة بكافة الظروف :lol: أنت بكلامك هذا لا تعطيها قدرها!

An old joke goes something like this:"There are three reasons for using assembly language: speed, speed, and more speed."

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

لنحسب عدد الاحتمالات ببساطة:

|solution space| = 16^12 = 281474976710656

for each solution, we have 12 digits.

Lets assume that each digit is represented with one byte only for simplicity.

solution space size = 281474976710656 * 12 Bytes

= 3377699720527872 Bytes

= 3298534883328 KiB

= 3221225472 MiB

= 3145728 GiB

أود أن أرى من لديه ثلاثة ملايين GiB لتخزين كل الاحتمالات :sad:

إن كان المطلوب هو إنتاج عينات عشوائية من هذا المجال, فالموضوع يتم ببساطة عن طريق uniform distributed random number في الحالة البسيطة إن كانت جميع الاحتمالات متساوية في الأهمية. أما محاولة إنتاجها و تخزين كل الاحتمالات, فهو أمر غير ممكن على الأقل بالتكنلوجيا المتوفرة.

تم تعديل بواسطه Khaled.Alshaya
4

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

إذا, لا يمكن رؤية جميع الإحتمالات إلا في الحواسيب الفائقة (Supercomputer) ؟

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أو أن يكون لديك ~3000 مستخدم كل واحد يستخدم 1 تيرا بايت على الأقل لتخزين جزء من النتائج.

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

إذا, أنصح الأخ hassan9599 بالتخلي عن الفكرة إلى حين شراء حاسوب فائق .. أو امتلاك أكثر من 3000 مستخدم كل واحد يستخدم 1 تيرا بايت !! :wacko:

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

انا احتاج هذة الاحتمالات لكسر شفرات القنوات والشفرات تعتمد علي خوارزمية

يعني الشفرة مستحيل تبقي زي كدة 000000000000 او 000000000100

ممكن تبقي زي كدة 6DE5729A3850

فأنا احتاج برنامج يصنع الاحتمالات الخوارزمية بهذة الشكل 6DE5729A3850

وليس بهذا الشكل 000000000000 او 000000000100

تم تعديل بواسطه hassan9599
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
اين البرنامج يا اخوان

هذا مثال باستخدام Cpp11, فقط قم بتغيير numbers_count لتنتج العدد الذي تريده من الأعداد العشوائية. استخدمت g++ 7.1 لترجمة البرنامج:

#include <cstdint>
#include <cstddef>
#include <fstream>
#include <iomanip>
#include <random>

int main(){
// specify the min/max range of the vouchers we want to generate
const std::uint64_t min = 0x0ul, max = 0xfffffffffffful;
// specify how many vouchers we want to generate, and the width
// of the vouchers when represented in text
const std::size_t numbers_count = 1000000, field_width = 12;
std::random_device seed;
std::mt19937_64 engine(seed());
std::uniform_int_distribution<std::uint64_t> range(min, max);
auto rnd = [&](){ return range(engine); };
std::ofstream output("output.txt");
output << std::hex << std::setfill('0');
for(std::size_t i = 0; i < numbers_count; ++i)
output << std::setw(field_width) << rnd() << '\n';
}

تم تعديل بواسطه Khaled.Alshaya
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

انا احتاج هذة الاحتمالات لكسر شفرات القنوات والشفرات تعتمد علي خوارزمية

يعني الشفرة مستحيل تبقي زي كدة 000000000000 او 000000000100

ممكن تبقي زي كدة 6DE5729A3850

فأنا احتاج برنامج يصنع الاحتمالات الخوارزمية بهذة الشكل 6DE5729A3850

وليس بهذا الشكل 000000000000 او 000000000100

الأفضل أن تُحاول كسر الخوارزمية لتختصر عليك الطريق و إلا فسيلزمك تجربة أكثر من Belliard احتمال ..! و قد يستغرق هذا منك عدة أشهر إن لم تكن سنوات.

بالنسبة للكسر فأعتقد أنه يُخالف قوانين المنتدى.

هذا مثال باستخدام Cpp11, فقط قم بتغيير numbers_count لتنتج العدد الذي تريده من الأعداد العشوائية. استخدمت g++ 7.1 لترجمة البرنامج

جميل جدا أخي خالد, ممكن ترفق لنا الملف التنفيذي لأنني أملك النسخة 3.4 من g++.

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

طيب هل يمكن احد يصنع لي ملف تكست يحتوي علي عدد كبير من الارقام والحروف معا وليس ارقام فقط او حروف فقط

تم تعديل بواسطه hassan9599
-1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أخي حسان, لا تجعل السؤال طريقك للتعلم !

الموضوع يحتوي على العديد من الخوارزميات التي يمكنها حل مشكلتك, اختر واحدة منها و أضف إليها بعض التعديلات حتى تُناسب رغباتك.

يُغلق الموضوع.

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
زوار
This topic is now closed to further replies.

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .