-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy path1-PythonED.txt
159 lines (131 loc) · 9.2 KB
/
1-PythonED.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
@fmasanori
about.me/fmasanori
github.com/fmasanori/ED
bit.ly/PythonED
Eu amo Estrutura de Dados. Apresentação para iniciantes! Se você acredita que isso é possível, venha curtir uma pequena amostra de códigos e discussões apaixonadas. Recursão. Vetores. Pilhas e Filas. Algoritmos de Ordenação: inserção, seleção, mergesort, quicksort. Algoritmos de Enumeração. Boyer-Moore. Teoria dos Grafos. Deixe seus traumas e venha ser feliz.
@Ver a "alma" do código à luz dos dados
Algoritmos e Estruturas de Dados na prática
-Amar mais a programação <3
-Soluções melhores para os problemas
-Processos seletivos
-Decisões de arquitetura
@Porque Python?
"the most common fault in computer classes is to emphasize the rules of specific programming languages, instead of to emphasize the algorithms that are being expressed in those languages. It's bad to dwell on form over substance" [Donald E. Knuth, People of ACM Interview]
"Programming is best regarded as the process of creating works of literature, which are meant to be read." [Donald E. Knuth, Literate Programming]
"A atividade de programação deve ser encarada como um processo de criação de obras de literatura, escritas para serem lidas."
"to be read by humans first and machines next" [Donald E. Knuth, People of ACM Interview]
@Busca Binária
"Binary search is to algorithms what a wheel is to mechanics: It is simple, elegant, and immensely important." [Udi Manber, Introduction to Algorithms]
"Busca binária é para algoritmos o que a roda é para a mecânica: ela é simples, elegante, e enormemente importante."
"Binary search is a notoriously tricky algorithm to program correctly. It took seventeen years after its invention until the first correct version of binary search was published!" [Steven Skiena, The Algorithm Design Manual]
"Busca binária é um algoritmo notoriamente difícil de programar corretamente. Somente dezessete anos depois da invenção do algoritmo a primeira versão correta do programa foi publicada!"
-Imaginem que tenho uma lista, em ordem alfabética, de todos os participantes da conferência. Uma lista com várias folhas... E que quero ver se um nome está na lista.
-A abordagem mais natural é, dada a primeira letra do nome, procurar no meio da lista. Muito mais eficaz do que ver nome por nome, desde o início.
-Essa abordagem custa log(n, 2) passos. Para ter uma ideia, se tivermos um milhão de itens, demoramos apenas 20 passos para a busca.
@Ver a "alma" do código
"You don't have to believe in God, but you should believe in The Book." [Paul Erdös]
-Sendo ateu, Paul Erdos se referia a um Livro imaginário, onde Deus teria escrito as demonstrações mais elegantes de todos os teoremas
-Demonstrações de Paul Erdos geraram inúmeros algoritmos, principalmente na área de Análise Combinatória e Teoria dos Grafos
-No mestrado trabalhei com o Problema dos Uns Consecutivos, que tem aplicações em Sequenciamento de DNA, especificamente Mapeamento Físico de DNA
-Numa matriz de zeros e uns, será que existe uma permutação de linhas, onde as colunas ficam com uns consecutivos?
-Usando o método Extensão Rotação, para detecção de Circuitos Hamiltonianos, junto com um algoritmo guloso, para o Problema dos Conjuntos Independentes, consegui a aproximação mais rápida para o problema
@Mergesort
-Merge = intercalar
-Imaginem que você tem duas fileiras de crianças em ordem crescente de altura
-Para ordenar uma fileira geral, vejo a primeira criança de cada fileira e vou passando para o início da nova fileira
-Como inicio o processo?
-Vou montando pares de crianças em ordem
-Depois quadruplas etc, dobrando a cada passo
-Número ímpar não é problema
@Mergesort interativo
-Rolo compressor que vai juntando fileiras
-Fileiras começam com tamanho 1
-São geradas fileiras de tamanho 2 ordenadas
-Tamanho 4, 8, 16...
-Num determinado passo o vetor está ordenado
-Algoritmos "enrolado", pois a vocação do dado é recursiva
@Mergesort recursivo
-O número de passos na recursão é log(n, 2) pois a "alma" é a mesma que o algoritmo de busca binária
-Cada merge compara todo mundo
-Custo total: n * log(n, 2)
-As partes são independentes, podemos fazê-las em paralelo
-No intercala podemos usar um método online
@Nem todo algoritmo recursivo é eficiente
"A Computação se apoia sobre três pernas: a correção, a eficiência e a elegância." [Imre Simon]
Correção: cumpre o prometido, ou seja, se faz o que promete fazer. Eficiente: não perde tempo à toa. Elegante: simples, limpo e econômico.
@Fibonacci recursivo
-Vemos que repetimos várias vezes valores de n já calculados
-Podemos resolver com um dicionário
-Ou usando lru_cache
-Usar uma Estrutura de Dados tornou nosso algoritmo eficiente
@Expressão bem formada usando Pilhas
-Empilho todos os abres
-Se é um fecha, verifico no topo da pilha se "casa"
-Caso positivo desempilha
-Se sobrou alguém no final não é bem formada
@Distâncias entre um nó e o resto da rede
-A matriz mostra se há caminho de um nó para outro
-Quero calcular o vetor de distâncias
-Enfilero a origem
-Enquanto a fila não está vazia
-Vejo quais nós eu chego e que nunca passei antes
-A distância é +1 em relação ao nó anterior
@Um bom algoritmo é uma faca afiada
"A good algorithm is like a sharp knife: it does what it is supposed to do with a minimum amount of applied effort. Using the wrong algorithm to solve a problem is like trying to cut a steak with a screwdriver: you may eventually get a digestible result, but you will expend considerably more effort than necessary, and the result is unlikely to be aesthetically pleasing." [Th. Cormen, Ch. Leiserson, R. Rivest, Introduction to Algorithms]
"Um bom algoritmo é como uma faca afiada: ele faz o que dele se espera com o mínima de esforço. Usar um algoritmo errado para resolver um problema é como tentar cortar um bife com uma chave de fenda: você pode até mesmo conseguir um resultado aceitável, mas você gastará muito mais esforço que o necessário e é pouco provável que o resultado será esteticamente agradável."
@Boyer Moore
-Busca de uma palavra em um texto
-Trecho de DNA numa sequência
-Trecho de código na memória ou disco
-Buscar sequencialmente obriga a andar de um em um
-Posso aproveitar a palavra (usar o Dado que tenho)
-Expliquei Estrutura de Dados e especialmente Boyer Moore para um amigo físico, gostou tanto que fez pós na Computação e hoje é docente do IME USP
Os algoritmos de ordenação
algoritmo
@Codificar algo simples é difícil
"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." [C.A.R.Hoare]
@Quicksort
-Quero colocar todo mundo em ordem
-Escolho um voluntário
-Metade menor vai para um lado e o resto para o outro
-O voluntário estará na posição definitiva
-Repito o processo para cada lado
-Vou dobrar a cada passo o número de elementos "certos"
-Pior caso é encontrar todo mundo já em ordem
-Porém isso é raro, então, na prática funciona bem
@Dois algoritmos com número de passos proporcionais no pior caso, na média podem ser diferentes
"As famílias felizes parecem-se todas; as famílias infelizes são infelizes cada uma à sua maneira." [Anna Kariênina]
@Inserção e Seleção
-Ambos são n**2 passos no pior caso
-No entanto, inserção olha para o lado direito, ordenado
-Números grandes não movimentam muito o lado direito
-Seleção olha o menor do lado esquerdo
-Logo não há caso bom, só ruins
@Força Bruta, Backtracking, Enumeração
"Often it appears that there is no better way to solve a problem than to try all possible solutions. This approach, called exhaustive search, is almost always slow, but sometimes it is better than nothing." [Ian Parberry, Problems on Algorithms]
"Muitas vezes não há maneira melhor de resolver um problema que tentar todas as possíveis soluções. Esta abordagem, chamada busca exaustiva, é quase sempre lenta, mas às vezes ela é melhor que nada."
@Arthur Merlim Games
-Rei Arthur passa dois problemas para o Mago Merlim
-Se todas as damas irão casar, dado suas preferências
-Se é possível colocar os cavaleiros em torno da Távola Redonda, com a condição de não sentarem do lado de alguém que não gostem
-O problema das damas exige gerar todos os subconjuntos, para verificar se os "queridos" do subconjunto estão em menor número
-O problema dos cavaleiros exige achar um Circuito Hamiltoniano
-Os dois problemas são bem diferentes, não só no tempo, mas em achar um obstrução
@Heurística Gulosa por Vértice de Grau Mínimo
-Sejam substâncias químicas
-Se elas reagem perigosamente, possuem uma ligação
-Quero o maior conjunto que não reaja entre si
-Problema difícil
-Aproximação por busca gulosa
-Vejo o vértice de grau mínimo
-Retiro os vizinhos
-Repito até o grafo sumir
Outros links:
https://wiki.python.org/moin/TimeComplexity
https://github.com/keon/algorithms
https://github.com/donnemartin/interactive-coding-challenges
https://github.com/LambdaSchool/Data-Structures
https://github.com/bt3gl/Python-and-Algorithms-and-Data-Structures
https://github.com/marcosfede/algorithms
https://github.com/anubhavshrimal/Data-Structures-Algorithms
https://github.com/ivankliuk/coursera-data-structures-algorithms