שנה"ל תשע"ט

 
 Seminar - Topics in Bioinformatics 1 
 
 
 Extended Introduction to Computer Science 

בקורס מבואי זה יוצגו מושגי יסוד במדעי המחשב, לצד מושגים בתכנות ובשפות תכנות. השפה בה נשתמש תהיה פייתון, גרסא 3, והיא תהווה פלטפורמה להצגה וטיפול במגוון נושאים בעלי עניין כללי במדעי המחשב.

נושאים לדוגמא: מיון וחיפוש; מבוא למבני נתונים; טבלאות ערבול (hash tables); ייצוג תווים ומחרוזות, התאמת מחרוזות; ייצוג ועיבוד תמונה; קודים לתיקון טעויות; דחיסת טקסט; חישובים נומריים ויציבותם; פעולות על מספרים גדולים מאוד ושימושיהן בתורת המספרים (בדיקת ראשוניות) ובתורת ההצפנות (יצירת מפתח סודי משותף); תכנות מונחה עצמים; רקורסיה; מושגים בתכנות פונקציונלי, ייצוג עצמים אינסופיים במחשב, ועוד.

 

בחלק מהנושאים נציג ונשווה בין מספר גישות לפתרון הבעיה. יינתן דגש על נכונות הפתרונות, ועל הסיבוכיות שלהם, הן סיבוכיות אסימפטוטית והן זמן ריצה בפועל. 


הקורס שם דגש על חשיפה למגוון תחומים במדעי המחשב, ועל כן אינו קורס "טהור" בתכנות, אך המטלות בו יכללו כתיבת תכניות מחשב בהיקף משמעותי.

 
 
 Discrete Mathematics 

                    

מתמטיקה בדידה

                                            ספר לימוד  לקורס: ארנון אברון "מבוא למתמטיקה בדידה"

                                                           

 

                        ספרים נוספים בעברית:  שי גירון ושוני דר "מתמטיקה בדידה"

                                                            נתי ליניאל ומיכל פרנס "מתמטיקה בדידה"

                                                            האוניברסיטה הפתוחה: "מתמטיקה דיסקרטית" (4 חלקים)

 

 

תוכנית הקורס:

 

חלק ראשון  - מבוא ל"תרבות מתמטית"- לוגיקה ותורת הקבוצות  

 

 

מושגים  בלוגיקה                        

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

 

 

מושגי יסוד בתורת הקבוצות      

קבוצות ואברים;  תת קבוצות; סימון קבוצות;   הפרדוקס של ראסל; עקרונות לבניית קבוצות;  הקבוצה הריקה;  קבוצת החזקה;  איחוד,  חיתוך, משלים, הפרש ותכונותיהם;  איחוד וחיתוך מוכללים

 

פונקציות ויחסים                        

זוגות סדורים; מכפלה קרטזית; יחסים;  היחס ההפוך;  הרכבת יחסים;  יחס מלא ויחס חד ערכי

פונקציות: פונקציות ופונקציות חלקיות; סימון l; פעולת החזקה בין קבוצות; פונקציות הפיכות                             

יחסים בתוך קבוצה ומיונם: תכונות של יחסים;  יחסי שקילות וחלוקות;  יחסי סדר

 

עוצמות                                     

עוצמה של קבוצה;  המספרים הטבעיים;  עוצמות אינסופיות; קבוצות בנות מניה ושימושיהן, אריתמטיקה של עוצמות;  סדר העוצמות; משפט  קנטור שרדר-ברנשטיין; קבוצות אינסופיות שאינן בנות מניה;  משפט קנטור

 

 

 

חלק שני - מבוא לקומבינטוריקה

 

 

עקרונות קומבינטוריים כלליים              

עקרונות החיבור והכפל;  עקרון שובך היונים; תמורות וצירופים

 

קומבינטוריקה סופית בסיסית               

תמורות עם או בלי חזרות; צרופים עם או בלי חזרות; הוכחות קומבינטוריות ; נוסחת הבינום; משולש פסקל;  תכונות של המקדמים הבינומיים    

 

עקרון ההכלה וההדחה              

פיתוח הנוסחה; שימושים; אי-סדר מלא

 

פונקציות  יוצרות                                               

הגדרה; מציאת פונקציות יוצרות; מציאת סדרות נוצרות; אופרטור הסכימה; פונקציות יוצרות מעריכית; שימושים לבעיות קומבינטוריות

 

רקורסיה                                                          

סדרות המוגדרות ברקורסיה; סדרת פיבונצ'י; משוואות נסיגה;  פתרון באמצעות פונקציות יוצרות רגילות; פתרון באמצעות הפולינום האופייני;  משואות נסיגה לינאריות הומוגניות במקדמים קבועים

 

מבוא לתורת הגרפים                 

הגדרות ושמושים אלמנטריים;  מסילות מעגלים וקשירות; עצים ונוסחת קיילי;  נושאים נוספים ככל שיתאפשר.

 
 
 Probability and Statistics 

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

נושאים נוספים מתוך: הלמה של בורל קנטלי, החוק החזק, מושגים בהסקה סטטיסטית, אומד חסר הטיה, אומד נראות מכסימלי.

 
 
 Laboratory for Bioinformatics Tools 
 
 
 Seminar - Topics in Bioinformatics 2 
 
 
 Software 1 

 הקורס מציג את המתודולגיה של תכנות מונחה עצמים ואת שפת התכנות ג'אווה. הקורס עוסק גם בצדדים תיאורטיים ועקרוניים של תכנות מונחה עצמים וגם מקנה מיומנויות תכנות בג'אווה. בצד התיאורטי, הקורס עוסק בנושאים: נכונות של מחלקה, נכונות במחלקות יורשות ומממשות, חוזים, משמעות ותיכון נכון של חריגים, טיפוסים גנריים, ועוד. בצד המעשי, הקורס מלמד את שפת ג'אווה ואת השימוש בספריות הסטנדרטיות שלה, כולל גישה לקבצים, מבני נתונים, שימוש בסביבת פיתוח מתקדמת, בדיקות תכנה וכדומה.

 

 

 

 

 
 
 Data Structures 
טיפוס נתונים מופשט, רשימות לינאריות, מחסניות, תורים, רשימות משולבות, עצים, עצי חיפוש בינארי, עצים מאוזנים, תור עדיפות, העתקות מפתח, שיטות מיון, מיון חצוני, עציB-
 
 
 Computer Structure 

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

 
 
 Algorithms 

אלגוריתמים יעילים בגרפים: סריקה של גרף, מעגל אוילר, עץ פורש מינימלי, מסלולים קצרים ביותר, זרימה ברשתות; טכניקות אלגוריתמיות נוספות לרבות תכנות דינאמי ותכנות לינארי.

 

 

 
 
 Software Project 

בקורס נלמדת שפת התכנות C ונכתב פרויקט תכנות מתקדם. שפת C היא שפה ותיקה שהשפעתה על עולם התכנות בעשורים האחרונים גדולה ביותר. בקורס נלמד את השפה לעומק ונסביר את הסיבות לפופולריות העצומה שלה.

הנושאים הבאים יועברו במסגרת לימוד שפת C:

  • תחביר השפה 
  • טיפוסים
  • מבני בקרה
  • פונקציות
  • מצביעים
  • ה Preprocessor
  • טיפול בקבצים
  • נושאי העשרה קשורים כמו  Computer Security, תכנון ופיתוח פרויקטים גדולים ותכנות מקבילי

במסגרת הקורס הסטודנטים יכתבו פרויקט מתקדם בשפת C תחת מערכת הפעלה UNIX.

 
 
 Operating Systems 
תכנון ומימוש מערכות הפעלה: תהליכים. קבצים ומערכת קבצים. שימוש במשאב משותף: מניעה הדדית, נעילות, סמפורים. תזמון תהליכים. ניהול זכּרון, דפדוף, זכּרון וירטואלי. יסודות רשתות מחשבים.

 
 
 Logic for Computer Science 
תחשיב פסוקים, תחשיב הפרדיקטים והכללותיו, שימושים כשפת ספציפיות, שפת שאילתות ולצורך אימות של תכניות, משפט הרברנד ויסודות התכנות בלוגיקה, לוגיקה מודלית, לוגיקה אינטואיציונליסטית ולוגיקות לא קלאסיות אחרות, תורות כריעות ואי כריעות, משפט אי השלמות.
 
 
 Computational Models 

