CSC-SY

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

لمن قام بحل أسئلة الدورات لدي الاستفسارات التالية:

1. دورة 2006 - 2007 : سؤال التقطيع الطلب b : اذا قمنا باختيار اسم الطالب هو المفتاح (key) لكونه وحيد هل هذا صحيح ؟ عدد عناصر جدول التقطيع المتوقع كم هو, هل نتوقع لدينا 14 محافظة من كل منها لدينا 10 طلاب بالتالي أقل عدد متوقع هو 140 (دون تكرار بمالرتبة اي طالبين بالمرتبة الاولى مثلاً)
2. الطلب c في نفس الدورة: المطلوب مسح الجدول بأكمله لأن الجدول مدخل على اساس اسم الطالب و بالتالي لا نستطيع تحديد ترتيب الطالب فوراً لأن كما ذكرت المفتاح هو اسم الطالب و بالتالي سوف نمسح الجدول كله ثم نظهر الأسماء مرتبة أبجدياً هل هذا صحيح ؟
3. دورة 2005 - 2006 أيضاً سؤال التقطيع : ما المقصود بعمليات النقل التي يمكن أن تولدها عملية الحذف؟
   شكراً لكم.

شباب كمان سؤال من بعد اذنكم بدورة 2004 الفصل الأول
التقطيع و حل التصادم بالتقطيع المتحالف Coalition Hashing شو رأيكم بهاد الحل :

Procedure Search ( T : HashTable; k : key ) : Integer;
j←h(k) // h the hash function 
	if ( T[j] = key )
		Return j
	Else if ( T[j] is empty )
		Return -1
	Else
		P ← T[j].link
		While ( P ≠ NIL ) and ( not Found ) 
			If ( P.tab = key ) 
				Found ← True   Return P.Index
			Else
				P ← P.link
		If ( not Found ) 
			Return -1

Procedure Delete ( Var T : HashTable ; k : key )
	J ← Search(T,k)
	If ( j ≠ -1 )
		If ( T[j].link = NIL )
			Free ( T[j])
		Else 
			L ← True
			Change_Positions ( T,T[j].link,E,L)     // E Empty Element “Type of the hash table slots elements”

Procedure Change_Positions ( Var T : HashTable; P : Pointer; Var E : Element; Var Last1 : Boolean)
	If ( P.link ≠ NIL ) 
		Change_Positions ( T,P.link,E,Last1)
	Tmp ← P.Tab
	P.Tab ← E
	E   ← Tmp
	If ( Last1 ) 
		P.link ← NIL
		Last1 ← False

وعليكم السلام...
بمناسبة أنو عنا فحص خوارزميات 2، وبمناسبة أنو داخل معنا بحث الملفات والفهرسة بالفحص، وبمناسبة أنو صعب وحالتو حاله ومالنا حالين عليه إلا كم مثال ، ساويت ملف صغير بيحوي مراجعة للملفات، معلومات قليلة صالحة للمراجعة وليس للدراسة لأول مرة، طبعاً المعلومات من الكتاب واستعنت شوي بآخر محاضرة نظري، تفضلوا هي الملف:

Microsoft Word - Files organizing.pdf

ياريت إذا حدا عندو أي ملاحظة على الملف يكتبها مشان الكل يستفيد.
مع العلم "مشان ما تتفاجأوا لاحقاً" في شغلة بالملف مكتوبة مرتين، كل مرة بشكل، وذلك لسبب بسيط أني لقيتها بالكتاب شي، وبالمحاضرة شي، وهي أنو التسجيلة بتحتوي على خانة used , delete bit من ضمن حقول التسجيلة، بينما لقيتها بالمحاضرة أنو الكتل مقسمة لغرف وبالغرفة في خانة used , delete bit .. فإذا حدا عندو معلومة عن هالشغلة هي ياريت يذكرها.

السلام عليكم ...وين حل الدورات يلي كاتبينو ياريت تحملوهم
وشكراً

نور سبقتيني الله يعطيكي العافية, كنت بدي حط:
-----
كتابي الجديد: ماذا أستعمل من بنى المعطيات؟ ومتى أستعملها؟
كتاب يشرح الفروق بين بنى المعطيات ويصنفها ويقارن بينها, ويوضح تعقيد خوارزمياتها.
كما أنه يصنف طرق الفرز بناء ً على تعقيدها.
يشرح أفكار تفيد في اتخاذك للقرار المناسب لبنية المعطيات المناسبة, كما أنه يعطيك لمحة بسيطة عن خوارزميات التخزين الثانوي والفروق بينها.
الكتاب موجود هنا.
ادعولنا أمانة ...

My mobile was stolen, if you gave me your number after 1/4/2008 send it to me again

الى الأمام .... و بالتوفيق انشاء الله

 اطلعت على محتواياته بشكل سريع .. ... فينا نسميه كُتيب مو كتاب .. مو هيك ؟

أخي نحنا منقول كتاب منشان العالم تقول: "ياي كتاب ببلاش ", بعدين بس نكبر منعدل الردود ومنساويها كتيب
شكرا ً عاهتمامك أنوس.

