Pratica di Shadowing: What Is Dynamic Programming and How To Use It - Impara a parlare inglese con i video

Scegli una modalità di pratica

Ogni modalità apre una sala di pratica a schermo intero.

175 frasi
Se le frasi sono troppo corte o troppo lunghe, clicca su Edit per modificarle.
1
Hey CSDojo, it's YK here.
2
So in this video I'm going to talk about what dynamic programming is
3
and how to use it and as I explain how it works I'm going to assume that you're already familiar with recursion.
4
So what is dynamic programming exactly?
5
It's actually fairly simple even though it might sound difficult
6
It's basically a way of making your algorithm more efficient by storing some of the intermediate results
7
And it works really well when your algorithm has a lot of repetitive computations
8
So that you don't have to repeat those computations over and over again and
9
I'm gonna give you a concrete example of how it works with Fibonacci sequence
10
So just in case you're not familiar with it Fibonacci sequence is a sequence of numbers
11
that starts with two ones at the beginning and Each number after that is computed by adding up the two previous numbers
12
So the third Fibranch number is 2 because 1 plus 1 equals 2
13
And then the fourth Fibranch number is 3
14
because 1 plus 2 equals 3 and so on and this sequence keeps on going forever
15
So let's say we're trying to solve the problem of finding the n's Fibranch number
16
or writing a function called Fib of n
17
Which takes a positive integer n and finds and returns the n's Fibranch number
18
So if the given n is 3
19
We want to be able to find and return the third free lunch number, which is 2
20
And if the given n is 5, we want to be able to return the fifth free lunch number, which is 5
21
Let's see how we can solve this problem using dynamic programming
22
So if you want to solve a problem using dynamic programming, there are typically three steps you can take
23
The first step is to come up with a recursive solution to your problem
24
And then in your recursive solution, if you notice that there are a lot of repeated computations
25
You can then store some of the intermediate results so that you don't have to repeat those computations
26
This process is also called
27
Memoization or memoize and this is not to be confused with Memorize
28
and I've made that mistake before too and then the third step if you don't like using recursion anymore is
29
To come up with something called a bottom -up approach
30
So let's first see what a recursive solution might look like for this particular problem
31
So as I said earlier, we're going to write a function called fib of n
32
Which takes n a positive integer and returns the nth fibranche number
33
And if n is equal to 1 or 2
34
We know that the first and the second fibranche numbers are 1
35
We're going to return 1
36
But instead of returning it right away
37
We're going to store it in a temporary variable called the result and then return that instead.
38
And it's going to be clear why we need to do that later.
39
And if n is neither 1 nor 2, then we're going to return the sum of the two previous Fibonacci numbers instead.
40
Fib of n minus 1 plus Fib of n minus 2, store that in result, and then return it at the end.
41
So this solution works, but it's very very inefficient.
42
To see why, let's see an example where we are trying to find the fifth Fibonacci number by calling Fibonacci 5.
43
So to find the return value of Fibonacci 5,
44
we need to first compute the return values for Fibonacci 4 and Fibonacci 3 so we can add them up.
45
And to find Fibonacci 4, we need to first compute Fibonacci 3 and Fibonacci 2 and so on.
46
And that's what this diagram shows.
47
And looking at this diagram, you might notice that there are some competitions that we repeat over and over again.
48
For example, we need to compute the return value for Fibonacci 3 times,
49
and we need to compute the return value for Fibonacci 3 twice here.
50
And it's not a big deal when we are trying to find the 5th or 6th Fibonacci number,
51
but if we're trying to find the 100th Fibonacci number, it becomes an issue.
52
And actually the time it takes to find the n's Fibonacci number grows exponentially
53
Or roughly in the order of 2 to the power of n
54
And dynamic programming here says why not just store those return values
55
For example for Fibonacci 3 store the return value once we compute it
56
And then use that same value when we see Fibonacci 3 again instead of computing it again
57
And again, this process is called memoization.
58
So let's see what a memoized solution looks like in code
59
Let's again consider the example where we're trying to find the fifth few months number by calling Fib of 5
60
The idea of this solution is going to be that we're going to use an array whose length is
61
n plus 1 or 6 in this particular case
62
because n here is 5 and then we're going to store the return value for the functional fib of n.
63
at the index n.
64
So we're going to store fib of 1, which is the first fib of number right here at index 1,
65
and then fib of 2 at index 2, and so on.
66
And initially we're going to set all these values to null.
67
And we're going to write our function fib, and this is going to take two arguments instead of just one.
68
The first one is the same as before, n, a positive integer, and the second one is going to be this array
69
and so you'll need to initialize this array memo before you call this function.
70
Now at the beginning of this function, check if memo at index n is null or not.
71
If it's not equal to null, that'll mean that we've already seen this argument n and we've
72
We've already stored the return value for that at the index n in memo, so just return that instead
73
So return memo square brackets n
74
Otherwise, the following part is the same as before
75
If n is equal to 1 or 2, return 1, store 1 in result, and then return that at the end
76
And if that's not the case, then find the sum of the two previous equivalent numbers, and then return that instead
77
And then what's new in this function is that before you return this result, the return value
78
You need to store it in Memo at index n so that you can use it later
79
Let's now think about the time complexity for this solution.
80
We're going to call it t of n
81
This is going to be the time it takes to find the n's Fibonacci number with this particular method and
82
we're going to find that by multiplying the number of times we call this function,
83
fib, with the time it takes to execute each of those calls.
84
We're going to call that t.
85
Now, there are only two ways we're going to call this function fib.
86
The first way is when we call this function for the first time with the arguments n
87
and memo to find the entropy bunch number, and the second way is from this line right here,
88
and And notice that if you look at this whole block after this first if clause,
89
this whole block is only executed at most n times.
90
And this is true because there are n possible arguments to this function.
91
That's 1 through n.
92
And each time this function is called with each of those arguments, the return value will be stored in memo at index n.
93
So after the first time this function is called with each argument, we'll never get to this block.
94
And each time this block is executed, fib is called a most twice if we get to this line.
95
So the number of times fib is called is a most 2 times n plus 1.
96
So 2n comes from this block right here, and 1 comes from the first time we call this function fib and
97
the time it takes to execute each of those calls this t right here is
98
Going to be a constant time or a big O of 1
99
and this is because if you look at each operation in this function excluding
100
These recursive calls that follow each operation is a constant time operation and when you have a constant time operation
101
when you add them up, you still get a constant time operation, which is big O of 1.
102
And that's why we have big O of 1 here.
103
And so t of n, or the time it takes to find the n -spin -onage number with this particular method,
104
is going to be 2n plus 1 times big O of 1, which is big O of 2n plus 1,
105
which is equal to big O of n.
106
and this is a huge improvement from what we had earlier
107
which was big O of 2 to the power of n
108
and let's now examine how this memo array is actually filled
109
so let's say we're trying to find the fifth Fibonacci number again
110
and when we call fib with the argument 5
111
and memo of course we'll see
112
that we don't have a stored value at the index 5 yet
113
so we go down and we're gonna to ask ourselves what's the value of Fib of 4
114
and then 3 and so on and when we get to Fib of 2
115
we'll know that this value is 1 so we're going to store it at index 2 right here,
116
and same with Fibon1, that's 1 right here, and once we have these two values, we'll be able to find the third Fibonacci number,
117
which is Fibon3 right here, and then once we find the value by adding them up,
118
store that value right here so we can use it later, and then when we go up to Fibon4,
119
we'll add 1 and 2 right here and we get 3
120
and so on until we get here and
121
so as you can see this array is mostly filled from left to right so
122
when you see this you might say why not just explicitly build
123
this array from left to right from scratch instead of building it recursively
124
and that's the idea behind a bottom -up approach
125
so let's see what a bottom -up approach might look like in code
126
we're going to define a function called fib bottom up
127
which takes n a positive integer just like before
128
and returns the nth Fibonacci number and then
129
if n is equal to 1 or 2 of course we're going to return 1 and after
130
that we're going to define an array whose length is going
131
to be n plus 1 where n plus 1 is 6 of course
132
if we're trying to find the fifth Fibonacci number right here
133
if n is equal to 5 and after
134
that we're going to set the first and the second elements of this array bottom -up to be 1, these two items right here,
135
and then we're going to run a for loop for i from 3, which corresponds to this item right here,
136
up to n, and n corresponds to the last item right here of this array,
137
and whatever index we're examining currently we're going to set
138
that element at the index i
139
or bottom up square brackets i to be the sum of the two previous items
140
so in this particular example we'll have two here three here
141
and after that we're going to return the last item in bottom up
142
or bottom up square brackets n
143
and we're done the time complexity for this algorithm will be again big o of n
144
because we're going to define this array and go through this array only once
145
Okay, so that's how dynamic programming works
146
But now I'm gonna show you a quick demo with Python
147
and something called Jupyter Notebook to show you how this idea might play out in practice
148
So in this Jupyter Notebook, I have defined a few functions in Python Fib of n which is a recursive naive recursive solution and
149
Fib of memo and fib of 2 which represent a memoized solution and 5th bottom -up, which is of course a bottom -up solution.
150
So let's see how they compare to each other in performance
151
We're gonna try running fib of n first the naive recursive solution with fib of 5 and
152
That gives us 5 which is expected.
153
What about fib of 20?
154
That gives us the answer pretty quickly, too.
155
And what about fib of 35?
156
This actually takes 5 to 6 seconds on my computer
157
So it's obviously not the most efficient approach.
158
Let's see how fib of two and fib of memo the memoized solution compares to that
159
Let's try running fifth memo of five firsts and that gives us five which is expected
160
And what about fifth memo 35?
161
That's pretty quick, too.
162
And what about fifth memo 100 and 1000
163
This actually gives us an error and this error is called the recursion error
164
Python gives us this error actually because there are too many recursive calls on a call stack and
165
To fix that we can just use the bottom -up approach
166
One advantage of using a bottom -up approach is that we don't have to put any recursive calls on a call stack
167
So we don't have to worry about that.
168
So we're going to load this function and then run it with the argument 35
169
Which is pretty quick 1000 and then let's try 10 ,000 as well
170
And that's pretty instantaneous, too.
171
Okay, so that's my introduction to dynamic programming.
172
Let me know in the comment section below what you thought of this video,
173
and if you have any requests about what kind of videos I should make in the future,
174
let me know in the comment section below as well.
175
I'm YK from CSDojo, and I'll see you in the next video.

