Entries:
Posts:

Something went wrong getting user information from Channel 9

Latest Achievement:

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Something went wrong getting the Visual Studio Achievements

# C9 Lectures: Yuri Gurevich - Introduction to Algorithms and Computational Complexity, 3 of 3

• Posted: Apr 21, 2011 at 11:48 AM
• Avg Rating: 4.5

(7)
• 57,610 Views

Right click “Save as…”

• High Quality WMV (best available)
• MP3 (Audio only)
• Mid Quality WMV (Lo-band, Mobile)
• High Quality MP4 (best available)
• Low Quality MP4 (approx. 500-800kbps)

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.

## Follow the Discussion

• Oops, something didn't work.

Getting "follow" information
Start following these comments
Setting up your "follow"
• 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!

close