C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 3 of 3
Download this episode
Description
The great Yuri Gurevich is back!! Yuri is a logician, computer scientist, and inventor of abstract state machines. He currently works in Microsoft Research (he's a member of Wolfram Schulte's RiSE team).
This is the third and final part in our introductory series of lectures exploring the fundamental logical construct that powers all that we do as software engineers—the algorithm.
In part 3, Dr. Gurevich teaches us about bounded complexity and the axiomatic definition of sequential algorithms.
Find some time to watch this. You'll be learning about algorithms from one of the world's premiere minds in the science of logic and algorithms. In this lecture, Yuri references a few of his academic papers, which you can find here.
Thank you, Yuri, for taking the time to share your extensive knowledge and gentle, kind spirit with Niner Nation. We all really appreciate it! Thanks, too, to Wes Dyer and Bart De Smet for being our live audience for this lecture and asking great questions.
Share
Format
Available formats for this video:
Actual format may change based on video formats available and browser capability.
More episodes in this series
C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 2 of…
Related episodes
C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 2 of…
C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 1 of…
C9 Conversations: Yuri Gurevich On Logic, Imperative, Abstraction and Algorithms
Advanced Analytics Projects  What Could Go Wrong?
Jim Radigan: Inside AutoVectorization, 1 of n
Guido de Caso  Distributed Knowledge Authorization Language
C9 Lectures: Greg Meredith  Monadic Design Patterns for the Web 4 of 4
C9 Lectures: Stephan T Lavavej  Advanced STL, 6 of 6
ICSE 2011: Conversation with Baris Aktemur
ICSE 2011: Danny Dig  Retrofitting Parallelism into a Sequential World
The Discussion

This is great!
Thank you, Charles, Yuri, Wes and Bart!
It was a very interesting discussion .
I still didn't get how a "crash" case is implicitly defined.
I can understand that mathematical sets don't have duplicate and therefore duplicate values are excluded either by UNION or by { }.
I can also see how "crash" could be formalized in various ways, I just don't know which would be the most appropriate. So basically I don't see the set constraint or a definition of an "inconsistent set". I think both pairs { (a1,v1), (a1,v2) } in this set are valid mathematically and there needs to be another condition!? I am not sure.
Thanks!!!

Personally I consider that the classical algorithm evolved into a higher order algorithm called a design pattern, which utilizes multiple algorithms together which itself doesn't have a bounded time but makes use of algorithms which do execute in bounded time.
It was sort of funny how Bart & Wes were trying to specialize the general semantics to fit modern practice and machine architecture so they could connect it with classical computer science. But this is basically just explaining how computer science evolved and the algorithm can be formally defined, even though we just have basic common knowledge of this if we program, but as this lecture shows, the math and science and formal explanation shows how computing can indeed be complex and its great that we can abstract away the need for knowing all this to create a massive learning curve.
@ivan_ I've understood the meaning of "crash" to be interchangeable with "fail". So things fail and don't work which implies a crash to happen and being invalid. But that is just my understanding and not his formal explanation on the subject.

It is implicit. Yuri calls it "inconsistent set" where at least two of the pairs have the same location such as in my example { (a1, v1), (a1, v2)}, where a1 is a location and v1 <> v2. In this case crash occurs. So we can define it something like that (sorry no math notations in here just English):
for every Ai where i = {1..k} and k < (infinity), there exists at least two tuples in the form (A, V)i, where Aj = Al, while Vj <> Vl and j <> l, and j,l = {1..k}.
This to me would be a definition of a "crash" or inconsistent state. I think (which doesn't bear a lot of weight ).
Thanks!
Comments closed
Comments have been closed since this content was published more than 30 days ago, but if you'd like to send us feedback you can Contact Us.