Discrete Mathematics (Coursera)

Discrete Mathematics (Coursera)

Añade tu reseña
Añadir a Mis FavoritosAñadido a tus favoritosEliminado de tus favoritos 0
Añadir para comparar

Descripción de “Discrete Mathematics (Coursera)”

Discrete mathematics forms the mathematical foundation of computer and information science. It is also a fascinating subject in itself. Learners will become familiar with a broad range of mathematical objects like sets, functions, relations, graphs, that are omnipresent in computer science. Perhaps more importantly, they will reach a certain level of mathematical maturity – being able to understand formal statements and their proofs; coming up with rigorous proofs themselves; and coming up with interesting results.

This course attempts to be rigorous without being overly formal. This means, for every concept we introduce we will show at least one interesting and non-trivial result and give a full proof. However, we will do so without too much formal notation, employing examples and figures whenever possible.

The main topics of this course are :

(1) sets, functions, relations,

(2) enumerative combinatorics,

(3) graph theory,

(4) network flow and matchings.

It does not cover modular arithmetic, algebra, and logic, since these topics have a slightly different flavor and because there are already several courses on Coursera specifically on these topics.

Who is this class for: The main target audience of this course is undergraduate students from Computer Science, Mathematics, and other related subjects. It is also suited for people with an interest in maths but without much prior formal education therein.

Syllabus

WEEK 1

Introduction – Basic Objects in Discrete Mathematics

This module gives the learner a first impression of what discrete mathematics is about, and in which ways its “flavor” differs from other fields of mathematics. It introduces basic objects like sets, relations, functions, which form the foundation of discrete mathematics.

Graded: Exercises for introduction lesson

Graded: Sets, Relations, Functions

Graded: Sets, relations, and functions

WEEK 2

Partial Orders

Even without knowing, the learner has seen some orderings in the past. Numbers are ordered by
Graded: Partial orders, maximal and minimal elements, chains, antichains

Graded: Partial orders, maximal and minimal elements, chains, antichains

WEEK 3

Enumerative Combinatorics

A big part of discrete mathematics is about counting things. A classic example asks how many different words can be obtained by re-ordering the letters in the word Mississippi. Counting problems of this flavor abound in discrete mathematics discrete probability and also in the analysis of algorithms.

Graded: Counting Basic Objects

Graded: Counting Basic Objects

WEEK 4

The Binomial Coefficient

The binomial coefficient (n choose k) counts the number of ways to select k elements from a set of size n. It appears all the time in enumerative combinatorics. A good understanding of (n choose k) is also extremely helpful for analysis of algorithms.

Graded: Combinatorial Identities

Graded: Digging Into Pascal’s Triangle

WEEK 5

Asymptotics and the O-Notation

Graded: Basic Facts

Graded: Classes that often occur in complexity theory

WEEK 6

Introduction to Graph Theory

Graphs are arguably the most important object in discrete mathematics. A huge number of problems from computer science and combinatorics can be modelled in the language of graphs. This module introduces the basic notions of graph theory – graphs, cycles, paths, degree, isomorphism.

Graded: Graphs and Isomorphisms

Graded: Graphs, isomorphisms, and the sliding tile puzzle

Graded: The Graph Score Theorem

WEEK 7

Connectivity, Trees, Cycles

We continue with graph theory basics. In this module, we introduce trees, an important class of graphs, and several equivalent characterizations of trees. Finally, we present an efficient algorithm for detecting whether two trees are isomorphic.

Graded: Cycles and Trees

Graded: Cycles and Trees

Graded: Spanning Tree Exchange Graph

WEEK 8

Eulerian and Hamiltonian Cycles

Starting with the well-known “Bridges of Königsberg” riddle, we prove the well-known characterization of Eulerian graphs. We discuss Hamiltonian paths and give sufficient criteria for their existence with Dirac’s and Ore’s theorem.

Graded: Hamiltonian Cycles and Paths

Graded: Hamiltonian Cycles and Paths

WEEK 9

Spanning Trees

We discuss spanning trees of graphs. In particular we present Kruskal’s algorithm for finding the minimum spanning tree of a graph with edge costs. We prove Cayley’s formula, stating that the complete graph on n vertices has n^(n-2) spanning trees.

Graded: Minimum Spanning Trees

Graded: Minimum Spanning Trees

Graded: Counting Trees on n Vertices

WEEK 10

Maximum flow and minimum cut

This module is about flow networks and has a distinctively algorithmic flavor. We prove the maximum flow minimum cut duality theorem.

Graded: Network Flows

WEEK 11

Matchings in Bipartite Graphs

We prove Hall’s Theorem and Kőnig’s Theorem, two important results on matchings in bipartite graphs. With the machinery from flow networks, both have quite direct proofs. Finally, partial orderings have their comeback with Dilworth’s Theorem, which has a surprising proof using Kőnig’s Theorem.

Graded: Matchings in Bipartite Graphs

Especificaciones: Discrete Mathematics (Coursera)

Curso ofrecido por
Disponibilidad

✔ Disponible

Plataforma

Universidad

Impartido por

Dominik Scheder

País

China

Nivel, duración y fechas
Nivel

Intermedio

Fecha

04/05/2020

Duración

11 semanas

Tiempo necesario

3-5 horas/semana

Idioma del curso
Idioma vehicular

Inglés

Subtítulos

No informado

Exámenes y Certificados
Certificados

Certificado de Pago

Exámenes/Proyectos

Con Examen/Proyecto Final Gratis

User Reviews

0.0 fuera de 5
0
0
0
0
0
Write a review

Aún no hay reseñas.

Se el primero en opinar sobre “Discrete Mathematics (Coursera)”

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Antes de enviar tu opinión, has de aceptar nuestra política de cookies y privacidad

Este sitio web utiliza cookies para un correcto funcionamiento. Si continúas navegando estás dando tu consentimiento para estas cookies y aceptas nuestra política de cookies, clic para más información.

ACEPTAR
Aviso de cookies
Comparar artículos
  • Total (0)
Comparar
0