Scarica l'app

Tutto ciò che serve per parlare fluentemente

Pronuncia con IAVoto per ogni frase
Pratica IPAPadroneggia ogni suono
VocabolarioCostruisci il tuo lessico
Gioco di vocabolarioImpara giocando

Stesso Canale

FOR YOU

Video consigliato

Vocabolario e note di pronuncia per questa lezione

Questa lezione di conversazione si basa sul video “What Is Dynamic Programming and How To Use It”. Le parole che ritornano più spesso: fib, return, Fibonacci, value, function. Questo video contiene 175 frasi e 2286 parole da ripetere con lo shadowing. Il parlato dura 14:27. Chi parla ha un ritmo naturale di circa 158 parole al minuto, vicino a una conversazione quotidiana. Il 85% delle parole rientra nelle 3.000 più comuni dell’inglese; conviene studiare le altre prima di iniziare.

Vocaboli chiave di questo video

15 parole del video che vale la pena imparare, con pronuncia e significato:

ParolaPronunciaSignificato
array sostantivo/əˈɹeɪ/abbigliamento, agghindamento
dynamic aggettivo/daɪˈnæm.ɪk/dinamico
sequence sostantivo/ˈsiː.kwəns/sequenza
define verbo/dɪˈfaɪn/definire, determinare
execute verbo/ˈɛksɪˌkjuːt/giustiziare
solve verbo/sɒlv/risolvere
algorithm sostantivo/ˈælɡəɹɪðm̩/algoritmo
bracket sostantivo/ˈbɹækɪt/staffa
element sostantivo/ˈɛləmənt/elemento
compare verbo/kəmˈpɛɚ/paragonare
efficient aggettivo/ɪˈfɪʃənt/efficiente, performante
examine verbo/ɪɡˈzæmɪn/esaminare
stack sostantivo/stæk/pila, bica
intermediate aggettivo/ɪn.tə(ɹ)ˈmi.di.ət/intermedio
complexity sostantivo/kəmˈplɛk.sɪ.ti/complessità

