Difference between revisions of "BSc:PhilosophyI"
Jump to navigation
Jump to search
m (M.petrishchev moved page BSc:PhilosophyI.F21 to BSc:PhilosophyI) |
|||
| (34 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
| + | [https://eduwiki.innopolis.university/index.php/BSc:Logic_and_Discrete_Mathematics Logic and Discrete Mathematics] |
||
| − | = Philosophy 1: Logic and Discrete Mathematic = |
||
| − | |||
| − | * <span>'''Course name:'''</span> Philosophy 1: Logic and Discrete Mathematic |
||
| − | * <span>'''Course number:'''</span> n/a |
||
| − | * <span>'''Subject area:'''</span> n/a |
||
| − | |||
| − | == Course characteristics == |
||
| − | This course consists of two distinct but overlapping parts: i. Logic; and ii. Discrete Mathematics. |
||
| − | |||
| − | The first part of the course is an introduction to formal symbolic logic. Philosopher John Locke once wrote that ``logic is the anatomy of thought.'' This part of the course will teach |
||
| − | students to analyse and evaluate arguments using the formal techniques of modern symbolic logic. |
||
| − | |||
| − | The second part of the is designed for students to teach them basic notions of graph theory, discrete optimization and dynamic programming. This part will give practical experience with basic algorithms in discrete mathematics. |
||
| − | |||
| − | |||
| − | === Key concepts of the class === |
||
| − | |||
| − | *Deductive Reasoning |
||
| − | *Inductive Reasoning |
||
| − | *Categorical Logic |
||
| − | *Propositional Logic |
||
| − | *Predicate Logic |
||
| − | *Basic elements of Graph Theory |
||
| − | *Planar Graphs |
||
| − | *Algorithms on Graphs |
||
| − | |||
| − | |||
| − | === What is the purpose of this course? === |
||
| − | |||
| − | The first part of the course (on Logic) sets students upon a path of finely honed logical skills essential for life in the modern world. This part of the course is thus specifically designed to improve writing, thinking and oral presentation skills that are applicable to all areas of academic study and relevant to working life. |
||
| − | |||
| − | The Discrete Math part of the course introduces students to the basic concepts of structuring algorithms through graph theory. This gives students the skills of deep algorithmic thinking. Thus, the successful completion of the course by students will give them the skills for further deep mastering of computer science courses. |
||
| − | |||
| − | |||
| − | === Course Objectives Based on Bloom’s Taxonomy === |
||
| − | |||
| − | === What should a student remember at the end of the course? === |
||
| − | |||
| − | *how to use Venn diagrams |
||
| − | *how to calculate truth values |
||
| − | *the formal structures of some arguments |
||
| − | *the difference between deduction and induction |
||
| − | *how to build spanning trees |
||
| − | *how to find Euler tour and Hamilton path |
||
| − | *how to use Dijkstra’s algorithm |
||
| − | *how to solve maximum flow problem |
||
| − | |||
| − | |||
| − | === What should a student be able to understand at the end of the course? === |
||
| − | |||
| − | By the end of the course, the students should be able to understand: |
||
| − | |||
| − | *what is categorical logic |
||
| − | *what is propositional logic |
||
| − | *what is predicate logic |
||
| − | *what is the difference between deduction and induction |
||
| − | *what is trees and spanning trees |
||
| − | *what is Euler and Hamilton graphs |
||
| − | *what is planar graphs |
||
| − | *Dijkstra’s algorithm |
||
| − | |||
| − | === What should a student be able to apply at the end of the course? === |
||
| − | |||
| − | By the end of the course, the students should be able to apply the content of this course in all areas of their academic study but also in their working life, with special reference to the following disciplines: |
||
| − | |||
| − | |||
| − | *computer science |
||
| − | *engineering |
||
| − | *robotics |
||
| − | |||
| − | === Course evaluation === |
||
| − | |||
| − | |||
| − | {| |
||
| − | |+ Course grade breakdown |
||
| − | ! |
||
| − | ! |
||
| − | !align="center"| '''Proposed points''' |
||
| − | |- |
||
| − | | Final Exam (Written, Math) |
||
| − | | 40 |
||
| − | |align="center"| 40 |
||
| − | |- |
||
| − | | Mid Term (Written, Logic) |
||
| − | | 40 |
||
| − | |align="center"| 40 |
||
| − | |- |
||
| − | | Participation/Attendance |
||
| − | | 20 |
||
| − | |align="center"| 20 |
||
| − | |} |
||
| − | |||
| − | If necessary, please indicate freely your course’s features in terms of students’ performance assessment. |
||
| − | |||
| − | === Final Exam (Written, Math): === |
||
| − | |||
| − | The final exam will consist of theoretical and practical questions. The exam will be 90 minutes long. |
||
| − | |||
| − | === Mid Term (Written, Logic): === |
||
| − | |||
| − | The midterm exam will consist of quizzes and various exercises (such as open theoretical questions, multiple choices, and true/false questions). The Mid-Term will be held in class on week 8. The exam will last 75 minutes. |
||
| − | |||
| − | === Participation/Attendance: === |
||
| − | |||
| − | Weekly exercises (hereby reports) must be uploaded on moodle the day after the lab sessions are over. Although reports are not marked, they directly count towards participation. Failure to submit reports will incur in a penalty of the course mark, which will be proportional to the number of reports missing. |
||
| − | |||
| − | '''Overall score:''' 100 points (100%). |
||
| − | |||
| − | === Grades range === |
||
| − | |||
| − | {| |
||
| − | |+ Course grading range |
||
| − | ! |
||
| − | ! |
||
| − | !align="center"| '''Proposed range''' |
||
| − | |- |
||
| − | | A. Excellent |
||
| − | | 85-100 |
||
| − | |align="center"| 85-100 |
||
| − | |- |
||
| − | | B. Good |
||
| − | | 75-84 |
||
| − | |align="center"| 75-84 |
||
| − | |- |
||
| − | | C. Satisfactory |
||
| − | | 60-75 |
||
| − | |align="center"| 60-75 |
||
| − | |- |
||
| − | | D. Poor |
||
| − | | 0-59 |
||
| − | |align="center"| 0-59 |
||
| − | |} |
||
| − | |||
| − | If necessary, please indicate freely your course’s grading features: The semester starts with the default range as proposed, but it may change slightly (usually reduced) depending on how the semester progresses. |
||
| − | |||
| − | === Resources and reference material === |
||
| − | |||
| − | Textbook: |
||
| − | |||
| − | ● Hurley, P. J. (2014). ''<span>A Concise Introduction to Logic. Wadsworth Pub Co.''<span> |
||
| − | ● Priest, G. (2017). ''<span>Logic: A very short introduction. Oxford, UK: Oxford University Press.''<span> |
||
| − | ● Lehman, E., Leighton, F. T., Meyer, A. R. (2017). ''<span>Mathematics for Computer Science. Massachusetts Institute of Technology Press.''<span> |
||
| − | |||
| − | Electronic copies of these books will be available on Moodle for download. All the materials for the course will be uploaded by the Professors on Moodle in due time. Please note: The lectures will be highly interactive and the students may be interrogated during the lectures, sometimes via kahoots (this approach is known as flipped learning). |
||
| − | |||
| − | * Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffrey D. Ullman. ''<span>Compilers. Principles, Techniques, & Tools, Second Edition, Addison-Wesley, 2007, ISBN 0-321-48681-1.</span>'' |
||
| − | * N. Wirth, ''<span>Compiler Construction, Addison-Wesley, 1996, ISBN 0-201-40353-6</span>'' |
||
| − | * http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf, 2005 |
||
| − | |||
| − | == Course Sections == |
||
| − | |||
| − | The main sections of the course and approximate hour distribution between them is as follows: |
||
| − | |||
| − | {| |
||
| − | |+ Course Sections |
||
| − | !align="center"| '''Section''' |
||
| − | ! '''Section Title''' |
||
| − | !align="center"| '''Lecture Hours''' |
||
| − | !align="center"| '''Seminars (labs)''' |
||
| − | !align="center"| '''Self-study''' |
||
| − | !align="center"| '''Knowledge evaluation''' |
||
| − | |- |
||
| − | |align="center"| 1 |
||
| − | | Introduction to compilers and compiler construction |
||
| − | |align="center"| 12 |
||
| − | |align="center"| 6 |
||
| − | |align="center"| 12 |
||
| − | |align="center"| 2 |
||
| − | |- |
||
| − | |align="center"| 2 |
||
| − | | Lexical, syntax and semantic analyses |
||
| − | |align="center"| 8 |
||
| − | |align="center"| 4 |
||
| − | |align="center"| 8 |
||
| − | |align="center"| 1 |
||
| − | |- |
||
| − | |align="center"| 3 |
||
| − | | Code generation, optimization and virtual machines |
||
| − | |align="center"| 8 |
||
| − | |align="center"| 4 |
||
| − | |align="center"| 8 |
||
| − | |align="center"| 1 |
||
| − | |- |
||
| − | |align="center"| 4 |
||
| − | | Project presentation |
||
| − | |align="center"| |
||
| − | |align="center"| |
||
| − | |align="center"| |
||
| − | |align="center"| 2 |
||
| − | |} |
||
| − | |||
| − | === Section 1 === |
||
| − | |||
| − | === Section title: === |
||
| − | |||
| − | Introduction to compilers and compiler construction |
||
| − | |||
| − | === Topics covered in this section: === |
||
| − | |||
| − | * Basic notions: source and target languages, target architecture, compilation phases. |
||
| − | * The history of languages and compiler development. Typical compiler examples. |
||
| − | * Compilation & interpretation. Virtual machines, JIT & AOT technologies. Hybrid modes. |
||
| − | |||
| − | === What forms of evaluation were used to test students’ performance in this section? === |
||
| − | |||
| − | <div class="tabular"> |
||
| − | |||
| − | <span>|a|c|</span> & '''Yes/No'''<br /> |
||
| − | Development of individual parts of software product code & 1<br /> |
||
| − | Homework and group projects & 1<br /> |
||
| − | Midterm evaluation & 0<br /> |
||
| − | Testing (written or computer based) & 0<br /> |
||
| − | Reports & 0<br /> |
||
| − | Essays & 0<br /> |
||
| − | Oral polls & 1<br /> |
||
| − | Discussions & 1<br /> |
||
| − | |||
| − | |||
| − | |||
| − | </div> |
||
| − | === Typical questions for ongoing performance evaluation within this section === |
||
| − | |||
| − | # What is compilation process? |
||
| − | # What’s the difference between compiler and interpreter? |
||
| − | |||
| − | === Typical questions for seminar classes (labs) within this section === |
||
| − | |||
| − | # How to compile a program? |
||
| − | # How to run a program? |
||
| − | # How to debug a program? |
||
| − | |||
| − | === Test questions for final assessment in this section === |
||
| − | |||
| − | # What are significant phases of a compilation process? |
||
| − | # Why do we need optimization phase? |
||
| − | # What’s the difference between syntax and semantic analyses? |
||
| − | |||
| − | === Section 2 === |
||
| − | |||
| − | === Section title: === |
||
| − | |||
| − | Lexical, syntax and semantic analyses |
||
| − | |||
| − | === Topics covered in this section: === |
||
| − | |||
| − | * Compilation pipeline & compilation data structures |
||
| − | * Lexical analysis and deterministic state automata |
||
| − | * Bottom-up and top-down parsing |
||
| − | * Principles of semantic analysis |
||
| − | |||
| − | === What forms of evaluation were used to test students’ performance in this section? === |
||
| − | |||
| − | <div class="tabular"> |
||
| − | |||
| − | <span>|a|c|</span> & '''Yes/No'''<br /> |
||
| − | Development of individual parts of software product code & 1<br /> |
||
| − | Homework and group projects & 1<br /> |
||
| − | Midterm evaluation & 0<br /> |
||
| − | Testing (written or computer based) & 0<br /> |
||
| − | Reports & 1<br /> |
||
| − | Essays & 0<br /> |
||
| − | Oral polls & 0<br /> |
||
| − | Discussions & 1<br /> |
||
| − | |||
| − | |||
| − | |||
| − | </div> |
||
| − | === Typical questions for ongoing performance evaluation within this section === |
||
| − | |||
| − | # Abstract syntax tree & symbol tables: what is it for and how create and manage them? |
||
| − | # How to organize communication between compilation phases? |
||
| − | # What are basic differences between bottom-up and top-down parsing? |
||
| − | |||
| − | === Typical questions for seminar classes (labs) within this section === |
||
| − | |||
| − | # How to implement a hash function for a symbol table? |
||
| − | # How to write a grammar for an expression using YACC/Bison tool? |
||
| − | |||
| − | === Test questions for final assessment in this section === |
||
| − | |||
| − | # Characterize the principles of top-down and bottom-up parsing. |
||
| − | # Explain how a symbol table can be implemented. |
||
| − | # AST: is it a tree or a graph? What’s about semantic attributes in an AST? |
||
| − | |||
| − | === Section 3 === |
||
| − | |||
| − | === Section title: === |
||
| − | |||
| − | Code generation, optimization and virtual machines |
||
| − | |||
| − | === Topics covered in this section: === |
||
| − | |||
| − | * Low-level code generation: machine instructions, assembly language |
||
| − | * Virtual machines’ architecture and their byte codes. |
||
| − | * The notion of language projections. |
||
| − | * Introduction to optimization techniques. |
||
| − | |||
| − | === What forms of evaluation were used to test students’ performance in this section? === |
||
| − | |||
| − | <div class="tabular"> |
||
| − | |||
| − | <span>|a|c|</span> & '''Yes/No'''<br /> |
||
| − | Development of individual parts of software product code & 1<br /> |
||
| − | Homework and group projects & 1<br /> |
||
| − | Midterm evaluation & 0<br /> |
||
| − | Testing (written or computer based) & 0<br /> |
||
| − | Reports & 0<br /> |
||
| − | Essays & 0<br /> |
||
| − | Oral polls & 0<br /> |
||
| − | Discussions & 0<br /> |
||
| − | |||
| − | |||
| − | |||
| − | </div> |
||
| − | === Typical questions for ongoing performance evaluation within this section === |
||
| − | |||
| − | # What’s the difference between assembly and machine instructions? |
||
| − | # What’s the similarities and differences between real target platforms and virtual machines? |
||
| − | # Explain some of widely used approaches for optimizing program source code? How these approaches can be implemented in a compiler? |
||
| − | |||
| − | === Typical questions for seminar classes (labs) within this section === |
||
| − | |||
| − | # Explain the idea behind the notion of control flow graph. |
||
| − | # What is “basic block” in CFG and what is it for? |
||
| − | |||
| − | === Test questions for final assessment in this section === |
||
| − | |||
| − | # Give some simple examples of language-code projections. |
||
| − | # How the object code for an expression can be optimized? |
||
| − | # How to avoid tail recursion while optimizing code? |
||