Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Modeling

Loading...

计算原理（第 2 部分）

4.8（270 個評分） | 10K 名學生已註冊

課程 4（共 7 門，计算机基础專項課程）

This two-part course introduces the basic mathematical and programming principles that underlie much of Computer Science. Understanding these principles is crucial to the process of creating efficient and well-structured solutions for computational problems. To get hands-on experience working with these concepts, we will use the Python programming language. The main focus of the class will be weekly mini-projects that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 2 of this course, the programming portion of the class will focus on concepts such as recursion, assertions, and invariants. The mathematical portion of the class will focus on searching, sorting, and recursive data structures. Upon completing this course, you will have a solid foundation in the principles of computation and programming. This will prepare you for the next course in the specialization, which will begin to introduce a structured approach to developing and analyzing algorithms. Developing such algorithmic thinking skills will be critical to writing large scale software and solving real world computational problems.

查看授課大綱

您將學習的技能

Recursion, Algorithms, Python Programming, Tree (Data Structure)

審閱

4.8（270 個評分）

5 stars
228 ratings
4 stars
35 ratings
3 stars
7 ratings

AM

Jan 13, 2017

If I wanted to learn programming from scratch, I'd take this specialization. They are great teachers and the recursion section was extremely helpful.

AF

Dec 08, 2017

Another fantastic course from the team at Rice University. The coursework is interesting and challenging, and I really feel I have learned a lot.

從本節課中

Modeling, Assertions, and Invariants

This week, we will explain the importance of modeling. We will also explore how to use assertions and invariants to ensure that our models are always consistent and correct.

The Importance of Modeling 3:04

Assertions 7:22

Invariants13:22

Software Development 14:52

教學方

Scott Rixner
Professor
Joe Warren
Professor
Luay Nakhleh
Associate Professor

腳本

[MUSIC]

Okay, so today I'm going to talk about

modeling, the importance of modeling in computer science.

And I'm going to illustrate it with a very important

example from my own research area, which is computational biology.

The example concerns the problem, a central problem in biology known

as the sequence alignment problem, or

more specifically, pair wise sequence alignment.

So, what is this problem?

Biologists often have this issue that they get a sequence, a DNA

sequence for a certain gene from human, and also from a different organism.

For example, they look at the human.

And take a sequence that looks like this, ACCT.

And they look at another organism, let's say, mouse.

They take, what we call a homologous sequence or the counterpart

of the sequence in mouse, and the sequence looks like ACTC.

Okay, let's see.

C another C here.

No, if you look at these two sequences, we,

the biologist says that I know these two sequences

evolve from a common ancestor, somehow a long time

ago when, when human and mouse had a common ancestor.

These two sequences came from one sequence.

They used to be one sequence millions of years ago.

Okay, so now again from human we have ACCT and here we have

ACTCC and they came from a common ancestor here.

Of course we have no record for this sequence, this one, again

this happened millions of years ago and we cannot just find this sequence

easily, we cannot find the sample in the, in nature, that we

can sequence and say, okay, this is how it used to be, right.

All right, so now the biologist is interested in the following problem.

Given these two sequences which biologists can easily get, I mean

we can easily today get DNA from human, and DNA from mouse.

They say I want you to align them.

Okay?

I want you to align them.

And through this alignment process, basically what

the biologist gets is reversing this process.

When I align these two sequences, we are

basically telling the biologist what type of mutations happened.

Now, when a biologist tells me this, that I want you to align these sequences.

I need to understand from the biologist first, is

that, why are the two sequences different, of different length.

The content is different also.

And what does the biologist mean by aligning them.

Okay?

So, when I talk to the biologist, the biologist says that by

aligning, I mean make them of equal length by inserting dashes in them.

Okay?

So, you can insert dash in any place in the sequence and align a letter with

a letter or a letter with a dash and you can make them of equal length.

So, for example, when I talk to the biologist, the

biologist might tell me, here's an example of an alignment.

ACCT-

ACTCC.

So, this way, basically, we are aligning this A with

A, C with C, C with T, T with C.

Because for this C, there's no letter, we ent, we insert a dash.

So, this is a possible alignment.

[BLANK_AUDIO]

Okay?

Now, if I look at this, what the biologist has told me,

then I can go to a biologist saying, is this an alignment?

[BLANK_AUDIO]

I inserted a dash, but here, between the A and C.

And it does, it does, it looks like an alignment because

it's of the same, both of them are the same length.

And I'm aligning a letter with a letter or a letter with a dash, right?

And biologist say, yes this is an alignment.

And then I say, is this an alignment?

And the biologist say, no

I don't like this because

this is meaningless.

Right?

I'm saying there was a, there was no letter here, no letter here.

And this is unnecessary to add.

So, biologist tells me that no, this is not an alignment.

Okay?

So now I start getting some information about

how to model the structure of an alignment.

So, to model the structure of an alignment, given two

sequences, basically I need to enter dashes in one or two

of the sequences so that I can make them aligned in

terms of, that is, they are both of the same length.

And when I enter these dashes, then I have to make the sequences of the same

length such that either a letter goes with a letter, or a dash with a letter.

But no dash with dash, okay?

So, this is a possible alignment, this is a possible alignment.