אוטומטים סופיים ושפות רגולריות . למות ניפוח. אוטומטי מחסנית, דטרמיניסטיים ואי דטרמיניסטיים. דקדוקים ושפות חסרות הקשר. מכונות Turing. מודלים נוספים ושקילותם למכונות Turing (כולל RAM). התאזה של Church  ו– Turing. מכונות Turing אוניברסליות. אי כריעות של בעיית העצירה. רדוקציות מיפוי. משפט Rice. בעיות אי כריעות נוספות. סיבוכיות Kolmogorov. הבעיה העשירית של Hilbert (סקירה). משפט הרקורסיה. מחלקות זמן דטרמיניסטיות ואי דטרמיניסטיות. המחלקה NP. משפט Cook-Levin (ניסוח בלבד). רדוקציות פולינומיאליות, מושגי  NP שלמות ו– NP קושי: הגדרות ודוגמאות.
אתר הקורס: moodle.tau.ac.il/course/view.php?id=368220001

 

 
 
 Communication Networks - 

Course name: Communication Networks

 

Course Syllabus

 

Lecturer: Dr. Nir Andelman, 054-2451042, niran@tauex.tau.ac.il

 

(Credit: 4 (3+1

 

Prerequisites: Algorithms, Introduction to Probability, Software Project

 

:Course Objectives

The course provides an introduction to the principles, challenges and techniques used in designing network architectures and protocols. 

The focus of the course is: network architectures, the layering model, the protocol concept, performance modeling, the Internet. Some of the topics included in detail: network programming, STP, ARP, reliable data transfer, flow and congestion control, addressing, routing algorithms,

 

:Course Syllabus

·         Introduction to network, layers and protocols

·         Datalink layer protocols, LAN protocols

·         LAN connectivity: Hubs, bridges, routers

·         Network layer: types of networks, addressing, forwarding, IP

·         Routing protocols & algorithms

·         Reliable data transfer issues and design alternatives

·         TCP handshake, data transfer, flow control,

·         TCP congestion control

·         Application protocols, Network security

·         Advanced topics (e.g. switching networks, scheduling ,  mobile IP, multicast) as time permits

 

:Course prerequisites

Algorithms, Introduction to Probability, Software Project

 

:Course requirements

(Homework Assignments submission (should be done in pairs 

 

:Required reading

None

 

 

 

 

:Recommended reading

[1]   James F. Kurose and Keith W. Ross, “Computer Networking: A Top-Down Approach Featuring the Internet”, Addison-Wesley 5th Edition (2009), 6th ed. (2012

[2]   S. Tanenbaum, “Computer Networks”,  Prentice-Hall, 4th ed. (2003) / 3rd ed (1996)

[3]   R. Perlman: Interconnections : Bridges, Routers, Switches and Interworking Protocols, Addisoin Wesley 2000

[4]   R. Stevens: TCP/IP Illustrated vol. I The Protocols, Addison Wesley 1994

[5]   R. Stevens, B. Fenner, A.M. Rudoff: UNIX Network Programming: The Socket Networking API , vol. 1, 3rd Edition, Addison Wesley 2004

 

 

 

Grade: 70% final exam, 15% programming exercises, 15% theoretical

             exercises

 

 

 

 

 

 
 
 Introduction to Modern Cryptography 

 
   בקורס נעסוק במספר אבני בניין יסודיות של קריפטוגרפיה קלסית ומודרנית. אלה יכללו פונקציות חד כווניות, מערכות הצפנה עם מפתחות סימטריים, ומערכות עם מפתח הצפנה פומבי. שיטות לאימות, זיהוי, וחתימות דיגיטליות. אקראיות ופסאודו אקראיות. 
 וסכמות לחלוקת סוד. כמו כן נדון באספקטים אלגוריתמיים של מספר נושאים רלוונטיים מתורת המספרים, כגון בדיקת ראשוניות, משפט המספרים הראשוניים, מציאת מחלק משותף, שדות וחוגים סופיים, יוצרים כפליים, ועוד.

 
 
 Advanced Topics in Programing 

סילבוס נושאים מתקדמים בתכנות

סמ' ב' תשע"ט

מרצה : אמיר קירש

(kirsh@post.tau.ac.il)

דרישות קדם

סיום בהצלחה של הקורס "פרוייקט תוכנה"

ידיעת שפת C

היכרות טובה עם שפה OOP כלשהי (למשל Java): מחלקות, הורשה, פולימורפיזם, כתיבת קוד גנרי.

שימו לב: שמו של הקורס עלול להיות מטעה. במהלך הקורס בעיקר נצלול לתוך פרטי תחביר של C++ ונתעסק באופן סיזיפי במימוש של פרוייקט מורכב. השאלה האם מדובר בנושאים מתקדמים נתונה לפרשנות. מי שפחות אוהב לתכנת עלול למצוא שהקורס מייגע ולא מועיל עבורו. לעומת זאת מי שאוהב אתגר תכנותי ועבודה קשה כנראה יימצא בקורס עניין.

נושאי הקורס

למידה והבנה של תחביר C++

שיקולים בתכנות object oriented 

תכנות גנרי

multi threading

נגיעה קלה ב-design patterns (בין שיעור לחצי שיעור במהלך הקורס)

תרגילים

במהלך הקורס יינתנו 4 תרגילי תכנות קשים

יש להגיש את התרגילים בזוגות.

ציון סופי

40% תרגילים

60% מבחן

על מנת לעבור את הקורס יש לקבל ציון עובר במבחן.

רשימת קריאה

ספרים מאת מייסד השפה

A Tour of C++ , Bjarne Stroustrup, AddisonWesley, 2013

The C++ Programming Language , Bjarne Stroustrup, Addison Wesley, 4th edition, 2013

Programming Principles and Practice Using C++ , Bjarne Stroustrup, AddisonWesley, 2014

סידרת ספרי ה-More Effective מהאורים והתומים של השפה Scott Meyers:

Effective C++, Scott Meyers, AddisonWesley, 3rd edition, 2005

More Effective C++ , Scott Meyers, AddisonWesley, 1996

Effective STL , Scott Meyers, AddisonWesley, 2001

Effective Modern C++ , Scott Meyers, AddisonWesley, 2014

הספר הידוע והמפורסם של design pattterns מחבורת הארבעה (The Gang of Four):

Design Patterns: Elements of Reusable ObjectOriented Software, Erich Gamma, John Vlissides, Ralph Johnson, and Richard Helm, AddisonWesley, 1994

 

מקורות ברשת (רשימה חלקית של מקורות רלבנטיים)

אתר הבית של תקן השפה:

https://isocpp.org , https://isocpp.org/faq , https://isocpp.org/wiki/faq/cpp11

האתר של Bjarne Stroustrup:

http://www.stroustrup.comhttp://www.stroustrup.com/C++11FAQ.html

אתר הרפרנס של השפה - כולל את הפירוט המלא של השפה, כלי עזר חשוב:

http://en.cppreference.comhttp://en.cppreference.com/w/cpp/language

מקורות נוספים:

http://www.cplusplus.com

http://www.cplusplus.com/doc/tutorial/

http://www.cplusplus.com/articles/

StackOverflow:

http://stackoverflow.com/tags/c++

http://stackoverflow.com/tags/c++/info

http://stackoverflow.com/tags/c++faq

אתר מצויין שמרכז C++ Idioms:

http://en.wikibooks.org/wiki/More_C++_Idioms

 

 
 
 Web Data Management 

Web Data Management

Dr. Daniel Deutch

The course discusses various algorithmic aspects of web data management. Web data has distinctive features: it contains both structured (tables), semi-structured (XML and linked data), and unstructured data (text); it is large-scale, contains contradicting pieces of data, and is uncertain. 

To be able to deal with this ocean of information, there is a need for new models as well as efficient retrieval, recommendation, and ranking techniques.

The goal of this course is to teach state-of-the-art models and algorithmic techniques for dealing with web data, in light of these challenging features.

In particular, we will start with an overview of models for structured data (in particular the relational and the nested relational models), semi-structured data (XML, tree automata, Web Graphs..), and unstructured data (Context-Free and Context-sensitive Languages). We will highlight some key issues in the design and usage of these models, in the context of web data. For each model, we will further introduce a probabilistic variant that allows to model uncertainty (probabilistic databases, probabilistic XML, HMMs, PCFGs, ..).  We will introduce analysis tasks (and query languages that capture them where appropriate) for all cases (relational algebra, XQuery and XPath, Text analysis with HMMs and PCFGs, Ranking web-pages) and state-of-the-art algorithms   for performing these tasks in the context of the probabilistic models that were studied.  The algorithms will include  techniques for evaluating relational algebra on probabilistic databases;  Google PageRank algorithm; algorithms for computing Part-of-speech tagging in text analysis; algorithms for recommendations,  and many others.

  

Bibliography:

 

 

Books

 

1. Serge Abiteboul,  Ioana Manolescu, Philippe Rigaux, Marie-Christine Rousset, Pierre Senellart,

 

    Web Data Management,  Cambridge University Press 2011


2. Dan Suciu​‌, Dan Olteanu​‌, Christopher Ré ​‌, Christoph Koch​‌ 

    Probabilistic databases,  Morgan and Claypool 2011

 


 


Papers

1. Brin, Page


 The Anatomy of a Large-Scale Hypertextual Web Search Engine, Computer Networks and ISDN Systems 30 (7), 1998

2. Fagin,

Kumar, Sivakumar, COMPARING TOP k LISTS SIAM J. Discrete Math 17 (1), 2003

3. Fagin, Lotem, Naor,

Optimal aggregation algorithms for middleware, in Proc. of SIGMOD ‘01

4. Sarwar, Karypis, Konstan, Reidl,

Item-based collaborative filtering recommendation algorithms in proc. of WWW’01

5. Wang, De Vries, Reinders,

Unifying user-based and item-based Collaborative Filtering in proc. of SIGIR ‘06

6. Kleinberg,

Authoritative sources in a hyperlinked environment, in JACM 46 (5), 1999

7. Serge Abiteboul, Benny Kimelfeld, Yehoshua Sagiv, Pierre Senellart:

     On the expressiveness of probabilistic XML models. VLDB J. 18(5), 2009

 
 
 Introduction to Information Security 
ראו פרטים באנגלית בהמשך, ואת אתר הקורס.
 
 
 Systems and Algorithms for Localization, Navigation and Mapping 

מערכות ואלגוריתמים לאיכון וניווט חדרו לחיי היום-יום של כולנו: הטלפון החכם משערך את מיקומנו ובכך מאפשר יישומי ניווט כגון וייז ושירותים מבוססי מיקום מתקדמים אחרים. לטכנולוגיה הזאת ודומותיה יש כמובן גם שימושים אזרחיים וצבאיים רבים נוספים, כגון שליטה על כלי רכב אוטונומיים, ניווט בסביבות חסרות נקודות ציון (ספינות בים ומטוסים בלילה), נחיתה בערפל, ועוד. כיצד מתבצע ה-"קסם" הזה של שערוך מדוייק של מיקום של מטרה, מרוחקת או עצמית?

הקורס מסביר את העקרונות הבסיסיים של שערוך מיקום, מציג מספר מערכות איכון מעניינות (כולל תיאור מפורט למדי של מערכת ה-GPS וחלופות חדשות לה, וכן של מערכות איכון בתוך בניינים), ומסביר כיצד מציגים בעיית איכון כבעיה אלגוריתמית/מתמטית וכיצד פותרים את אותן בעיות.

במסגרת זאת הקורס מציג מושגי יסוד בתורת השערוך הקלסית (שערוך של משתנים דטרמיניסטיים מתוך מדידות רועשות), עקרונות לשערוך אופטימלי, חסמים על דיוק, והמרה של בעיות שערוך לבעיות אופטימיציה, בדרך כלל לא לינראריות, גם בעיות רציפות וגם בעיות מעורבות (חלק מהמשתנים רציפים וחלק שלמים). נדון גם בשערוך של מסלולי תנועה שלמים (פילטר קלמן ונגזרותיו) ובבעיות עיבוד אותות שמערכות איכון צריכות להתמודד איתן, בעיקר שערוך זמן הגעה של אות רדיו.

המטלות בקורס כוללות כשש או שבע מטלות בית. המטלות מתמקדות בהצגת בעיות איכון כבעיות אופטימיצזיה, במימוש וחקר אלגוריתמים לפתרון בעיות האופטימיזציה הללו, במימוש וחקר אלגוריתמים רלוונטיים לעיבוד אותות (כולל עיבוד אותות GPS אמיתיים שהוקלטו מול בניין שרייבר), ובחקר הביצועים של מערכות איכון. המטלות ממומשות בסביבת Matlab (ניתן להשתמש בסביבות אחרות בחלק מהמטלות אבל ללא תמיכה נוספת מהמרצה).

בקורס תתקיים בחינה.

הקורס מיועד לתלמידי תואר ראשון ושני במדעי המחשב, והוא מתאים גם לתלמידי מתימטיקה והנדסה.

 
 
 Reinforcement Learning 

 Introduction, Optimal Policy, Planning MDP (Bellman optimality equations), Value iteration,

Policy iteration, Dynamic Programming, Learning MDP (small state spaces), TD Learning,

Model base learning, Model free: Q learning, Policy gradient, Actor critic, 

Learning MDP (large state spaces), Deep Learning, Multi-Arm Bandit,

Inverse RL, POMDP

 
 
 Algorithms and Applications in Social Networks 

Tentative topics: 

  • Intro and examples of Social Networks
  • Social Networks structure
  • Networks formation
  • Communities (formation and detection)
  • Links prediction
  • Social Networks partitioning
  • Influence in Social Networks
  • Social media and social content (feed generation algorithms, advertisements)
 
 
 Natural Language Processing 
 
 
 Computational Genomics 
המחקר הביולוגי והרפואי עבר מהפכה בעקבות ריצוף הגנום האנושי – תחילה רוצף גנום בודד וכיום מרוצפים מדי שנה רבבות גנומים של בני אדם, ובמקביל גנומים של יצורים חיים אחרים (בעלי חיים, צמחים, חידקים ועוד). טכנולוגיות נסיוניות חדישות מתפתחות ומייצרות מידע המאפשר לחשוף תובנות מהפכניות לגבי חיינו, בריאותנו והעולם שסביבנו. ניתוח מידע זה מחייב שיטות חישוביות מתקדמות, ובמידה רבה צוואר הבקבוק של הניתוח עבר מייצור המידע לניתוחו.  
הקורס ידון באלגוריתמים לבעיות חישוביות מרכזיות בביולוגיה וברפואה. אנו נלמד אלגוריתמים מדויקים לבעיות שניתן לפתרן ביעילות, ואלגוריתמי קירוב והיוריסטיקות לבעיות קשות יותר. דוגמאות ביולוגיות יוצגו לכל בעיה. השיטות החישוביות משלבות אלגוריתמים, סיבוכיות, תורת הגרפים, הסתברות, סטטיסטיקה, אופטימיזציה, למידה חישובית ועוד. פירוט הנושאים שיילמדו מוצג באתר הקורס.
הקורס אינו דורש רקע ביולוגי.
 
 
 Seminar - Topics in Bioinfprmatics 3 
 
 
 Computational Structural Biology 
 
 
 Seminar on selected topics in theory of computer science 

הסמינר יעסוק בנושאים מתקדמים בתיאוריה של מדעי המחשב בדגש על הוכחת חסמים תחתונים למעגלים בוליאנים. על התלמידים המשתתפים בסמינר להעביר הרצאה באנגלית על מאמר בתחום.

 
 
 Seminar in Formal Verification 

הסמינר יעסוק באימות פורמלי. נדון בלוגיקות טמפורליות שונות, אלגוריתמי בדיקת מודל עבור הלוגיקות השונות וטכניקות שונות להתמודדות עם בעיית התפוצצות המצבים המתעוררת בבדיקת מודל.

דרישת קדם: לוגיקה למדעי המחשב

 
 
 Seminar in Teaching Computer Science 

בסמינר נדון באוסף נושאים הקשורים להוראה ולימוד של מדעי המחשב. הסמינר מיועד לסטודנטים של מדעי המחשב, שמעוניינים להרחיב את השכלתם על התחום אותו הם לומדים מנקודת מבט שלא נכללת בתוכנית הלימודים באוניברסיטה.

מטרות הסמינר

  • העמקת החשיפה לסוגיות שונות הקשורות להוראה ולמידה של מדעי המחשב, ובכך פיתוח החשיבה הביקורתית של המשתתפים על הוראת תחום הלימודים שלהם. בוגרי מדעי המחשב עשויים למצוא עצמם בעתיד בעמדה של "מתווכי ידע" (מרצים או מתרגלים באקדמיה, העברת הדרכות וסמינרים לקולגות במקום עבודתם, מתן הרצאות לקהל הרחב). חשיפה לסוגיות השונות בהוראה ולמידה של מדמ"ח תתרום ליכולתם לעשות זאת באופן מוצלח.
  • הרחבת נקודת המבט של המשתתפים על התחום של מדעי המחשב מכיוון שאיננו מתמטי-מדעי-טכנולוגי, ובכך חיזוק הזהות המקצועית שלהם. בוגרי מדמ"ח שאינם נחשפים לסוגיות מסוג זה עלולים לחוות את התחום בו הם עוסקים באופן צר יותר, פחות מאוזן, ופחות מקושר להיבטים "רכים" שלו (כמו היבטים חברתיים, חינוכיים, אתיים, היסטוריים וכו').

 

מהנושאים בהם יעסוק הסמינר

רשימת נושאים ממוקדת וחלוקת נושאים למשתתפים תתתבצע בתחילת הסמסטר, לאחר שמספר המשתתפים יתייצב. כמו כן המשתתפים מוזמנים להציע נושאים וסוגיות נוספות לאישור המרצה.

  • היסטוריה של מדעי המחשב
    • אבני דרך בהתפתחות עולם החומרה
    • אבני דרך בהתפתחות עולם התוכנה והנדסת תוכנה
    • אבני דרך בהתפתחות האינטרנט
  • הגדרת התחום של מדעי המחשב
    • מדעי המחשב – זה מדע? זו הנדסה? זה ענף של מתמטיקה?
    • מה בין מחשבים למדעי המחשב?
    • אבחנה בין עקרונות יסוד של התחום למימושים משתנים שלהם
  • חשיבה חישובית
    • מהו אופן המחשבה המאפיין מדעני מחשב ומבחין אותם מתחומים אחרים?
  • תוכניות לימוד באוניברסיטה
    • סקירת תוכניות לימוד אקדמיות (ברמת אוניברסיטה / מכללה) וגישות שונות.
    • מה הופך תוכנית לימודים למוצלחת?
    • האם וכמה צריך ללמוד מתמטיקה?
    • הבדלים בין תוכניות ל- CS majors ולסטודנטים שאינם לומדים לתואר במדמ"ח (למשל סטודנטים לביולוגיה)
    • תוכניות לימוד ברמת בית ספר בארץ ובעולם
  • שיטות מחקר בהוראת מדעי המחשב
    • איך מבצעים מחקר בתחום כזה? במה הוא שונה ממחקר מדעי במדמ"ח? מחקר איכותני (qualitative) וכמותני (quantitative).
  • שפת תכנות ראשונה
    • מהי "שפת אם" מוצלחת? האם זה כל כך חשוב?
  • גיוון חברתי במדעי המחשב
    • למה מספר הנשים במדמ"ח יורד דרמטית עם ההתקדמות בתארים? מה המצב בבתי הספר בארץ ובעולם? האם זו בעייה בכלל? ואם כן האם צריך להתערב?
    • תת-ייצוג של מיעוטים חברתיים במדעי המחשב ותחומי הנדסה נלווים 
  • הגיל המתאים להתחלת לימוד מדמ"ח
    • האם אפשר ללמוד מדמ"ח כבר בגן או בבית הספר היסודי? האם כדאי?
  • גישות הוראה לא סטנדרטיות / חדשניות
    • קורסים מקוונים (MOOCs) – סקירת מצב. ברכה או קללה? מה מייחד קורסים מקוונים במדמ"ח משאר הקורסים המקוונים?
    • הכיתה ההפוכה (flipped classroom)
    • לימוד מבוסס פרוייקטים (project based learning)
    • לימוד מבוסס חקר (research based learning)
  • נושאים נוספים ע"פ עניין המשתתפים

 

חובות המשתתפים בסמינר

  1. כל משתתף/ת יידרשו להעביר הרצאה שמשכה כשיעור עד שיעור וחצי (תלוי במספר המשתתפים), ואשר תתבסס על מאמרים באנגלית ועל חומרים נוספים, שאת חלקם על הסטודנטים למצוא בעצמם. סקר ספרות וחיפוש מקורות מתאימים, בהדרכת המרצה, הוא חלק מהדרישות. חלק מכל הרצאה יוקדש לדיון שיונחה ע"י הסטודנט.
  2. המשתתפים יחולקו לקבוצות ויידרשו להכין הצעה לשיפור תוכנית הלימודים הקיימת במדמ"ח באוניברסיטת תל אביב או קורס ספציפי , תוך התייחסות לסוגיות שיידונו במהלך הסמסטר. ההצעות יוצגו בשיעורים האחרונים של הסמסטר.
  3. כל סטודנט יידרש לרשום סיכום תמציתי של כעמוד אחד עבור הרצאה של סטודנט אחר.

 

קביעת הציון תתבסס על הנ"ל + נוכחות + התרשמות ממידת העניין והתרומה לדיונים.

נוכחות: הנוכחות בכל פגישות הסמינר חובה. איחור של חמש דקות ומעלה ייחשב להיעדרות החל בפעם השניה.

דרישת קדם: מורשים להשתתף בסמינר סטודנטים וסטודנטיות משנה ג'. בקשות חריגות תישקלנה על בסיס מקום פנוי. מטרת דרישת הקדם היא להבטיח בסיס ידע משותף ורחב מספיק.

 

לשאלות והתלבטויות ניתן לפנות למרצה במייל (amirr ואז הסימן @ ואז tau.ac.il)

 
 
 Compilation 
ניתוח לקסיקלי ותחבירי (כולל שימוש בכלים כגון Lex ו- Yacc). דקדוקים מופשטים. יצירת קוד ביניים. בחירה יעילה של קוד מכונה. מבוא לאופטימיזציה והקצאת אוגרים.
הקורס כולל פרוייקט גדול של בניית קומפילר משפת תכנות קטנה לשפת מכונה.
 
 
 Computational Complexity 
 
 
 Topics in Software Engineering 
 
 
 Seminar in Digital Humanities 

 

 

 
 
 Introduction to Machine Learning 
 
 
 Fundamentals of Computer Graphics, Vision and Image Processing 
 
 
 Programming Languages 
יסודות התחביר והסמנטיקה של שפות תכנות. לימוד משווה של מספר שפות תכנות על מרכיביהם העיקריים (מבני בקרה, טיפוסי נתונים, הפשטה, כבילה וכו'). פרדיגמות של שפות תכנות. מבוא לסמנטיקה פורמלית של שפות תכנות
 
 
 
 Computer Science Learning in the Community 
 
 
 First Steps in Research of Outstanding Students 

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

במהלך הקורס הסטודנטים ייחשפו לתחומי המחקר של רבים מחברי סגל בית הספר למדעי המחשב.

הקורס מיועד לסטודנטים מצטיינים בתואר ראשון הלוקחים חלק בתכנית לעידוד מצוינות ומחקר של ביה"ס למדעי המחשב ושמעוניינים באפשרות להמשיך את לימודיהם לתואר שני במדעי המחשב.

הסטודנטים יתבקשו לבחור באחד מהנושאים שילמדו בקורס ולבצע בו עבודת מחקר בהיקף בינוני, תוך שיתוף פעולה עם המנחה הרלוונטי.

תוצאות המחקר יסוכמו במאמר, שבמידת האפשר ישלח לפרסום. מאמר כזה יכול להיות משמעותי מאוד בהמשך הלימודים לתואר שני.

 

דרישות קבלה: הקורס מיועד לתלמידי תואר ראשון בשנה השלישית ללימודים המשתתפים בתכנית לעידוד מצוינות ומחקר של ביה"ס למדעי המחשב.

 
 
 Web System and Application Security 

Web based systems (i.e. systems which are based on the HTTP protocol, including mobile and cloud based applicationsa) are facing unique threats from information security perspective, at the network layer, at the infrastructure layer, and at the application layer. In the course we will learn how to perform threat modeling to a web system, and how to secure the web system by implementing security mechanisms and security best practices. We will learn how to secure the access to a network using firewalls, how to harden the web system infrastructure, and how to secure the application layer by implementing authentication and authorization mechanisms, and web session management. In addition, we will discuss (web) application vulnerabilities and related attacks (e.g. Injection attacks, XSS, XSRF, etc.), and will learn how to prevent them by implementing secure coding best practices.

 
 
 Convolution Neural Networks 

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

 

  • סיווג תמונות: גישה מונחית נתונים, K-Nearest Neighbours, סיווג לינארי

  • פונקציות לוס ואופטימיזציה: High Level Representations, Stochastic Gradient Descent

  • רשתות נוירונים: Backpropagation, Multilayer Perceptrons

  • ארכיטקטורות של רשתות נוירונים: פונקציות אקטיבציה.

  • רשתות קונבולוציה: קונבולוציות, pooling, רשתות קונבולוציה מחוץ לראייה ממוחשבת

  • אימון רשתות נוירונים: אתחולים, רגולריזציה, נרמול, אנסמבלים, למידת העברה, שיטות עדכון, vanishing and exploding gradients, overfitting and underfitting

  • ארכיטקטורות של רשתות קונבולוציה: AlexNet, VGG, GoogleNet, ResNet

  • רשתות נוירונים רקורסיביות: RNN, LSTM, GRU

  • זיהוי אובייקטים: detection and segmentation

  • מודלים גנרטיביים: GAN, Variational AutoEncoders

  • למידה לא מבוקרת מול למידה מבוקרת.

מומלץ לדעת את החומר של הקורס מבוא ללמידה חישובית (אבל לא חובה).

 
 
 Introduction to Data Science 

Syllabus:

http://slavanov.com/teaching/ds1718b/

 
 
 A high level view of Computer Science 

מבט על: מדעי המחשב

אמיר רובינשטיין ובני שור

בסמינר נדון באוסף נושאים בעלי חשיבות להתפתחות התחום של מדעי המחשב, ולהשפעותיו בסוגיות שחורגות מהפן הטכני, כגון: הגדרת התחום של מדעי המחשב, ההיסטוריה של התחום (הן המדעית והן הפוליטית-אקדמית), האם "מדעי המחשב" הם דיסציפלינה מדעית, הוראה ותכניות לימודים במדעי המחשב, מהי חשיבה חישובית (computational thinking), סוגיות חברתיות ואתיות והקשר ללמידה חישובית ובינה מלאכותית, ועוד.

מטרת הסמינר היא להרחיב את נקודת המבט של המשתתפים על התחום בו הם עוסקים, ולהעמיק את חשיפתם להיבטים של מדעי המחשב שאין מרבים לעסוק בהם במסגרת תכנית הלימודים באוניברסיטה.

כל סטודנט יידרש להעביר הרצאה שמשכה כשעה עד שעתיים, ואשר תתבסס על מאמרים ועל חומרים נוספים, שאת חלקם על הסטודנטים למצוא בעצמם. איסוף וסינון החומרים הרלוונטיים הוא חלק מהדרישות ומהציון. בנוסף, כל סטודנט יידרש לסכם הרצאה אחת של סטודנט אחר.

ייתכן שבחלק מהשבועות כלל הסטודנטים יידרשו לקרוא לפני הפגישה חלקים נבחרים מהמקורות הרלוונטיים, זאת על מנת להגיע מוכנים להרצאות ולאפשר דיון מעמיק יותר.

הנוכחות בכל פגישות הסמינר חובה.

דרישת קדם: מודלים חישוביים.

 
 
 Seminar 

  

 
 
 Data-Base Systems 

1

. תוכן הקורס:

 

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

 

נתחיל בהכרת המודל הרלציוני ושפת השאילתות SQL, ובלימוד שיטות לתכנון המסד. בהמשך נדון בארכיטקטורה הפנימית של המערכות, כולל אכסון נתונים יעיל, אופטימיזציה של שאילתות, שערוך יעיל של שאילתות, וכדומה. לקראת סוף הקורס, בהתאם למגבלות הזמן, נלמד על נושאים מתקדמים כגון שערוך מבוזר של שאילתות, MapReduce ו-Pig Latin, ניהול מידע בעזרת הקהל (crowdsourcing) ועוד.

 

 

 

2. חובות התלמיד:

 

השתתפות בשיעורים, הגשה של פתרונות התרגילים והפרויקט, מבחן מסכם.

 

 

 

3. הרכב הציון:            

 

תרגילים 15%

 

פרויקט: 35%

 

מבחן: 50%

 

 

תרגילים/פרויקט שיוגשו באיחור לא יתקבלו (מלבד מיקרים המאושרים אל פי התקנון)                                      

4. חומרי עזר :

     בדף הבית    http://courses.cs.tau.ac.il/databases/databases201718/index.php 

 
 
 "Digital Signal Processing" 

הקורס נועד לתלמידי תואר ראשון ושני במדעי המחשב או מתימטיקה.

 

הקורס מתבסס על ספר לימוד "Digital Signal Processing - a Computer Science Perspective"

(Wiley:2000)   מאת המרצה.

 

רשימת הנושאים, ובעיקר חלק היישומים שבה, עשויה להשתנות בהתאם לתחומי העניין של קהל הסטודנטים.

השתתפות בהרצאות חובה. אין חובה להגיש עבודות.

רקע מתימטי דרוש:

·                מספרים מרוכבים

·                פונקציות טריגונומריות ואקספוננציאליות

·                מושגי יסוד באלגברה ליניארית (מרחב ווקטורי, מטריצה, פתרון משוואות ליניאריות)

·                אינפי בסיסי (נגזרת, אנטגרל, טור אינסופי)

 

 

רשימת הנושאים הנלמדים

 

אותות

1) אותות אנאלוגיים וספרתיים, משפט הדגימה

2) ייצוג בזמן ובתדר

3) ספקטרום, טרנספורם הילברט, טרנספורם Z, עקרון אי-הוודאות

4) רעש

 

מערכות לעיבוד אותות

1) מסננים ומערכות שאינן מסננים

2) מסנני MA, AR, ו ARMA