My mobile was stolen, if you gave me your number after 1/4/2008 send it to me again

بالنسبة لسؤال الأول
بعتفقد إنو لو حطيت ال Key هو رقم الطالب بيكون أحسن حتى لو صار هيك في عشر تصادمات لأنو تابع التقطيع هوو رح يحل المشكلة
بس المشكلة هي بنابع التقطيع شلون بدك تختارو يعني حتى لو كان ال Key هوو اسم الطالب (يعني بدك تساويي بحيث يغطي ال 140 خانة بالجدول.
2- هلق إذا حططيت ال Key هو رقم الطالب رح تنحل المشكلة
بس أنا حاسس إنو بدون من السؤال إنو ما ننقل الأسماء لجدول تاني ونرتبهون بعدين (لازم نطلعهون ضغري مرتبين) .
3- متل ما قلي Venus88 إنو الأصل بعملية الحذف لازم وقت نحذف ما نحط "Deleted" وإنما لازم نرجع جميع العناصر بسلسلة الإراحة مرتية (في السلسلة).

وشكرا Ray , mpcabd

Procedure Delete ( Var T : HashTable ; k : key )
	J ← Search(T,k)
	If ( j ≠ -1 )
		If ( T[j].link = NIL )
			Free ( T[j])
		Else 
			L ← True
			Change_Positions ( T,T[j].link,E,L)     // E Empty Element “Type of the hash table slots elements”

Procedure Change_Positions ( Var T : HashTable; P : Pointer; Var E : Element; Var Last1 : Boolean)
	If ( P.link ≠ NIL ) 
		Change_Positions ( T,P.link,E,Last1)
	Tmp ← P.Tab
	P.Tab ← E
	E   ← Tmp
	If ( Last1 ) 
		P.link ← NIL
		Last1 ← False

Procedure Change_Positions ( Var T : HashTable; P : Pointer; Var E : Element; Var Last1 : Boolean) 
.
.
	If ( Last1 ) 
		P ← NIL
		Last1 ← False

وأيضا يجب إعطاء E قيمة بدائية (مثلا -1 ).
وإن شاء الله يكون كلامي صح.

سؤال لو سمحتو
الفصلين التامن والتاسع (الفهارس ) عطتون الدكتورة

سؤال من بعذ إذنكون
خوارزميات البحث داخلة ولا لاء ؟

السؤال الذي يطرح نفسه بقوة, شو داخل بشكل عام, يعني بدنا حدا يكون حضران لنعرف شو عطت الدكتورة.

My mobile was stolen, if you gave me your number after 1/4/2008 send it to me again

يا ريت من يللي كان يحضر يقلنا سو داخل من الملفات والفهارس...
ومن وين درستوها.....؟؟؟؟
حاكم ما عندي كتاب....

أصدك ترتيب الطالب!!!!
اذا هيك قصدك بتوقع ما بصير ناخد ال Key تبع المعطيات ترتيب الطالب لأن يجب أن يكون الKey وحيد "Unique" إلى حد ما.

شكراً Obaeda

السؤال الأول دورة 1/7/2008 هذا حلي ما رأيكم ؟؟

For each vertex i in G do
	R ← 0
	DFS ( G,i,R)
	If R = |v| - 1 then
		Print “ Vertex i is a root”
Procedure DFS ( G : Graph , w : Vertex , Var r : integer)
	w.visited ← True
	For each vertex v adjacent to w do
		If ( v.visited = False ) then
			v.visited ← True
			r ← r + 1
			DFS ( G,v,r)

حتى تكون شجرة يجب أن يتحقق مايلي:

 لكل عقدة v يكون Out-degree ≤ 2

لكل عقدة v يكون In-degree = 1 عدا الجذر يجب أن يكون In-degree = 0

الآن نقوم بكتابة إجرائية ال BFS باستخدام الألوان لتحديد فيما اذا كانت العقدة قد تم زيارتها مسبقاً ام لا أو تم زيارة مجاورتها أم لا و تفصيل الألوان كالتالي وهي طريقة كتاب Introduction to Algorithms:

White = العقدة لم تزر بعد

Gray = العقدة مزارة لكن مجاورتها لم يزارو

Black = العقدة مزارة و كذلك جميع مجاوراتها

الآن اذا وجدنا عند زيارة عقدة ما أن أحد مجاورتها لونها Gray إذاً البيان ليس شجرة لأن هذا يعني أنه قد تم الوصول إلى هذه العقدة من عقدة أخرى أي أن هذه العقدة لها أبوين

نخزن عند كل عقدة ال Out-degree وال In-degree ثم نتحقق منهم سوف اكتب الخوارزمية بشكل عام دون الخوض بالتفاصيل أرجو التأكد منها

أولاً يجب تحديد الجذر ويتم ذلك على ما اعتقد كما يلي

For each vertex i in G  do
	BFS ( G,i,r)
	If r = |v| - 1 then
		Print “ It’s a tree and the root is i.”
		Break
Procedure BFS ( G: Graph, s: Vertex, r: integer)
	For each vertex v in G do
		v.color ← white
		v.in-degree ← 0
		v.out-degree ←  0
	s.color ← Gray
	Enqueue (Q,s)
	While ( Q ≠ Ø ) do
		x ← dequeue (Q)
		for each vertex v adjacent to x do 
			r ← r +1
			x.out-degree ++
			if ( v.color = white ) then
				v.in-degree ++
				v.color ← Gray
				Enqueue ( Q,v)
			Else if ( v.color = Gray ) then
				Return “It’s not a tree”
		x.color ← Black

I came across an interesting problem in “Introduction to Algorithms” not very hard, but cool :)

