Name: Lec 15｜MIT 6.046J / 18.410J アルゴリズム入門 (SMA 5503), Fall 2005 (Lec 15 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005)
Uploaded: 2021-01-14T04:54:44.000Z
Duration: 1 h 11 min 1 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

So, the topic today is dynamic programming.

The term programming in the name of this term doesn't refer

to computer programming. OK, programming is an old word

that means any tabular method for accomplishing something.

So, you'll hear about linear programming and dynamic

even though we now incorporate those algorithms in computer

programs, originally computer programming, you were given a

datasheet and you put one line per line of code as a tabular

method for giving the machine instructions as to what to do.

Of course, and now conventionally when you see

programming, you mean software, computer programming.

And these terms continue in the literature.

So, dynamic programming is a design technique like other

design techniques we've seen such as divided and conquer.

OK, so it's a way of solving a class of problems rather than a

So, we're going to work through this for the example of

so-called longest common subsequence problem,

sometimes called LCS, OK, which is a problem that

And it's particularly important in computational biology,

where you have long DNA strains, and you're trying to

find commonalities between two strings, OK, one which may be a

genome, and one may be various, when people do,

what is that thing called when they do the evolutionary

OK, phylogenetic trees. Good, so here's the problem.

So, you're given two sequences, x going from one to m,

and y running from one to n. You want to find a longest

sequence common to both. OK, and here I say a,

not the, although it's common to talk about the longest common

subsequence isn't unique. There could be several

different subsequences that tie for that.

However, people tend to, it's one of the sloppinesses

that people will say. I will try to say a,

unless it's unique. But I may slip as well because

it's just such a common thing to just talk about the,

So, here's an example. Suppose x is this sequence,

and y is this sequence. So, what is a longest common

Is there another one that's the same length?

Is there another one that ties? BCAB, BCAB, another one?

BCBA, yeah, there are a bunch of them all of length four.

There isn't one of length five. OK, we are actually going to

come up with an algorithm that, if it's correct,

we're going to show it's correct, guarantees that there

isn't one of length five. So all those are,

we can say, any one of these is the longest comment subsequence

using functional notation, but it's not a function that's

really a relation. So, we'll say something is an

LCS when really we only mean it's an element,

if you will, of the set of longest common

abusive notation. As long as we know what we

mean, it's OK to abuse notation. What we can't do is misuse it.

But abuse, yeah! Make it so it's easy to deal

so there's a fairly simple brute force algorithm for

let's just check every, maybe some of you did this in

your heads, subsequence of x from one to m to see if it's

So, just take every subsequence that you can get here,

So, to check, so if I give you a subsequence

of x, how long does it take you to check whether it is,

in fact, a subsequence of y? So, I give you something like

And how do you do it? Yeah, you just scan.

So as you hit the first character that matches,

recursively see whether the suffix of your string matches

the suffix of x. OK, and so, you are just simply

walking down the tree to see if it matches.

You're walking down the string to see if it matches.

OK, then the second thing is, then how many subsequences of x

x just goes from one to m, two to the m subsequences of x,

OK, two to the m. Two to the m subsequences of x,

how many subsequences are there of something there?

If I consider a bit vector of length m, OK,

that's one or zero, just every position where

字幕リスト動画再生

Lec 15｜MIT 6.046J / 18.410J アルゴリズム入門 (SMA 5503), Fall 2005 (Lec 15 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005)

long

problem

compute

good