I phrasal verb che sentirai

ParolaSignificato
come up with verboideare, escogitare
add up verbosommarsi
go through verboattraversare

La grammatica di questo video

Le strutture che chi parla usa di più, con le parole esatte del video:

StrutturaNel video
Forma passiva be + participio passato — conta ciò che accade, non chi lo fais computed · is also called · is called
Present perfect have/has + participio passato — un’azione passata che conta ancora adessoI've made · we've already seen · We've already stored
Frasi relative who / which + frase — un’informazione in più su una persona o una cosanumber, which is · operation, which is · five which is

Pronuncia a cui fare attenzione

Chi parla usa 62 contrazioni e forme ridotte, come we're, don't, we'll. Pronunciale nella forma breve, così come le senti.

  • I suoni “sh” e “zh”: efficient /ɪˈfɪʃənt/, computation /ˌkɑmpjʊˈteɪʃn̩/, recursion /ɹɪˈkɜː(ɹ)ʒən/, memoization /ˌmɛmoʊaɪˈzeɪʃən/, exponentially /ɛkspə(ʊ)ˈnɛnʃəli/
  • Parole lunghe — attenzione all’accento: intermediate /ɪn.tə(ɹ)ˈmi.di.ət/, complexity /kəmˈplɛk.sɪ.ti/, temporary /ˈtɛmp(əˌɹ)ɛɹi/, repetitive /ɹɪˈpɛtɪtɪv/, memoization /ˌmɛmoʊaɪˈzeɪʃən/