And this is the first step in, towards answering

the problem and solving the questions that the biologist is

interested in, which is how do we model an alignment,

what is the actual mathematical object that captures an alignment.

And in this case, it is we can formalize it very cleanly, mathematically by

saying, given two sequences, you can enter dashes in any of them or both.

Such that you make them of the same length.

And such that no dash goes with a dash, either

a letter with a letter or a dash with a letter.

And, of course, you cannot change the order

of the letters in any of the sequences.

So I cannot take ACCT and make it ACTC, for example.

All right?

So now, the first phase of, of modeling here was to get a notion of feasibility.

What is a feasible alignment versus what's not feasible.

This is not allowed.

The biologist doesn't like something like this.

So, now that I understand from a biologist what he or she wants

from me in terms of what is an alignment, I can look at this.

Now we can use mathematical skills to say, okay,

what is the number of such possible feasible alignments?

And I'm not going to show the number here.

But believe me, the number is going to be very large.

Right?

In the sense that if you give me a sequence of length four

and a sequence of length five, there are many, many ways of aligning them.

For example, one that you are not seeing here, is, for is ACCT.

They all go with dash here, and ACTCC, they all go with dashes here.

This is another possible alignment.

Okay?

It is feasible the, both of the same length.

A letter goes with a dash or a letter with a letter.

Nothing is wrong with it.

And I can keep adding more and more.

So the first step of modelling the feasibility of an alignment.

What is an alignment?

That is fine.

All right?

And using mathematical tools now I can reason about what is the number.

Once I reason about the number and find it's very large.

Now I understand I need also a way to choose among these.

So I can tell the biologist, here's an alignment.

Here's an alignment.

Here's an alignment.

And I can keep listing them.

But the biologist says, for example, I don't like this.

Or the biologist might say, I don't like this.

Now we have again to go back to the modeling

phase, which is to say, why don't you like this?

Or, why don't you like this?

This is a modeling question.

Because if a biologist tells me that they like this

but not like this, I have now to start doing

a mathematical reasoning about his so that I turn that

like and dislike, I turn it into some mathematical measure.

Say, I will define a measure that will

give a better value to this, than this, okay?

And once we do this, now we can turn to the algorithmic question, and

say, now that I have a measure, that gives a score to each possible alignment.

Now I'm interested in an algorithm that will find,

of all possible alignments, the one that maximizes the score.

Okay, and here, just to give an example of one what such a score might be.

And this is a real example, I mean, this is what a biologist might use.

For example here, for the, for the case of DNA, you can basically

describe such a, scoring mechanism by a 5 by 5 matrix.

And, every entry here is going to tell us what is the score or

penalty of putting a letter with a letter or a dash with a letter.

So, for example, the biologist might say, I, I, I like

alignments that always match the same letter with the same letters.

Like A with A, C with C, T with T, G with G.

In terms of modeling, it means that I should give

very high score to these cases, like ten, ten, ten, ten.

The biologists will tell me that because

of evolution and mutation can change the letter,

that the biologist is willing to accept T going with C, for example, all right.

But they will again still pre, pre, prefer that the sequence are written like this.

So, in that case, we can give this is A, A, A going with C, for example, a score

that's lower than ten, we can give it four, four, four and so on, okay.

And we can use it as symmetric metrics and we can give the same thing.

Then the biologists might say, you know, I

don't like too many dashes, I'm going to penalize it.

I'm going to see if I put dashes, the more dashes you put,

the lower the score should get, so we have to penalize these things.

For example, saying that if you put any letter with

a dash you penalize it by three points, for example.

[NOISE] And in some sense, this is minus infinity.

I'm not going to allow you to put a dash with a dash.

If you put it.

The score of that is very bad.

That we are not going to accept that alignment.

Okay?

So now, this is the second phase of the modelling.

Which is, how do I get a score for an alignment?

Or how do I evaluate an alignment whether it is good or not?

By going through the modelling.

By saying, the biologist has given, been

giving me information about, you know, what,

what do they like about A with A, or don't like about dash with C?

And I turn it into a mathematical object.

because once I have this, now I can say, what is the score of this alignment?

Well, the answer is, A with A, that scores ten.

C with C scores ten.

T with C scores four.

T over C scores four.

Dash over C scores minus three.

And if I use an additive measure, I say it's 20, 28, minus 3, 25.

Okay, so now I'm going through this modeling, I

have been going through back and forth with a biologist.

Taken the notion of an alignment that the biologist was mentioning.

It's going through modeling.

I understand what is a feasible alignment, what's not feasible, then given all the

possible feasible alignment, through modeling, I have

some, some mechanism to score this alignment.

And then the last step I would go through with algorithmic development phase.

Where I can develop an algorithm that will find, of all the possible,

feasible alignments, and given the scoring scheme, the one that maximizes the score.

Okay.

So this is an example that illustrates the importance of modeling.

I couldn't have gone to solve the problem for the biologist if I didn't go through

this entire process of modelling what is in

alignment, what is fine, what is not fine.

How do I distinguish among the fine alignments or the feasible ones?

And this process of modeling is very mathematical in nature.

And this is why we have been teaching you math, to illustrate, to,

to be able to use this mathematical tools to go through this process

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司