Attendees of a faculty party shake hands to greet each other, and each professor remembers how many times he or she shook hands. At the end of the party, the department head adds up the number of times that each professor shook hands. Show that the result is even by proving the handshaking lemma: if G = (V, E) is an undirected graph, then

كتب happy:

كتب Hadhood:

كتب hanihh:

يا ريت من يللي كان يحضر يقلنا سو داخل من الملفات والفهارس... ومن وين درستوها.....؟؟؟؟ حاكم ما عندي كتاب....

هلأ أنا ماكنت احضر بس اسمعت انو الدكتورة قالت انو ملفات الباير مو داخلة واللي قبل داخلين كلون بس اذا في حدا متأكد ياريت يخبرنا

و أنا هيك سمعت ؟!؟!؟!؟! كمان بس اذا في حدا متأكد ياريت يخبرنا .....

ههههههههههههههههههه ما الإشاعة طالعة من عندي

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

وينك هبة مو هيك صار الحكي؟؟

هلأ في شغلة اسمها cluster كاتبة عندي أنها محذوفة، بس المشكلة أني ما لقيتها بالكتاب ، حدا بيعرف شو هي الcluster؟؟
أنا بتصور توع من الفهرسة...
بآخر محاضرة حليت الدكتورة سؤال دورة، وأجت سيرة الفهرس الأجوف، والكثيف فيها..وكمان أجت سيرة ISAM!

كتب Ray:

هلأ في شغلة اسمها cluster كاتبة عندي أنها محذوفة، بس المشكلة أني ما لقيتها بالكتاب ، حدا بيعرف شو هي الcluster؟؟ أنا بتصور توع من الفهرسة... بآخر محاضرة

انا بتذكر مرت معي Clusters بالHash tables بالتحديد بال Linear probing إنو

"Linear probing is easy to implement, but it suffers from a problem known as primary clustering"

والمقصود بال Clusters التجمعات.

السلام عليكم ..أنا حامل المادة يعني هلق شو داخل بالملفات الفهارس كلها سمعت من الأنسة Rasha أنو موداخلة ملفات باير يعني أكيد بس ملف كومة والفهرس الكثيف والفهرس الأجوف يلي هو نفس اسم ISAM وملفات التقطيع والله يا أنسة RAY ما ني سمعان بهيك شي ياريت يلي حضران معها تبعات حل مسائل الملفات ينزلنا ياهن الله يوفقكم وشو بتقصد الأنسة Rasha كأنو الدكتورة مركزة على BAYER وشو بتقصدي بالبحث ياريت يلي حضر وضح أكتر ...وشكرا لكم جميعاً

هلأ الشي اللي خلاني ظن أنو هو تابع للفهارس أنو انذكر بآخر محاضرة، مع أني دورت عليه بالكتاب، بس ما لقيته!
Murhaf هي مارة معك بالHashing تبع الفهارس، أو جداول التقطيع العادية؟؟؟

ليكني هون ..
مبلى .. هيك تماما .. يعني نحنا متأكدين .. لا إشاعة ولا شي

السلام عليكم ....شايف ماحدا رد طيب شو ممكن تركز على أشجار باير ولي بس مو الاجرائيات تبعها ومنفهم من الأنسة Hiba مو داخلة ملفات باير اريح على حالتين كلو ما بيعرف يحلو بس شو بقصد البحث يلي قبل أشجار باير أنو مهم ...ولاتواخذونا ....

أنا ماقلت إنو أشجار الباير مهم أنا قلت إنو الدكتورة قالت "خلص مو مشكلة ملفات الباير بس لاتنسوا أشجار الباير"

بس قصدي بكلمة البحث أي"الفصل"الذي يسبق ملفات الباير هاد لازم ندرسه.....

_____________________________________________________
علما إنو هاد كلام الدكتورة "بس مادخلني إذا جابت شي!"

بال Hash tables

سؤال:

في بالدورات تبع 2005-2006 سؤال تبع نقول عن عقدة أنها بؤرة, كأنو السؤال كتير سهل اذا حدا شافو ممكن يشرحلنا شو المطلوب لأن حسب ما فهمت حسيت السؤال مالو طعمة
حلقة For و كم If بيطلع خالص حاسس حالي مالي فهمان السؤال