Now, a lot of computer science students bristle a little bit when they take an algorithms class,
because of the heavy emphasis on mathematics.
A lot of us got involved in computer science because we really like doing stuff
and not necessarily doing math.
But nevertheless, I think there's a very strong case to be made for the importance
of mathematics in computer science and in algorithm design in particular.
I'd argue that there are three natural ways that theory stuff or math can really help.
One is to just get you thinking clearly about what it is that you're trying to accomplish.
It's very easy when you're in the depths of writing code to lose track
of what it is that you want the code to actually do.
Just thinking formally about what you're doing is something
that using your mathematical background can help with.
Another thing that it can be very helpful with is analyzing the efficiency of what you've produced.
You can actually know where there are spots where you could be doing a better job
and have the code be running more effectively and more efficiently
without producing incorrect code.
Just taking a moment to think a little mathematically can be a huge win
and save you tremendous amounts of time.
It sounds very important, right?
Now, this notion of efficiency is actually very important to think about.
What is it that you want your program to do efficiently.
Do you want it to be fast in terms of time?
Do you want it to be efficient in terms of the amount of memory
on the computer that it uses, so it does its work with as little memory as possible?
These days more and more people are worrying about energy usage.
Are there ways of organizing your computation so that it is efficient
in terms of the amount of power that it uses.
The tools that we develop in this course are going to be useful across the board here,
but we're going to mainly focus on issues of time.
To get you thinking about algorithms and how they work and what makes them correct
and how to make them more efficient, let's go through an example together.
Here is a little bit of Python code that I wrote.
It's a routine called naïve, because I'm not telling you yet what it actually is doing.
What it takes in as input are two integer-valued variables
that are none negative, and then it does some assignments
and recalculations and a while loop.
It runs for a little bit and then it returns z.
What I'd like you to do is take a look at this. It's not very long.
It's probably not completely obvious to you right away what it is that it's doing.
I encourage you to run this in Python.
Give it some example inputs and outputs.
See if you can come up with a pattern for what it is that it's doing,
and then convince yourself why.
Once you have a hypothesis as to what it's doing,
see if you can figure out how you can convince yourself that this program actually
is computing what you think it's computing.
Then I want you to fill out the following quiz.
You can take this code, and you can run it for any particular value of a and b,
but I want you to think about what it does in general as a function of a and b.
When you run naive(a, b) does it return whichever of a or b is the larger one?
Does it calculate a - b, or for that matter, does it calculate b - a?
Does it calculate the sum of a and b?
Does it calculate the product of a and b?
Muchos estudiantes de ciencias de la computación se irritan un poco cuando toman una clase de algoritmos,
debido al fuerte énfasis en matemáticas.
Muchos de nosotros nos involucramos en informática porque realmente nos gusta hacer cosas
y no necesariamente hacer matemáticas.
Pero sin embargo, creo que hay un caso muy fuerte para la importancia
de las matemáticas, Ciencias de la computación y el diseño de algoritmos en particular.
Yo diría que hay tres formas naturales de ese tipo de cosas de teoría o matemáticas pueden ayudar.
Uno es para llegar a pensar con claridad acerca de cómo es que usted está tratando de lograr.
Es muy fácil cuando estás en las profundidades de escribir código para perder
de lo que es la que desea que el código hacerlo realidad.
Pensando solo formalmente en lo que haces es algo
que mediante su fondo matemático puede ayudar.
Otra cosa que puede ser muy útil con es analizar la eficacia de lo que ha producido.
Realmente se puede saber donde hay lugares donde usted podría hacer un mejor trabajo
y el código se ejecuta más eficaz y más eficiente
sin producir código incorrecto.
Sólo tomar un momento para pensar un poco matemáticamente puede ser una gran victoria
y ahorrar enormes cantidades de tiempo.
Suena muy importante, ¿verdad?
Ahora, esta noción de eficiencia es realmente muy importante para pensar.
¿Qué es lo que desea su programa hacerlo eficientemente.
¿Quieres que sea rápido en términos de tiempo?
¿Quieres que sea eficiente en términos de la cantidad de memoria
¿en el equipo que utiliza, así hace su trabajo con la memoria tan poco como sea posible?
Estos días cada vez más personas están preocupadas por el uso de la energía.
¿Hay alguna manera de organizar su cómputo para que sea eficiente
en cuanto a la cantidad de energía que utiliza.
Las herramientas que desarrollamos en este curso se van a ser útiles en todos los ámbitos
pero vamos a se centran principalmente en cuestiones de tiempo.
Para conseguirte pensando en algoritmos y cómo funcionan y lo que los hace correcto
y cómo hacerlos más eficientes, vamos juntos a través de un ejemplo.
Aquí le damos un poco de código Python que escribí.
Es una rutina llamada ingenuo, porque yo no estoy diciendo todo lo que realmente está haciendo.
Lo que se necesita como entrada son dos variables valores enteros
que no son negativos, y luego lo hace algunas tareas
y recálculos y un bucle while.
Se ejecuta durante un poco y luego se devuelve z.
Lo que me gustaría hacer es echar un vistazo a esto. No es muy larga.
Probablemente no es totalmente obvio para usted inmediatamente lo que es que lo está haciendo.
Os animo a ejecutar esto en Python.
Le dan algunos ejemplo entradas y las salidas.
Vea si usted puede subir con un patrón por lo que es que lo está haciendo,
y entonces por qué a convencerse.
Una vez que haya una hipótesis sobre lo que está haciendo,
Vea si usted puede averiguar cómo usted puede convencerse de que este programa realmente
es informática qué crees que es informática.
Entonces quiero que rellene el siguiente cuestionario.
Usted puede tomar este código, y se puede ejecutar para cualquier valor de a y b,
pero quiero que se piense en lo que hace en general como una función de a y b.
¿Al ejecutar ingenuo (a, b) lo hace volver a cualquiera de a o b es el más grande?
¿Calcula a - b, o de hecho, ¿calcula b - un?
¿Calcula la suma de a y b?
¿Calcula el producto de a y b?
コンピュータ・サイエンス専攻の学生が
アルゴリズムの授業を取ると大抵の場合
その数学的要素に混乱します
コンピュータ・サイエンスに携わる人は必ずしも
数学が好きではないのです
それでもコンピュータ・サイエンス
特にアルゴリズムにおいて
数学は非常に重要だと私は主張します
次の3つの点から理論または数学は有用です
1つ目は目的を明確にできるという点です
コードを書いている時に何をしようとしていたのかを
見失うのはよくあることです
数学的な知識を用い目的を形式的に捉えることで
これを防ぐことができます
もう1つの利点は作成したものの効率を
検証するのに有益だという点です
数学を用いることで
問題解決をより効率的にするためには
どこを修正すればいいのかを知ることができます
これにより正確さも保てます
少し数学的に考えるだけで多大な成果をもたらし
時間の節約にもなるのです
数学の重要性は分かりましたね
次に重要なのはこの効率性の尺度です
どの観点での効率性を重視しますか
短い時間で処理できるという効率性でしょうか
使用するメモリをできるだけ
少なくするという意味での効率性でしょうか
それとも最近 省エネルギーが叫ばれていますが
電気使用量をより少なくするという意味での
効率性でしょうか
このコースで学ぶツールは
いずれの効率性にも貢献しますが
ここでは時間の効率性に注目します
どのように正確かつ効率的なアルゴリズムを作るかを
考えるため次の例を見てみましょう
これはPythonコードです
これはnaiveと名付けたルーチンです
機能はまだ教えません
aとbには非負の整数値を当てはめることができます
すると代入文が処理され
whileループが実行されます
少したつとzの値を返します
このアルゴリズムをよく見てください
これで何ができるかすぐには分からないと思いますが
Pythonで実行してみてください
適当な数値を入れて実行し
パターンを見いだせるか試してみてください
そしてその理由を考えてください
仮説を立てることができたら
このプログラムがどういう計算をして
仮説のような計算結果に
たどり着くのかを考えてください
皆さんにやってもらいたいのは次のクイズです
このプログラムのaやbに数値を入れて実行した結果を
aとbを使って表すとどのようになるでしょうか
aまたはbいずれか大きい方の数値でしょうか
a-bでしょうか それともb-aでしょうか
それともa+bでしょうか
またはa×bでしょうか