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

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

اسلاید 1: 1Data Structure (40-254)در اين درس مباني ساختمان داده ها و الگوريتم ها تدریس میشود.

اسلاید 2: 2مطالبي كه دانشجو بايد از قبل بداندساختمان گسسته (بعنوان درس پيش نياز)آشنائي با يكي از زبانهاي برنامه نويسي مانندCC++JavaPascalدر اين درس سعي ميشود الگوريتم ها مستقل از زبان برنامه نويسي ارائه گردد.

اسلاید 3: 3مراجعIntroduction to Algorithms, T.Cormen, V.Leiserson, R.Riverst & C.Stein (CLRS) MIT Press, Sept. 2001,

اسلاید 4: 4مراجعFoundation of Computer Science,A.V.Aho, D.Ullman, W.H.Freeman & Company, 1992, مباني علم كامپيوتر - جلد اول – ترجمه منصور جم زاد انتشارات دانشگاه صنعتي شريف - 1381

اسلاید 5: 5مراجع

اسلاید 6: 6ريز مواد درسمعرفي درس - سطوح تجريد (انتزاع) - مراحل مختلف حل مسئله و انتزاع - داده مدل ها (Data Models)،‌ داده گونه ها (Data Types)،‌ داده ساختار ها (Data Structures) ، داده گونه هاي انتزاعي (ADT)، شئي (Object)روش هاي تحليل الگوريتم ها - تابع رشد ، شمارش مراحل ، رابطه هاي بازگشتي و روش هاي حل آنها (حدس و استقرا) ، رابطه هاي همگن

اسلاید 7: 7ريز مواد درس 3. داده ساختار هاي ليست - تعاريف اوليه ، عمليات بر روي ليست - داده ساختار ها براي ليست ، كار با اشاره گر هاي واقعي - انواع ليست ها : صف پشته Heap ، پياده سازي آنها ، ليست هاي كلي - پياده سازي رشته ها ُStrings - Garbage Collection

اسلاید 8: 8ريز مواد درس 4. داده ساختار هاي درخت - تعاريف اوليه ، درخت عبارت : Expression Tree - پياده سازي هاي مختلف درخت ها ، استقرا بر روي درخت پيمايش درخت استقراي ساختاري : Structural Induction درخت دودوئي : Binary Tree { توليد كد اسمبلي ازدرخت عبارت } اعمال مختلف بر روي درخت عبارت

اسلاید 9: 9ريز مواد درس 5. داده ساختار ها براي فرهنگ داده ها - درخت دودوئي جستجو : Binary search tree - درخت دودوئي جستجوي متوازن : Balanced binary search tree - درخت AVL - درخت ” قرمز – سياه ” - درخت بازه : Interval tree - درخت الفبا : Trie - درخت هاي 3-2

اسلاید 10: 10ريز مواد درس6 – ساير داده ساختار ها - صف اولويت و درخت نيمه مر تب : Priority Queue and Partially Ordered Tree

اسلاید 11: 11ريز مواد درس7 – الگوريتم هاي مرتب سازي Sorting Algorithms - درخت تصميم : Decision Tree - الگوريتم هاي ساده مرتب سازی : حبابي Bubble درجي Insertion انتخابي Selection - الگوريتم هاي با مرتبه خطي : Count sort - الگوريتم هاي با مرتبه غير خطي : Heap sort Radix sort Quick sort Bucket sort Shell sort External sort

اسلاید 12: 12ريز مواد درس Hash tables and related algorithms

اسلاید 13: 13نحوه ارزيابي درستمرين هاي درسي (مسائل تئوري ) .................. 2 نمره مسائل برنامه نويسي ...... 2 آزمون هاي كوتاه : 3 كوئيز ، هر كدام 1 نمره ........ 3 آزمون ميان ترم .............................................. 5آزمون پايان ترم ............................................. 8 جمع 20 نمره

اسلاید 14: 14كلاس هاي حل تمرين شنبه ها يا دوشنبه ها ساعت 1:00-12:00 شركت در كلاس هاي حل تمرين قويا ّّ توصيه ميشود.