3) תגובה לתדר, תגובה להלם, פונקצית תמסורת, גרפים של אפסים וקטבים

4) זיהוי מערכות

5) מסננים מתואמים  (במידה ויספיק הזמן)

6) מסננים אדפטיביים  (במידה ויספיק הזמן)

 

אלגוריתמים וארכיטקטורות חישוב

1) השימוש בגרפים ויישום מסננים סיפרתיים

2) אלגוריתם ה FFT

3) אלגוריתמים נומריים ב DSP (במידה ויספיק הזמן)

4) מעבדי אותות 

 

יישומים

1) DSP בתקשורת ומודמים

2) עיבוד, דחיסה והבנה של דיבור

3) שימוש ב DSP לניבוי תנודות שוקי כספים

4) יישומים אחרים במידה ויספיק הזמן

 

 
 
 Workshop in Data-Centered Crowdsourcing 

ראו סילבוס ב http://slavanov.com/teaching/crowd1718a/

 
 
 Workshop in Software Models 

הסדנא מציעה פרויקטים הקשורים לשימוש במודלים בהנדסת תוכנה.

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

 

 
 
 Workshop in Information Security 
 
 
 Google Workshop 

 

This is a workshop focusing on Cloud and Web Development, using primarily - but not exclusively - Google tools and technologies.

