Combinatorics, Graphs and Boolean Logic

by I. Makarov

Syllabus    http://www.hse.ru/edu/courses/130675921.html

 

           Lectures 1-2 (PDF, 2.50 Мб)

   II.     Euler  formula for intersecting sets, Newton  binomial, asymptotic combinatorial identities
          
           Lecture 3 (PDF, 319 Кб)

           HomeWork 1 (PDF, 502 Кб)

           Lecture 4 (PDF, 194 Кб)

                    Lecture 4 supplementary (proofs) (PDF, 864 Кб)

   III.    Linear recurrent sequences and regular generating functions
                   Lecture 5 (PDF, 2.89 Мб)

                  Lecture 5 supplementary (Mobius) (PDF, 1.34 Мб)

           Lecture 6 (PDF, 3.50 Мб)

           HomeWork 2 (PDF, 511 Кб) 

 IV.    Group action on finite sets
          Lecture 7 (PDF, 206 Кб)

          Lecture 8 (PDF, 293 Кб)

          HomeWork 3 computataions & coding (PDF, 453 Кб)

           Homework #3:
           Solve 3 tasks from section 1-3, each from one section.  
           Task distribution is placed in the grade google-sheet: 
           https://goo.gl/Ft1dx9
           Compute and code exact solutions - fixed problem can be
           implemented by a pair of students.
           You have to send to cgbl2016@gmail.com
           interactive report in *.rmd format!!! 
           (networkx + *.ipynb is also allowed)

           Mid Term 1 Sample (PDF, 489 Кб)

   V.    Graphs and trees, basic theorems on graphs and coloring  of graph
           Lecture 9.1 (PDF, 1.63 Мб)

           Lecture 9.2 (PDF, 842 Кб)

           Lecture 10 (PDF, 351 Кб)

           Lecture 11 (PDF, 269 Кб)

         Secret Section: Social Networks
         1. Basic concepts
           IGraph Tutorial + Installation (PDF, 536 Кб)

           IGraph (ZIP, 232 Кб)

           IGraph (PDF, 269 Кб)

         2. Graph file-formats. Power law. Network descriptive statistics

           Networks (ZIP, 10.25 Мб)

           Graph Formats and Network Desciptive Statistics (PDF, 687 Кб)

            HomeWork 4
           HomeWork_4 (ZIP, 1.34 Мб)

           HomeWok 4 Network Descriptive Statistics (PDF, 245 Кб)

                  HomeWork_4_Hints (ZIP, 1.35 Мб)

                  HomeWork 4 Hints (PDF, 331 Кб)

       3. Mathematical models of networks
           Graph_Models (ZIP, 3.92 Мб)

           Mathematical Models of Networks (PDF, 1.37 Мб)

       4. Centrality metrics (read during vacations)
           Centrality_Metrics (ZIP, 916 Кб)

           Centrality Metrics (PDF, 1.46 Мб)

       5. Community detection. Dense Graphs.

           Community_Detection (ZIP, 1.64 Мб)

           Dense Graphs and Communities (PDF, 1.02 Мб)

       6. Community detection II. Graph Patterns. Vizualization.
           Graph_Patterns_and_Vizualization (ZIP, 2.06 Мб)

           Graph Patterns and Vizualization.
Summary for Exploratory Graph Analysis (PDF, 1.24 Мб)

            HomeWork 5-6 - till 08.05.2016
           VK NodeXL Plugin (PDF, 741 Кб)

           HomeWork_5-6 (ZIP, 1.37 Мб)

           HomeWork_5-6 Graph Analysis (PDF, 202 Кб)

    Important info: Project - till 12.06.2017
    (more precisely, 10 days before session week).
    Read carefully implementation part (4) about VK API.         
           SNA_Project_Bac (PDF, 120 Кб)


Mining Social Media https://github.com/MakarovIA/Mining-the-Social-Web-2nd-Edition
VKontakte
VK R Tutorial

Facebook

TwitteR
Package https://cran.r-project.org/web/packages/twitteR/twitteR.pdf
Tutorial http://geoffjentry.hexdump.org/twitteR.pdf
Presentation http://www.rdatamining.com/docs/twitter-analysis-with-r

---

   VI.   Boolean logic. Predicate logic, basic notions, prefix form
           Lecture 12 (PDF, 1.32 Мб)

 VII.  Completeness of functional systems
           Lecture 13.1 (PDF, 1.60 Мб)

           Lecture 13.2 (PDF, 3.52 Мб)

 VIII.   Normal forms, complexity for Boolean functions realizations by schemes and formulas
  IX.   Basis and finite total equivalence systems for closed classes of Boolean logic
           Lecture 14.1 (PDF, 523 Кб)

           Lecture 14.2 (PDF, 1.03 Мб)

           Lecture 15 (PDF, 417 Кб)

 Secret Section: Knowledge Representation and OBDA

           Lecture Notes  + Home Assignment 1-5
           Practical Classes 
           Addirional Reading 
           Prolog Online

           The Semantic Web

Homework 7: Write a simple knowledge base, consisting of at least 30 facts about your 
interests and your friends. Extract at least 5 rules, representing dependencies for them.
Construct 15 new rules, containing logical connectives and, or, not, and recursive rules
with respect to friends' relations.

Homework 8: Make a dictionary KB from here (you may use C++, R, Python, etc.). Create a crossword using, for example, this service, with at least 30 horizontal and 30 vertical words of a length greater than 6 and containing at least 45 word intersections. Answer crossword query through the Dictionaty KB as it was presented in the exercise. + independently provide queries and explain different results for exercises 1 and 2.

Homework 9: Solve one of two tasks:
1) For a given list write a function that finds its local maximum (possibly, the first or the last) element in O(log n).
2) Try to find a sublist S in a list L. Output the index of a first entry.

Homework 10 (30 points): Describe grammar rules for simple C++ compiler; write grammar rules and parser in Prolog. Output parse tree (15). Calculate the programm for a given values of variables, inputted as a list to query program([x,y,...]). (10). Use lambda calculus to include semantic rules, such as variable should be declared before assignment, devision by zero is prohibited, bynary operations should have the same type of arguments (5).

---

         
Exam_Sample (PDF, 385 Кб)out of date

Friday 18 June            - office hours for Exam preparation
Monday 20 June         - written and oral
(for those, who fail for section in written part) parts of exam

Tutorials
 R/RStudio Setup Guide (PDF, 1.33 Мб)

          R Setup
          RStudio Setup

 R Tutorial (PDF, 885 Кб)

 R Cheat-Sheet (PDF, 72 Кб)

 R Markdown Tutorial (PDF, 650 Кб)

 R Short Introduction (PDF, 367 Кб)

 Coursera course for R
 Learning R with SWIRL 

 Portal for R References