COMPUTATIONAL PARADIGMS FOR PROBLEM SOLVING

Pasquale FOGGIA COMPUTATIONAL PARADIGMS FOR PROBLEM SOLVING

8802000005
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
P.H.D. COURSE
INFORMATION ENGINEERING
2020/2021

OBBLIGATORIO
YEAR OF COURSE 1
YEAR OF DIDACTIC SYSTEM 2020
PRIMO SEMESTRE
CFUHOURSACTIVITY
318LESSONS
Objectives
INTRODUCTION
A COMPUTATIONAL PARADIGM IS A WAY OF MODELING THE EXECUTION OF A PROGRAM WRITTEN IN A PARTICULAR PROGRAMMING LANGUAGE, AND HAS IMPLICATIONS ON HOW THE PROGRAMMING LANGUAGE CAN BE USED TO SOLVE PROGRAMMING PROBLEMS. WHILE THE STUDENTS HAVE BEEN WIDELY EXPOSED TO IMPERATIVE COMPUTATIONAL PARADIGMS (USED IN PROCEDURAL PROGRAMMING LANGUAGES LIKE C AND OBJECT-ORIENTED PROGRAMMING LANGUAGES LIKE JAVA), THE MODULE IS AIMED AT INTRODUCING DECLARATIVE PARADIGMS (MAINLY LOGIC AND FUNCTIONAL PROGRAMMING), TOGETHER WITH THE BASIC TECHNIQUES FOR WRITING AN INTERPRETER FOR A PROGRAMMING LANGUAGE.

KNOWLEDGE AND UNDERSTANDING
AT THE OF THE MODULE, STUDENTS WILL UNDERSTAND:
• THE DIFFERENCES AMONG THE MAIN COMPUTATIONAL PARADIGMS
• THE FUNDAMENTAL ASPECTS OF THE LOGIC COMPUTATIONAL PARADIGM
• THE FUNDAMENTAL ASPECTS OF THE FUNCTIONAL COMPUTATIONAL PARADIGM
• THE BASIC ASPECTS IN THE SYNTAX ANALYSIS AND INTERPRETATION OF A PROGRAMMING LANGUAGE

PRACTICAL SKILLS
AT THE OF THE MODULE, STUDENTS WILL BE ABLE TO:
• DESIGN THE SOLUTION TO A PROBLEM USING THE LOGIC PARADIGM
• DESIGN THE SOLUTION TO A PROBLEM USING THE FUNCTIONAL PARADIGM
• WRITE AN INTERPRETER FOR A SIMPLE PROGRAMMING LANGUAGE.
Prerequisites
THE STUDENT SHOULD BE FAMILIAR WITH PROGRAMMING IN AN OBJECT-ORIENTED LANGUAGE LIKE JAVA, AND WITH THE FUNDAMENTAL DATA STRUCTURES. ALSO, A BASIC KNOWLEDGE OF FIRST-ORDER LOGIC IS RECOMMENDED.
Contents
INTRODUCTION: WHAT IS A COMPUTATIONAL PARADIGM. THE IMPERATIVE MODEL OF EXECUTION AND ITS LIMITATIONS. SYNTAX OF A PROGRAMMING LANGUAGE. LEXICAL ANALYSIS. GRAMMARS AND PARSING. ABSTRACT SYNTAX TREES. A RECURSIVE DESCENT PARSER. (LECTURES: 3 HOURS)

INTERPRETATION OF A PROGRAM: EXPRESSIONS AND SIMPLE STATEMENTS. THE MEMORY ABSTRACTION: VARIABLES AND THE ENVIRONMENT. SUBPROGRAM DEFINITION AND EXECUTION. PARAMETER PASSING. LOCAL VARIABLES. LEXICAL AND DYNAMIC SCOPING. (LECTURES. 3 HOURS)

THE LOGIC PARADIGM: EXECUTION AS THEOREM-PROVING. THE PROLOG PROGRAMMING LANGUAGE. FACTS. QUERIES. LOGICAL VARIABLES AND EXISTENTIAL QUANTIFICATION. RULES AND UNIVERSAL QUANTIFICATION. UNIFICATION. LISTS AND RECURSIVE ALGORITHMS ON LISTS. SYMBOLIC EXPRESSIONS. MANIPULATION OF SYMBOLIC EXPRESSIONS: THE SYMBOLIC DERIVATIVE. EXTRA-LOGIC OPERATORS: NOT AND CUT. (LECTURES: 6 HOURS)

THE FUNCTIONAL PARADIGM: EXECUTION AS APPLICATION OF PURE FUNCTIONS. RECURSION AND ITERATION. DYNAMIC CREATION OF FUNCTIONS. CLOSURES. HIGH-ORDER FUNCTIONS. FUNCTIONAL DATA STRUCTURES: LISTS AND TREES. DELAYED EVALUATION AND STREAMS. REAL WORLD APPLICATIONS OF FUNCTIONAL PROGRAMMING. (LECTURES: 6 HOURS)
Teaching Methods
LECTURES SUPPORTED BY PROBLEM-SOLVING TUTORIALS WITH PRACTICAL ASPECTS ALSO COVERED DURING LECTURES.

IN ORDER TO PARTICIPATE TO THE FINAL ASSESSMENT AND TO GAIN THE CREDITS CORRESPONDING TO THE MODULE, THE STUDENT MUST HAVE ATTENDED AT LEAST 65% OF THE HOURS OF ASSISTED TEACHING ACTIVITIES.
Verification of learning
THE EXAM CONSISTS OF A WRITTEN TEST. THE TEST INCLUDES BOTH METHODOLOGICAL QUESTIONS AND SIMPLE PROGRAMMING PROBLEMS.

POSSIBLE GRADES ARE, IN DESCENDING ORDER: OTTIMO (EXCELLENT), BUONO (GOOD), DISCRETE (FAIR), SUFFICIENTE (PASS), INSUFFICIENTE (FAIL). STUDENTS WHO GET AN INSUFFICIENTE (FAIL) MARK OR REJECT THE GIVEN MARK CAN REPEAT THE EXAM ONLY ONCE AFTER AT LEAST 30 DAYS.
Texts
H. ABELSON AND G. J. SUSSMAN WITH J. SUSSMAN, “STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS”, MIT PRESS, 1996.

L. STERLING AND E. SHAPIRO, “THE ART OF PROLOG: ADVANCED PROGRAMMING TECHNIQUES”, MIT PRESS, 1994.

SOFTWARE TOOLS AND ONLINE TUTORIALS PROVIDED DURING THE COURSE
More Information
TEACHING LANGUAGE IS ENGLISH.
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-05-23]