These include Android (Google Phone), Chrome and Chrome OS, Google Maps, YouTube API, Google Visualization API, Google AppEngine, Social networks, Google TV and more.

 

Students will group in teams of 4 students. Each group will come up with a project for the semester.

Project will include designing and developing a live web system.

 

The course will include several frontal lectures going over the technologies, and the rest of the semester will include project reviews (initial project presentation, design and workplan review, several iterations of project demos and finally a complete project presentation).

Each group will also maintain a web page with project documentation and design documents.

 

מופיע גם באתר: https://sites.google.com/site/cloudweb15b/

 
 
 Machine Learning Based Algorithms in Structural Biology and Drug Design 
מבחינה אלגוריתמית/מתימטית הסדנה תעסוק בפיתוח תוכנה לפיתרון פאזלים תלת מימדיים, כשתחום האפליקציה הוא ביולוגיה מוליקולרית.

נעסוק במידול במרחב התלת-מימדי של קומפלקסים המורכבים ממספר רב של חלבונים, כאשר נתון מידע מדויק על החלבונים הבודדים, המשתתפים בקומפלקס ומידע ברזולוציה נמוכה על מבנה כל הקומפלקס.
 
מבחינה מתימטית הבעיה דומה לפיתרון פאזל תלת-מימדי, כאשר ידועות חתיכות הפאזל הבודדות ויש מידע "מטושטש" על המבנה של הפאזל כולו.
מכאן שהאלגוריתמים שנפתח יוכלו להיות מותאמים גם לפיתרון בעיות דומות בראיה ממוחשבת ובגרפיקה, אם כי אנו נתרכז בתחום האפליקציה של ייצוג תלת מימדי של חלבונים.
 
