Donald Knuth - The Knuth-Morris-Pratt algorithm (92/97)
Donald Knuth (b. 1938), American computing pioneer, is known for his greatly influential multi-volume work, 'The Art of Computer Programming', his novel 'Surreal Numbers', his invention of TeX and METAFONT electronic publishing tools and his quirky sense of humour. Donald Knuth (b. 1938), American computing pioneer, is known for his greatly influential multi-volume work, 'The Art of Computer Programming', his novel 'Surreal Numbers', his invention of TeX and METAFONT electronic publishing tools and his quirky sense of humour. [Listener: Dikran Karagueuzian; date recorded: 2006]
TRANSCRIPT: There was a story really behind every... every paper that I wrote pretty much and this one is a kind of interesting story. The algorithm itself has became famous but not, I'm... I'm not sure, well... I haven't had to use it myself for the last 20 years but... but it's in all the textbooks and... and it makes a nice instructive example of... of if you're... you're trying to search through a long piece of... piece of text and you're looking for a certain word - suppose I'm looking for the word, well, t-h-e, or something like that. It would be foolish to look for that word, let's look... look for d-i-k-r-a-n or something, okay - d-i-k-r-a-n. Okay, so... so I can... I can go until I... so the obvious way is you... you... you start at every place in the text and you say is it a D? Oh yes. Then you look at the next letter, is it an I? Yes. Is it a K? Then look... is it a K? No, this is the word 'direction' or something. All right well then go to the next place and... and start... start over again. Is that a D? Well all, you know, all we observed was that you already know that it's an I, it's not a D so you might as well skip ahead a little further before you make your next test. Well, there's more to the story than that though. The... you can have... you can have more complicated words where... like you were looking up the word 'didymus' or something where there's a couple of Ds and so you'll have... the... but the... the interesting thing in this case was that a professor at Berkeley, Steve Cook had proved a very amazing theorem. He said if... if you could... if you took a kind of... a certain kind of computer that is very limited in its capability, and if you could write a program for that dumb kind of computer to solve a problem, no matter how slow that program was then there was a fast way to write a program for a real computer. So, in other words if you take a... a particular limited computer and if it... if it can solve a problem at all then there's a fast way to do it on a real computer. So one of the problems that we... that we could solve with that... with this... with this funny computer was to decide whether a string of letters was a palindrome, whether or not it read the same backward... backward to forward... no, sorry, was a... was a concatenation of... of palindromes... palindrome followed by another palindrome and so on. It was just a curiosity, I mean nobody really cares about concatenation of palindromes but there it was, and... and so according to Cook's theorem, since there was a way for this funny machine to... to recognise these... these palindromes, then there must be a fast way to recognise these... these concatenations of palindromes on a regular computer. But I couldn't think of any good way to do it on a regular computer, it just seemed to me that that was going to be a much harder problem. So, I thought I... I was a pretty good programmer but here is this theorem saying there's a way to do it and I can't think of the way to do it. That's the first time that I was sort of stumped this way by saying that somebody saying that he had a good way and I couldn't think of it. And so I... so I took... I took an afternoon, or maybe an afternoon and evening and I... I worked out in great detail on a blackboard the way Cook's construction would have finally given me a way on my... on my regular computer to... to do it fast. And all of a sudden, ah ha, of course, that's the trick. And so I was smoking out the... the idea as to how this general theorem would... would apply to a... to a real... real programming problem and it... and it occurred that this would also solve the problem of... of searching in the text. So I... I mentioned this on a trip to Berkeley and I met... where I met Vaughan Pratt and he... he was the one that made most of the crucial insights, you know, I was just the one that wrote it up afterwards and then we found out that Jim Morris had discovered the same idea a few months earlier and used it in software and that other people had looked at this program and didn't understand it so they took it out. But, so... anyway, it's a nice... it's a method for efficient searching text but also good...
Visit https://www.webofstories.com/play/don... to read the remaining part of the transcript and to view more of Donald Knuth’s inspiring thoughts and life stories.
TRANSCRIPT: There was a story really behind every... every paper that I wrote pretty much and this one is a kind of interesting story. The algorithm itself has became famous but not, I'm... I'm not sure, well... I haven't had to use it myself for the last 20 years but... but it's in all the textbooks and... and it makes a nice instructive example of... of if you're... you're trying to search through a long piece of... piece of text and you're looking for a certain word - suppose I'm looking for the word, well, t-h-e, or something like that. It would be foolish to look for that word, let's look... look for d-i-k-r-a-n or something, okay - d-i-k-r-a-n. Okay, so... so I can... I can go until I... so the obvious way is you... you... you start at every place in the text and you say is it a D? Oh yes. Then you look at the next letter, is it an I? Yes. Is it a K? Then look... is it a K? No, this is the word 'direction' or something. All right well then go to the next place and... and start... start over again. Is that a D? Well all, you know, all we observed was that you already know that it's an I, it's not a D so you might as well skip ahead a little further before you make your next test. Well, there's more to the story than that though. The... you can have... you can have more complicated words where... like you were looking up the word 'didymus' or something where there's a couple of Ds and so you'll have... the... but the... the interesting thing in this case was that a professor at Berkeley, Steve Cook had proved a very amazing theorem. He said if... if you could... if you took a kind of... a certain kind of computer that is very limited in its capability, and if you could write a program for that dumb kind of computer to solve a problem, no matter how slow that program was then there was a fast way to write a program for a real computer. So, in other words if you take a... a particular limited computer and if it... if it can solve a problem at all then there's a fast way to do it on a real computer. So one of the problems that we... that we could solve with that... with this... with this funny computer was to decide whether a string of letters was a palindrome, whether or not it read the same backward... backward to forward... no, sorry, was a... was a concatenation of... of palindromes... palindrome followed by another palindrome and so on. It was just a curiosity, I mean nobody really cares about concatenation of palindromes but there it was, and... and so according to Cook's theorem, since there was a way for this funny machine to... to recognise these... these palindromes, then there must be a fast way to recognise these... these concatenations of palindromes on a regular computer. But I couldn't think of any good way to do it on a regular computer, it just seemed to me that that was going to be a much harder problem. So, I thought I... I was a pretty good programmer but here is this theorem saying there's a way to do it and I can't think of the way to do it. That's the first time that I was sort of stumped this way by saying that somebody saying that he had a good way and I couldn't think of it. And so I... so I took... I took an afternoon, or maybe an afternoon and evening and I... I worked out in great detail on a blackboard the way Cook's construction would have finally given me a way on my... on my regular computer to... to do it fast. And all of a sudden, ah ha, of course, that's the trick. And so I was smoking out the... the idea as to how this general theorem would... would apply to a... to a real... real programming problem and it... and it occurred that this would also solve the problem of... of searching in the text. So I... I mentioned this on a trip to Berkeley and I met... where I met Vaughan Pratt and he... he was the one that made most of the crucial insights, you know, I was just the one that wrote it up afterwards and then we found out that Jim Morris had discovered the same idea a few months earlier and used it in software and that other people had looked at this program and didn't understand it so they took it out. But, so... anyway, it's a nice... it's a method for efficient searching text but also good...
Visit https://www.webofstories.com/play/don... to read the remaining part of the transcript and to view more of Donald Knuth’s inspiring thoughts and life stories.
همه توضیحات ...