Explore
For Enterprise
Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Títulos y certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

Modeling

Loading...

Principles of Computing (Part 2)

Universidad Rice

4.8 (268 calificaciones) | 10K estudiantes inscritos

Curso 4 de 7 en Fundamentals of Computing Programa Especializado

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.

Destrezas que aprenderás

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

Revisiones

4.8 (268 calificaciones)

5 stars
226 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.

De la lección

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

Impartido por:

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

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados