חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תש"ף

  מבני נתונים ואלגורתמים
  Data Structures and Algorithms                                                                       
0512-2510-07
הנדסה | תואר ראשון - חשמל ואלקטרוניקה
סמ'  א'1100-1400102לימודי הנדסה - כיתותשיעור פרופ אפלבאום בנימין
ש"ס:  4.0

סילבוס מקוצר

2510מבני נתונים ואלגוריתמים  

Data Structures and Algorithms


משקל: 3.5
דרישות קדם:  תכנות 2 – שפת C (0512.1820) ומערכות לוגיות ספרתיות (0512.3561)

 

 

הקדמה: חיפוש איבר ברשימה ממוינת, חיפוש בינארי.  הגדרת סדר הגודל של פונקציה,  ניתוח נכונות וזמן ריצה של אלגוריתמים.
בעיית המיון (Sorting): מיון הכנסה (Insertion Sort).  מיון מיזוג (Merge Sort). מיון "מהיר" ((Quick Sort . חסם תחתון למיון במודל ההשוואות ומושג עץ ההכרעה (Decision Tree). מיון בזמן ליניארי.
טיפוסי נתונים מופשטים (Abstract Data Types) ומבני נתונים: מחסנית ותור. תור קדימויות וממוש ע"י ערימה (Heap). עצי חיפוש בינאריים ועצי 2-3. ניהול קבוצות זרות.
טכניקות אלגוריתמיות: פרדיגמת "הפרד ומשול"  (Divide and Conquer).   אלגוריתמים חמדניים (Greedy Algorithms). תכנון דינאמי  .(Dynamic Programming)
אלגוריתמים על גרפים: ייצוג גרפים. חיפוש על גרפים. מציאת עץ פורש מינימאלי, זרימה ברשתות.

 

ספרי לימוד:

Introduction to Algorithms (2nd edition),  Corman, Leiserson, Rivest, Stein

או

Introduction to Algorithms (1st edition),  Corman, Leiserson, Rivest

יש תרגום לעברית:  מבוא לאלגוריתמים, בהוצאת האוניברסיטה הפתוחה.

 

:                                Data Structures and Algorithms,  Aho, Hopcroft, Ullman

 

Course description

0512.2510   Data Structures and Algorithms

Credits: 3.5

Prerequisites: Programming in C (0512.1820) and Digital Logic Systems  (0512.3561)

 

Introduction: Binary Search, Order of growth of functions, Analysis of correctness and running times of algorithms.

The Sorting problem: Insertion sort, Merge sort, Quick sort, lower bound for sorting in the comparison model, sorting in linear time.

Abstract Data Types and Data Structures: stack and queue, priority queue and heap implementation, binary search trees and 2-3 trees, disjoint sets.

Algorithmic Techniques: divide and conquer paradigm, greedy algorithms, dynamic programming.

Graph algorithms: representations of graphs, searching on graphs (in particular, breadth first search), minimum spanning tree, network flow.

 

Textbooks:

Introduction to Algorithms (2nd ed.),  Corman, Leiserson, Rivest, Stein
(or Introduction to Algorithms (1st ed.),  Corman, Leiserson, Rivest                     (

 

Data Structures and Algorithms,  Aho, Hopcroft, and Ullman

סילבוס מפורט

הנדסה | תואר ראשון - חשמל ואלקטרוניקה
0512-2510-07 מבני נתונים ואלגורתמים
Data Structures and Algorithms
שנה"ל תש"ף | סמ'  א' | פרופ אפלבאום בנימין

666סילבוס מפורט/דף מידע

מבני נתונים ואלגוריתמים
  Data Structures and Algorithms

0512.2510

צוות הקורס:
 

מרצה:  פרופ' דנה רון, danaron@tau.ac.il, בניין "הנדסת תוכנה", 201.

מתרגלות:  לירון דוד, lirondavid@gmail.com,  בניין "הנדסת תכנה",  313.
                 טליה עדן, talyaa01@gmail.com,  בניין "הנדסת תכנה", 210.
           

בודקי תרגילים:   לילך בן-זקן,  benzakon@mail.tau.ac.il,  עידן גדנסקי, idangdanski@mail.tau.ac.il, בועז פיש boazfish@mail.tau.ac.il,

שעות קבלה: בתיאום מראש בדואר אלקטרוני.

 

אתר הקורס:  הכניסה דרך אתר Moodle: http://moodle.tau.ac.il                                          

 

נושאים:

  • הקדמה: חיפוש איבר במערך ממוין, חיפוש בינארי.  הגדרת סדר הגודל של פונקציה.

        ניתוח נכונות וזמן ריצה של אלגוריתמים.

  • בעיית המיון (Sorting): מיון הכנסה (Insertion Sort).  מיון מיזוג (Merge Sort). מיון "מהיר" ((Quick Sort . חסם תחתון למיון במודל ההשוואות ומושג עץ ההכרעה (Decision Tree). מיון  "ספירה" (Counting Sort).
  • טיפוסי נתונים מופשטים (Abstract Data Types) ומבני נתונים: מחסנית ותור. תור קדימויות וממוש ע"י ערימה (Heap). עצי חיפוש בינאריים ועצי 2-3. טבלאות ערבול. קבוצות זרות.
  • טכניקות אלגוריתמיות: פרדיגמת "הפרד ומשול"  (Divide and Conquer).   אלגוריתמים חמדניים (Greedy Algorithms). תכנון דינאמי (Dynamic Programming).
  • אלגוריתמים על גרפים: ייצוג גרפים. חיפוש על גרפים, זרימה ברשתות, עץ פורש עם משקל מינימאלי.

 

ספרות:

ספר הקורס הוא:          1. Introduction to Algorithms,  Corman, Leiserson, and Rivest (CLR)

לספר ישנן גרסאות ומהדורות רבות, וכן תרגום לעברית (של האוניברסיטה הפתוחה). אין חשיבות מיוחדת לגרסה או למהדורה.  
ספר נוסף:                       2. Data Structures and Algorithms,  Aho, Hopcroft, and Ullman (AHU)

 

מרכיבי הציון

  • תרגילים עיוניים: 10% מהציון הסופי. יינתן תרגיל כל שבוע או שבועיים.
  • מבחן סוף סמסטר: 90% מהציון הסופי

 

Data Structures and Algorithms

0512.2510

Lecturer: Prof. Dana Ron, danaron@tau.ac.il, “Software Engineering” building, room 201

Teaching Assistants:
      Liron David,  lirondavid@gmail.com,  “Software Engineering” building, room 313
      Talya Eden,  talyaa01@gmail.com,  “Software Engineering” building, room 210

Graders:
       
Lilach Ben-Zakon,  benzakon@mail.tau.ac.il,  Idan Gdanski,  idangdanski@mail.tau.ac.il
       Boaz Fish, boazfish@mail.tau.ac.il


Office hours shold be coordinated by email


Course website: access through Moodle - http://moodle.tau.ac.il  


Subjects covered in the course

  • Introduction: Searching in a sorted array, Binary search. Asymptotic notations. Analysis of correctness and running time of algorithms.
  • Sorting: Insertion Sort, Merge Sort, Quick Sort. Lower bound for sorting in the comparison model and the notion of a Decision Tree. Counting Sort.
  • Abstract Data Types and Data Structures: Stack and Queue, Priority Queue and its implementation by a Heap, Binary Search Trees and 2-3 Trees, Hash tables, Union-Find (disjoint sets).
  • Algorithmic techniques: Divide and Conquer, Greedy algorithms, Dynamic Programming.
  • Graph algorithms: Represenation of graphs, searching on graphs, Network Flow, Minimim Weight Spanning Tree (MST).

 

Textbooks

  • Introduction to Algorithms (2nd ed.),  Corman, Leiserson, Rivest, Stein (or Introduction to Algorithms (1sted.),  Corman, Leiserson, Rivest                     (
  • Data Structures and Algorithms,  Aho, Hopcroft, and Ullman

 

 The final grade of the course is based on 10% homework assignments (given weekly or biweekly), and 90% final exam.

להצהרת הנגישות


אוניברסיטת ת