הסדנא מיועדת לתלמידי התכנית לביואינפורמטיקה ולתלמידי תכניות מדעי המחשב. אין צורך בידע ביולוגי מוקדם. עיקרי הידע הביולוגי הדרוש ודרך תרגומו למבנים גיאומטריים יינתנו במפגשים הראשונים של הסדנא.
 
צוות הסדנא יציג מספר פרויקטים לבחירה וניתן יהיה גם להציע פרויקט עצמאי לאישור הצוות.
לקראת אמצע הסמסטר כל קבוצה (של כ-3 איש) תגיש לאישורו של צוות הסדנא תכנית מפורטת של הפרויקט שהם מתכננים לבצע
הגשת הפרויקטים תהיה לקראת סוף הקיץ. שפת התכנות המועדפת היא פייתון, אך ניתן יהיה ליישם את הפרויקטים בשפות אחרות, כפוף לאישור.
 
 
 Workshop in Data Science 

הסדנא תתמקד בחילוץ מידע ותובנות מכמות גדולה מאוד של נתונים תוך שימוש בכלים סטטיסטיים ו\או באלגוריתמי למידה חישובית. הסטודנטים יידרשו (בקבוצות) לתיכון ולפיתוח מערכת גדולה שכזו, ולהציג את תוצאותיהם בכיתה.   

נבחנת האפשרות לשיתוף פעולה עם חברת microsoft במסגרת הסדנא.

 
 
 Workshop in Machine Learning Applications for Computer Graphics 

Course name: workshop in machine learning applications for computer graphics

סדנה ביישומי למידת מכונה לגרפיקה ממוחשבת

 

Course description:

In this workshop we will focus on the ground breaking method of generative adversarial networks (GAN). GANs are a class of deep learning architectures used to learn a deep representation of given data and synthesize new data.

GANs achieve state of the art results in many applications such as image synthesis, style transfer and image super-resolution.

The first two weeks of the workshop will include lectures on the basics of deep learning networks and GANs. Afterwards, each group of three students will present a paper to the class and work on a project. None of the necessary infrastructure is required of you as you will be working on google colab and aws.

 

 
 
 Workshop On Search Data Structures for High-Performance Databases 
 
 
 Seminar in Localization, Navigation, and Mapping 

הסמינר יציג מאמרים עכשיווים בתחום של איכון וניווט, כגון מאמרים על שיטות איכון בתוך בניינים, פתרון בעיות איכון GPS בדרכים יצירתיות (למקרים שבהם לא ניתן לבצע את כל המדידות שהאלגוריתמים המקוריים דורשים), וכדומה.

מומלץ לקחת את הקורס "מערכות ואלגוריתמים לאיכון, ניווט ומיפוי" בסמסטר א'; החומר שנלמד בקורס עוזר מאוד להבין מאמרים בתחום.

 

 
 
 Algorithmic Methods 
 
 
 Algorithms for Modeling, Fabrication and Printing of 3D Objects 

כללי:

הקורס יעסוק באספקטים החישוביים של מידול אובייקטים לצרכי ייצור בכלל, והדפסה תלת-מימדית בפרט. הקורס הינו קורס מתקדם הפתוח לסטודנטים לתארים גבוהים או למסיימי תואר ראשון. הקורס דורש ידע והבנה במקצועות האפליקטיביים של מדעי המחשב באופן כללי. המלצת קדם לקורס הינה "יסודות גרפיקה, עיבוד תמונה וראיה", קורס אשר יקנה יתרון למי שכבר ביצע אותו. הקורס יכלול הוראה פרונטלית כמחצית מהזמן, הצגת מאמרים בסגנון סמינר בשאר הזמן, ויסתיים בהצגת פרוייקט גמר.

נושאים:

בוגרי הקורס יכירו באופן כללי את הנושאים הדרושים לצורך פיתוח אלגוריתמים המקלים על תהליך המידול, או הפיתוח, של אובקייטים תלת-מימדיים אשר עתידים לייצור, כאשר לב הקורס הינו ייצוג ואופטימיזציית הגיאומטריה של האובייקט. 

הקורס יכלול הסבר שטחי על טכנולוגיות הדפסה תלת-מימדית, טכניקות של סימולציה פיזקלית ושל אופטימיזציה באופן כללי. לאחר מכן, דרך דוגמאות של מאמרים עדכניים, נראה כיצד ניתן להשתמש בשיטות אלו על מנת להקל על תהליך הפיתוח הנ"ל, להפוך חלקים ממנו לאוטומטיים, או לאפשר הקניית תכונות לאובייקטים שלא היו אפשריות קודם לכן. 

את דוגמאות אלו נראה בתחומים של שליטה על טווח ומסלולי התנועה והדיפורמציה של אובקייטים, שליטה ושיפור החוזק של אובייקטים וכך גם המראה שלהם. בנוסף, כמה דוגמאות יעסקו בתהליך ההדפסה עצמו, כאשר נראה איך שיטות דומות יכולות גם לשפר את זמן ואיכות ההדפסה.

תחומי ההתמקדות במהלך קורס ניתנים לשינוי ויהיו תלויים גם בהבעות ההתעניינות של הסטודנטים, אבל באופן כללי יעקבו אחרי התחומים המפורטים בספר: "Design, Representations, and Processing for Additive Manufacturing"

 
 
 Derandomization 1 

A first course in Derandomization

Randomness is extremely useful for developing fast and simple  algorithms. Derandomization often enables one to convert a randomized algorithm  into a deterministic one. In this course we will develop tools and  techniques for the design and analysis of efficient randomized algorithms and their derandomization. A tentative list of possible topics follows.

- A probabilistic algorithm for finding a maximal independent set in parallel, and its derandomization using pairwise independence.

- A probabilistic algorithm for finding a perfect matching in parallel. The identity testing problem.

- The Hardness vs. Randomness Paradigm

- The converse: Derandomization implies Hardness

We will use various tools, e.g. from: pairwise independence, eps-bias, k- wise and almost k-wise independence, expanders, extractors, error correcting codes and pseudo-random- generators.

 
 
 Foundations of Cryptography 
 
 
 Automatic Verification of Systems 

הקורס יעסוק באימות אוטומטי של מערכות חמרה ותכנה באמצעות בדיקת מודל (Model Checking).

נראה דרכים למידול מערכות ולתיאור תכונות (מפרטים) של מערכות באופן פורמלי ע"י נוסחאות בלוגיקה טמפורלית, נציג אלגוריתמי בדיקת מודל לבדיקה אוטומטית כי מערכת מקיימת מפרט נתון, נדון במגבלות של האלגוריתמים הללו ובדרכים להתמודד איתן. בפרט, נגדיר יחסי סדר ושקילויות בין מודלים, נציג טכניקות אבסטקרציה ועידון, אימות מודולרי, בדיקת מודל סמבולית מבוססת BDD ובדיקת מודל מבוססת SAT.

 
 
 Automata Logic and Games 

 

Course name:

 

Games, Logic and Automata

 

 

 

Course Syllabus

 

 

 

 

 

 

 

Lecturer:  Alex  Rabinovich

 

 

 

Credit:  3pt

 

 

 

Prerequisites: Logic for  CS, Computational Models.

 

 

 

Course Objectives:

 

In this course  we will study topics related to games, logic and automata and a rich interplay between them. These provide  the  mathematical foundations to  formal verification.

 

 

 

Automata on infinite words and trees serve as a computational model for reactive systems; Logics are  the basis of  specification formalisms and

 

games are a conceptual framework for understanding the interaction between

 

a system and its environment.

 

 

 

 

 

 

 

Course Syllabus:

 

Infinite  behavior of finite automata: closure properties, succinctness,

 

deteminization  algorithms.

 

 

 

Specification formalisms and their expressive power and succinctness properties: : Monadic second order logic, temporal  logics, algebraic formalisms.  

 

 

 

Decidability of monadic second-order logics over the naturals and over  the full binary tree. Reduction to finite automata, EF games, Shelah's compositional method.

 

 

 

Church Synthesis problem:   Infinite two-persons perfect information games.  Determinacy, computational and descriptive complexity of winning strategies.

 

 

 

 

 

Model Checking  Problem.  Algorithms for model-checking and their complexity.

 

 

 

 

 

 

 

 

 

 

 

 

 

Recommended reading:

 

D. Perrin and J. E. Pin. Infinite Words Automata, Semigroups, Logic and

 

Games. Pure and Applied Mathematics Vol 141 Elsevier, 2004.

 

 

 

W. Thomas Automata and Reactive systems. (draft of a book).

 

 

 

 

 

Grade:  80% home exam + 20% HW

  

 
 
 Advanced Topics in Multicore Architecture and Software Systems 

רישום לתלמידי תואר ראשון אפשרי רק באישור המרצה (לא דרך הבידינג).

דרישות קדם לקורס:

- מערכות הפעלה
- מבנה מחשבים

 

 
 
 Abstract Algebra in Theoretical Computer Science 

Theoretical computer scientists make an extensive use of elements from abstract algebra. From the design and analysis of algorithms and cryptographic protocols to the construction of desired combinatorial objects, the use of algebraic structures has repeatedly provided powerful and elegant solutions. Mastering the required mathematical background, however, requires isolating relevant parts from several courses in Mathematics or, alternatively, is done ad hoc.

This course provides a thorough introduction to abstract algebra, focusing on the useful elements required for the aforementioned use within computer science. In the first half of the course, we will study basic, frequently used, notions such as groups, rings, and finite fields. In the second part, we will consider more advanced notions from Commutative Algebra and Galois Theory. The math will be developed alongside applications in Theoretical Computer Science, Coding Theory, and Cryptography. We will take a bird's-eye view, focusing on the key notions and ideas while omitting some of the proofs. Some of the applications that will be discussed are:

​- Randomness mergers and the Kakeya Set problem

- Private Information Retrieval schemes

- Parvaresh–Vardy codes and the Guruswami-Umans-Vadhan expander graph​

 

For more information, see the course webpage at https://www.gilcohen.org/abstract-algebra-for-tcs

 

 
 
 Introduction to Algebraic-Geometric Codes 