I suoni difficili per chi parla italiano:

  • Consonante finale — senza aggiungere una vocale dopo: dynamic /daɪˈnæm.ɪk/, sequence /ˈsiː.kwəns/, execute /ˈɛksɪˌkjuːt/, solve /sɒlv/, bracket /ˈbɹækɪt/
  • /æ/ — più aperta della “e”: dynamic /daɪˈnæm.ɪk/, algorithm /ˈælɡəɹɪðm̩/, bracket /ˈbɹækɪt/, examine /ɪɡˈzæmɪn/, stack /stæk/

Come esercitarsi con questo video

  1. Ascolta tutto il video una volta senza parlare e annota le parole che non conosci.
  2. Inizia a velocità 0,75×, fai shadowing frase per frase e torna alla velocità normale quando diventa facile.
  3. Registrati e confronta con l’originale, facendo attenzione a parole come array, dynamic, sequence.

Cos'è la tecnica dello Shadowing?

Shadowing è una tecnica di apprendimento delle lingue supportata da studi scientifici, originariamente sviluppata per la formazione dei traduttori professionisti e resa popolare dal poliglotta Dr. Alexander Arguelles. Il metodo è semplice ma potente: ascolti un audio in inglese di madrelingua e lo ripeti immediatamente ad alta voce — come un'ombra che segue il parlante con un ritardo di solo 1–2 secondi. A differenza dell'ascolto passivo o degli esercizi di grammatica, lo shadowing costringe il tuo cervello e i muscoli della bocca a elaborare e riprodurre simultaneamente i modelli di discorso reale. La ricerca dimostra che migliora significativamente la precisione della pronuncia, l'intonazione, il ritmo, il discorso connesso, la comprensione dell'ascolto e la fluidità del parlato — rendendolo uno dei metodi più efficaci per la preparazione alla prova di speaking dell'IELTS e per la comunicazione reale in inglese.

Tecnica dello shadowing: leggi la guida completa passo dopo passo →