Lecture

Calcul and Algorithms: Quadratic Equation Example

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-119(d): Information, Computation, Communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (langage C++). ...

Description

This lecture introduces three types of control structures: conditional branches, conditional loops, and iterations. It then presents an algorithm to solve a quadratic equation, discussing the design process and different scenarios. The importance of ensuring algorithm correctness through mathematical proofs is emphasized.

Instructor

Jean-Cédric Chappelier

Jean-Cédric Chappelier is currently senior researcher and lecturer in Computational Linguistics at the Ecole Polytechnique Fédérale de Lausanne (Switzerland). He holds an Ms.Sci. and a Ph.D. in Computer Science from the Ecole Nationale Supérieure des Télécommunications de Paris (France).

Official source

Related concepts (23)

Mathematical proof

A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation".

Mathematical induction

Mathematical induction is a method for proving that a statement is true for every natural number , that is, that the infinitely many cases all hold. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder: Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). A proof by induction consists of two cases.

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Computer-assisted proof

A computer-assisted proof is a mathematical proof that has been at least partially generated by computer. Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a computer program to perform lengthy computations, and to provide a proof that the result of these computations implies the given theorem. In 1976, the four color theorem was the first major theorem to be verified using a computer program.

Proofs and Refutations

Proofs and Refutations: The Logic of Mathematical Discovery is a 1976 book by philosopher Imre Lakatos expounding his view of the progress of mathematics. The book is written as a series of Socratic dialogues involving a group of students who debate the proof of the Euler characteristic defined for the polyhedron. A central theme is that definitions are not carved in stone, but often have to be patched up in the light of later insights, in particular failed proofs. This gives mathematics a somewhat experimental flavour.

Related lectures (64)

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Set Cover: Integrality Gap

Explores the integrality gap concept in set cover and multiplicative weights algorithms.

Quasi-newton optimization

Covers gradient line search methods and optimization techniques with an emphasis on Wolfe conditions and positive definiteness.

The Languages of Isabelle: Isar, ML, and Scala

Explores the languages of Isabelle, focusing on Isar, ML, and Scala, covering proof schemes, Natural Deduction rules, inductive definitions, and the LCF approach.

Algorithms & Growth of Functions