קורס זה מהווה קורס מבוא לבנייה של קודים לתיקון שגיאות המתבססים על עקומים אלגבריים. מטרת הקורס היא לבנות בצורה יסודית ומעמיקה את המתמטיקה המרתקת שבבסיס חקר עקומים אלגבריים עד לנקודה בה ניתן להגדיר קודים אלגבריים-גאומטריים לתיקון שגיאות. הסטודנטים שיסיימו את הקורס יוכלו להשתמש בכלים המתמטיים שיפותחו מעבר לאפליקציה הספציפית לקודים. השימוש הנרחב בפולינומים בתאוריה של מדעי המחשב, קודים וקריפטוגרפיה מצביע על כך שהכלים המתמטים שיופתחו בקורס (המכלילים בצורה משמעותית כלים שימושיים הקשורים לפולינומים מעל שדות סופיים) יוכלו להוות כלי מחקר שימושי.

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

(1) עקומים אלגבריים - חלק א׳: עקומים, חוגי פונקציות, רזולטנט, נקודות ואידאליים מקסימיאליים, מורפיזמים, סינגולריות.

(2) הפן האלגברי - הסגור השלם, מכפלת אידאליים, חוגי נתר, חוגים מממד אחד, חוגי דדיקנד.

(3) עקומים אלגבריים - חלק ב׳: לוקליזציה וחוגים מקומיים, הקשר בין סינגולריות לסגור השלם, משפט הבסיס של הילברט.

(4) גאומטריה פרוייקטיבית - תחומי הערכה דיסקרטית, המישור הפרוייקטיבי ועקומים פרוייקטיבים.

(5) השימוש לקודים - מחלקים, משפט רימן, וקודים אלגבריים-גאומטריים לתיקון שגיאות.

בסמסטר העוקב יינתן קורס המשך לקורס מבוא זה בו נמשיך ונפתח בצורה יסודית כלים מרכזיים בחקר עקומים אלגבריים כמו משפט רימן-רוך, פירוק אידאלים בהרחבת חוגים, דיסקרמיננטים, פונקצית הזטא של עקומים אלגבריים, ובניות מפורשות של עקומים אלגבריים בעלי תכונות רצויות, וכן בניות מפורשות של קודים אלגבריים-גאומטריים לתיקון שגיאות.

 
 
 Seminar On pseudorandomness 
 
 
 Seminar on Algorithms for Deep Sequencing Data 

"טכניקות הדור הבא" בריצוף ד.נ.א. (Next Generation Sequencing ובקיצור NGS) יצרו מהפיכה שהורידה את עלויות הריצוף בפקטור של 10,000 תוך עשור. ניסוי אופייני מייצר 10 – 100 מיליון רצפי ד.נ.א. (אלפא-ביתא של ארבע אותיות) באורך 100-200 כל אחד, המהווים מקטעים מגנום המטרה עם שגיאות. היעילות והמחיר הזול הפכו את NGS לכלי-על המשמש למאות סוגים של מדידות ביולוגיות ורפואיות.  על מנת להתמודד עם המסות האדירות, נדרשים אלגוריתמים חזקים ומהירים וקהילת הביואינפורמטיקה בעולם עוסקת בנושא במרץ רב.

בסמינר נלמד כמה מהאלגוריתמים המרכזיים שפותחו בשנים האחרונות לשם ניתוח נתוני NGS. ביניהם: גרף de Bruijn, minimizers, universal hitting sets, Minhash ויישומיהם.

הסמינר אינו דורש ידע מוקדם בביולוגיה. כל הידע הנדרש יוצג בפגישות הראשונות.

הסמינר פתוח לתלמידי תואר שני ולתלמידי תואר ראשון שסיימו בהצלחה את הקורס "אלגוריתמים".

 
 
 Topics in Software and Systems Modeling 

בקורס זה אנחנו מתעניינים בהגדרה של שפות מידול (modeling languages) ובשימוש במודלים (models) בהנדסת תוכנה.   נתמקד בהגדרה ובחקירה של שפות מידול, ביחסים בין מודלים, ובשיטות פורמליות מתאימות שנעזרות בניתוח אוטומטי (SAT solvers, BDD-based symbolic algorithms) כדי לספק למהנדסים הפשטות (abstractions) וכלים להתמודדות עם האתגרים של התכנון, הבניה, ההרצה, הבדיקה, התחזוקה, והאבולוציה של מערכות תוכנה.

נתמקד באחד או יותר מהנושאים הבאים:

Reactive synthesis
Specification mining and model inference

Combinatorial testing

Temporal logics

Alloy

UML
  

הקורס מיועד לתלמידי תואר שני ושלישי במדעי המחשב.
קורסים קשורים ומומלצים: מודלים חישוביים, לוגיקה, אימות תוכנה וחומרה, בדיקות תוכנה, סמינר מחקר בתוכנה (0368-5245).

 
 
 Research pearls in theoretical computer science 2 

The course in intended as a general introductory to Theory of CS

for students who consider research in the field

 

The course takes the following format

On the usual aspect,  it will cover many of the subjects covered

in these lecture notes

https://sites.google.com/a/mail.tau.ac.il/codes16a/home

 

In addition, the course would serve as preparation for the Theory Seminar

held immediately afterwards, so as to make it more accessible to students

 

