An introduction to probabilistic reasoning for random structures, including random graphs, graphical models and Markov Random Fields (MRF). Topics include: large deviations theory and concentration inequalities Theory of random graphs,the moment method. Combinatorial optimization on random graphs and the differential equations method. Planted clique and applications to sparse PCA in statistics. Gibbs measures on finite and infinite MRF. Algorithms for counting and computing partition functions, Dubroshin's uniqueness and the correlation decay method. Glauber dynamics and rapid/torpic mixing. Introduction to statistical physics. Reconstruction of MRF from observations. Sample and computational complexity.