_(he topics we will cover include (among others

Analysis of Boolean functions and their applications

- PCP and Hardness of approximation 

- The unique-games conjecture

- Applications to Cryptography

 
 
 Distributed Computation 

הסמסטר נלמד שני נושאים עיקריים:  הקדמה לחישוב מבוזר, ו-Blockchains.  בחישוב מבוזר נלמד את יסודות האלגוריתמים המבוזרים במודל החלפת הודעות (מעל גבי רשת תיקשורת)  ובמודל הזיכרון המשותף. כמו כן נלמד את הנושאים בחישוב מבוזר אשר מהווים את הבסיס להבנה בנייה ותכנון Blockchains כמו Replicated State Machine ו-Consensus Algorithms, Fault Tolerant Byzantine Agreement. בכלים וההיבטים הקריפטגרפיים של Blockchains נעשה שימוש במידת הצורך ונבין אותם כקופסא שחורה. בהמשך נלמד מספר מערכות Blockchain שוב בעיקר nההיבטים של החישוב המבוזר.

חישוב מבוזר: שיתוף פעולה ותאום אלוגריתמי בין מעבדים ברשת תקשורת על מנת לפתור בעיות גלובאליות משותפות. כל מעבד בחישוב מקבל רק חלק מהקלט ומייצר רק חלק מהפלט כך שאיחוד הפלטים הוא פלט חוקי של החישוב המבוזר; במודל העיקרי בו נעסוק, המעבדים מתקשרים ביניהם אך ורק ע"י העברת הודעות בקוי התקשורת. כמו כן נעסוק במודל של זכרון משותף; יידונו רשתות סינכרוניות ואסינכרוניות ומספר רב של בעיות; הפצת הודעה, בחירת מנהיג, שבירת סימטריה, בניית עץ פורש, פיזור ושליטה במשאבים. כמו כן יידונו בעיות מיוחדות של סינכרון, וצילום מצב גלובלי.

 

 
 
 Advanced Topics in Machine Learning-Algorithmic Game Theory 

הקןרס יתרכז בנושאים של קבלת החלטות תחת חוסר ודאות.

נכסה נושאים הקשורים ל- online learning, experts, multi-arm bandits

כמו כן נושאים שקשורים ללמידה במכרזים תוך דגש על סיבוכיות הדגימה.

 
 
 Program Analysis and Verification 
Operational semantics (How do we formally define the meaning of programs).
Program logics (Classical and modern approaches for manual verification of computer programs).
Abstract interpretation (Theoretical foundation of automatic compile-time
analysis, aka static analysis, For example, determining during compile time whether x= y / z is always 1 or that at this program point z is not zero.)
Miscellaneous verification techniques: MC (Model
checking), SAT (Satisfiability) and SMT (Satisfiability
Modulo Theory).
 
The course will have ~4 exercises and a final project (that can be done in pairs.)
Prerequisite: Computational models (0368-2200)
 
 
 Algorithmic Game Theory 

Syllabus (tentative)

  • Introduction: games, mechanism design, inefficiency of equilibrium and equilibrium computation
  • Nash equilibrium and Nash’s theorem
  • Zero-sum games: normal form and extensive form, minmax theorem, Yao’s principle
  • Congestion games and potential games, pure NE existence and computation, best-response dynamics
  • Inefficiency of equilibria: price of anarchy, price of stability, smoothness framework (extension to correlated equilibrium and regret minimization)
  • Mechanism design basics: single-item auctions, Myerson’s lemma
  • Algorithmic mechanism design: Multi-unit auctions: computation and communication
  • VCG mechanisms
  • Market models, equilibium, Welfare theorems, computational aspects

Course Requirements

  • Class attendance is mandatory.
  • Scribe notes (latex templatelatex tutorial)
  • Problem sets: 2-3 problem sets will be given during the semeter. You should submit them in pairs.
  • Final exam.
 
 
 Deep Learning 

**הרשמה ידנית -- קישור באתר המרצה**

הקורס יערך במתכונת שונה מאוד מהקורסים המוכרים לכם מהאוניברסיטה, בצורה של כיתת אמן.

מוטיבציה: אין נושא במדעי המחשב עם יותר חומר חופשי ומצויין מאשר למידה עמוקה. למשל, במהלך שלושת השבועות הראשונים, תדרשו להשלים בעצמכם את החומר של מרבית הקורס הזה: http://cs231n.stanford.edu/syllabus.html. בנוסף, התחום מאוד דינאמי ומתפתח יותר מהר מכל תחום אחר במדעים מדוייקים והנדסה, ולכן חשובה מסגרת פתוחה.

כיצד יערכו השיעורים: במתכונת של דיון ודו שיח סוקרטי (השאלות ישאלו בשני הכיוונים ובצורה נעימה) סביב חומר הקריאה אותו תדרשו לדעת לפני השיעורים, סביב הפרוייקטים של הקבוצה שלכם, וסביב נושאים אותם יבחרו להעלות הסטודנטים. מדי פעם תוצג מצגת כדי לקדם את הדיון.

מחויבויות הסטודנטים: (1) נוכחות חובה. (2) לקרוא את חומר הקריאה לפני השיעור ולגלות בקיאות בחומר (יופעלו סנקציות). (3) תרגילים קבוצתיים (כ-3 סטודנטים בקבוצה). התרגילים הינם מחקריים ומאתגרים ולפי תחומי עניין.

הקורס מחייב שימוש ב-gpu. יש כיום שני דרכים עיקריות להשיג גישה -- א. דרך המנחה שלכם בתואר. ב. בתשלום לשרותי ענן.
לצערי, אין באפשרותנו כיום לתמוך בסטודנטים באמצעות משאבי gpus. אנחנו מנסים להשיג מן הגורן ומן היקב, אבל כלל לא בטוח שנצליח.

קבלה: באישור המרצה. הקורס מיועד לתלמידי מחקר עם עניין אמיתי בלמידה עמוקה ורקע כלשהו בלמידה חישובית. תנתן עדיפות למדעי המחשב (חובה תקנונית) ותתאפשר השתתפות של סטודנטים מצטיינים מתואר ראשון באישור המזכירות.

ציון: לפי הפרוייקטים, השתתפות, תרומה אמיתית לדיון, בקיאות בחומר כפי שמתגלה בשיעורים. לפחות פרוייקט אחד ראוי לפרסום במקום נכבד נדרש על מנת לקבל ציון מעל 92. ציון בין 85-92 ידרוש פרוייקט שהוא לפחות מימוש מלא כולל ניסוי מקיף של מאמר מורכב מספיק שכבר פורסם.

נושאים: רשתות עמוקות בראייה ממוחשבת. רשתות עמוקות בNLP. רשתות עמוקות בSPEECH. למידה לא מפוקחת למשל עם GANs. מודלים של attention ורשתות זכרון.

מידע נוסף: הframework של הקורס הינו pytorch

צוות הקורס:
ליאור וולף
אליה נחמני

 
 
 Communication and Information Complexity 

סיבוכיות תקשורת עוסקת בשאלה: כמה ביטים של תקשורת נדרשים כדי לבצע חישוב על קלט שמחולק בין שני מחשבים שונים? למשל, אם שני עותקים של קובץ שמורים על מחשבים שונים, ואנו רוצים לוודא שהעותקים זהים, כמה ביטים של תקשורת נדרשים -- האם צריך לשלוח את הקובץ כולו או שניתן להסתפק בפחות תקשורת?

סיבוכיות תקשורת מהווה כלי שימושי ביותר להוכחת חסמים תחתונים בתאוריה של מדעי המחשב, עם שימושים בתחומים מגוונים הכוללים סיבוכיות מעגלים (circuit complexity), מבני נתונים, חישוב מבוזר, אלגוריתמים תת-לינאריים ועוד. כדי להוכיח חסמים תחתונים על סיבוכיות התקשורת של פונקציות שונות קיימות שיטות הסתברותיות, קומבינטוריות ואלגבריות, אותן נסקור בקורס. כמו-כן נלמד כיצד מודדים את כמות ה*אינפורמציה* שעוברת בפרוטוקול תקשורת נתון, שיטות להוכחת חסמים תחתונים על כמות זו, וקשרים בין אינפורמציה ותקשורת.

הקורס יועבר באנגלית הסמסטר.

 

דרישות קדם:

 

  • סיבוכיות (אפשר תוך-כדי באישור המרצה)

 

דרישות הקורס:

 

  • תרגילי בית דו-שבועיים

  • בחינה

 
 
 A seminar on derandomization 

0368-4622: Seminar in Derandomization Syllabus

Syllabus

 

Below is a tentative list of papers for the seminar. There are more papers then meetings, and you can choose those papers that you like most (or are interested in most). Some papers can be taken in pairs.

 

Hardness vs. Randomness

1. The NW generator [NW94].


2. List decoding RS codes [Sud97, GRS15].


3. Worst-case to average case reduction for PSPACE [STV01].

 

Average-case Hardness

4. Background and Definitions [BT06a, BT06b].


5. Negative results for Black-box worst-case to average-case reductions for NP [BT06a, BT06b].

6. Worst-case to average-case reduction for MINKT [Hir18].


7. Impagliazz’o five worlds [Imp95].


8. The easy witness method [IKW02].


9. Hardness amplification within NP [O’D04].

 

Extractors, coding, PRG

 

10. Trevisan’s extractor [Tre01].


11. The SU extractor [SU05].


12. The Umans PRG [Uma02].


13. The beautiful curve mergers [DW11].

14. Subspace Evasive Sets [DL12].

15. Arithmetic Hardness vs. Randomness [KI04, Section 7].


16. A Welch-Berlekamp Like Algorithm for Decoding Gabidulin Codes, [Loi06].

 

 

Space-bounded PRG

17. Pseudorandom Generators from Polarizing Random Walks [CHHL18].

18. Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates [CHLT18].

19. Bounding the Fourier spectrum of small width branching programs [CHRT18].

 

Miscellaneous

20. Constructive proofs of concentration bounds [IK10].

References

[BT06a] Andrej Bogdanov and Luca Trevisan. Average-case complexity. Foundations and Trends in Theoretical Computer Science, 2(1):1–106, 2006.

[BT06b] Andrej Bogdanov and Luca Trevisan. Average-case complexity. arXiv preprint cs/0606037, 2006.

[CHHL18] Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudo- random generators from polarizing random walks. In LIPIcs-Leibniz International Pro- ceedings in Informatics, volume 102. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[CHLT18] EshanChattopadhyay,PooyaHatami,ShacharLovett,andAvishayTal.Pseudorandom generators from the second fourier level and applications to ac0 with parity gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[CHRT18] Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 363–375. ACM, 2018.

[DL12] Zeev Dvir and Shachar Lovett. Subspace evasive sets. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 351–358. ACM, 2012.

[DW11] Zeev Dvir and Avi Wigderson. Kakeya sets, new mergers, and old extractors. SIAM Journal on Computing, 40(3):778–792, 2011.

[GRS15] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential Coding Theory. 2015. Available at http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/ book.

[Hir18] Shuichi Hirahara. Non-black-box worst-case to average-case reductions within np. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 247–258. IEEE, 2018.

[IK10] Russell Impagliazzo and Valentine Kabanets. Constructive proofs of concentration bounds. In Approximation, Randomization, and Combinatorial Optimization. Algo- rithms and Techniques, pages 617–631. Springer, 2010.

[IKW02] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672–694, 2002.

[Imp95] Russell Impagliazzo. A personal view of average-case complexity. In Structure in Com- plexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE, pages 134–147. IEEE, 1995.

[KI04] Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1–46, 2004.

[Loi06] Pierre Loidreau. A welch–berlekamp like algorithm for decoding gabidulin codes. In Coding and cryptography, pages 36–45. Springer, 2006.

[NW94] Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of computer and System Sciences, 49(2):149–167, 1994.

[O’D04] Ryan O’Donnell. Hardness amplification within np. Journal of Computer and System Sciences, 69(1):68–94, 2004.

[STV01] Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62(2):236–266, 2001.

[SU05] Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM (JACM), 52(2):172–216, 2005.

[Sud97] Madhu Sudan. Decoding of reed solomon codes beyond the error-correction bound. Journal of complexity, 13(1):180–193, 1997.

[Tre01] Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM, 48(4):860–879, 2001.

[Uma02] Christopher Umans. Pseudo-random generators for all hardnesses. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC ’02, pages 627–634, New York, NY, USA, 2002. ACM.

 
 
 Avanced Topics in Computational Genomics  
 
 
 Final Examination 
 
 
 Thesis