Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commited99f9d

Browse files
themgoncalvestrekhleb
authored andcommitted
Adds Portuguese (pt-BR) translation (trekhleb#340)
* create portuguese translations* renames `Lista Ligada` to `Lista Encadeada`* revert changes on package-lock.json
1 parent1520533 commited99f9d

35 files changed

+1111
-63
lines changed

‎README.pt-BR.md

Lines changed: 17 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -29,23 +29,23 @@ os dados.
2929

3030
`B` - Iniciante,`A` - Avançado
3131

32-
*`B`[Linked List](src/data-structures/linked-list)
33-
*`B`[Doubly Linked List](src/data-structures/doubly-linked-list)
34-
*`B`[Queue](src/data-structures/queue)
35-
*`B`[Stack](src/data-structures/stack)
36-
*`B`[Hash Table](src/data-structures/hash-table)
37-
*`B`[Heap](src/data-structures/heap)
38-
*`B`[Priority Queue](src/data-structures/priority-queue)
39-
*`A`[Trie](src/data-structures/trie)
40-
*`A`[Tree](src/data-structures/tree)
41-
*`A`[Binary Search Tree](src/data-structures/tree/binary-search-tree)
42-
*`A`[AVL Tree](src/data-structures/tree/avl-tree)
43-
*`A`[Red-Black Tree](src/data-structures/tree/red-black-tree)
44-
*`A`[Segment Tree](src/data-structures/tree/segment-tree) - com exemplos de consultas min / max / sum range
45-
*`A`[Fenwick Tree](src/data-structures/tree/fenwick-tree) (Árvore indexada binária)
46-
*`A`[Graph](src/data-structures/graph) (ambos dirigidos e não direcionados)
47-
*`A`[Disjoint Set](src/data-structures/disjoint-set)
48-
*`A`[Bloom Filter](src/data-structures/bloom-filter)
32+
*`B`[Lista Encadeada (Linked List)](src/data-structures/linked-list.pt-BR)
33+
*`B`[Lista Duplamente Ligada (Doubly Linked List)](src/data-structures/doubly-linked-list.pt-BR)
34+
*`B`[Fila (Queue)](src/data-structures/queue.pt-BR)
35+
*`B`[Stack](src/data-structures/stack.pt-BR)
36+
*`B`[Tabela deHash(HashTable)](src/data-structures/hash-table.pt-BR)
37+
*`B`[Heap](src/data-structures/heap.pt-BR)
38+
*`B`[Fila de Prioridade (Priority Queue)](src/data-structures/priority-queue.pt-BR)
39+
*`A`[Trie](src/data-structures/trie.pt-BR)
40+
*`A`[Árvore (Tree)](src/data-structures/tree.pt-BR)
41+
*`A`[Árvore de Pesquisa Binária (Binary Search Tree)](src/data-structures/tree/binary-search-tree.pt-BR)
42+
*`A`[ÁrvoreAVL(AVLTree)](src/data-structures/tree/avl-tree.pt-BR)
43+
*`A`[Árvore Vermelha-Preta (Red-Black Tree)](src/data-structures/tree/red-black-tree.pt-BR)
44+
*`A`[Árvore de Segmento (Segment Tree)](src/data-structures/tree/segment-tree.pt-BR) - com exemplos de consultas min / max / sum range
45+
*`A`[ÁrvoreFenwick(FenwickTree)](src/data-structures/tree/fenwick-tree.pt-BR) (Árvore indexada binária)
46+
*`A`[Gráfico (Graph)](src/data-structures/graph.pt-BR) (ambos dirigidos e não direcionados)
47+
*`A`[Conjunto Disjuntor (Disjoint Set)](src/data-structures/disjoint-set.pt-BR)
48+
*`A`[FiltroBloom(BloomFilter)](src/data-structures/bloom-filter.pt-BR)
4949

5050
##Algoritmos
5151

‎src/data-structures/bloom-filter/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
#Bloom Filter
22

33
_Read this in other languages:_
4-
[_Русский_](README.ru-RU.md)
4+
[_Русский_](README.ru-RU.md) |[_Português_](README.pt-BR.md)
55

66
A**bloom filter** is a space-efficient probabilistic
77
data structure designed to test whether an element
Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
#Filtro Bloom (Bloom Filter)
2+
3+
_Leia em outro idioma:_
4+
[_English_](README.md) |[_Русский_](README.ru-RU.md)
5+
6+
O**bloom filter** é uma estrutura de dados probabilística
7+
espaço-eficiente designada para testar se um elemento está
8+
ou não presente em um conjunto de dados. Foi projetado para ser
9+
incrivelmente rápido e utilizar o mínimo de memória ao
10+
potencial custo de um falso-positivo. Correspondências
11+
_falsas positivas_ são possíveis, contudo_falsos negativos_
12+
não são - em outras palavras, a consulta retorna
13+
"possivelmente no conjunto" ou "definitivamente não no conjunto".
14+
15+
Bloom propôs a técnica para aplicações onde a quantidade
16+
de entrada de dados exigiria uma alocação de memória
17+
impraticavelmente grande se as "convencionais" técnicas
18+
error-free hashing fossem aplicado.
19+
20+
##Descrição do algoritmo
21+
22+
Um filtro Bloom vazio é um_bit array_ de`m` bits, todos
23+
definidos como`0`. Também deverá haver diferentes funções
24+
de hash`k` definidas, cada um dos quais mapeia e produz hash
25+
para um dos elementos definidos em uma das posições`m` da
26+
_array_, gerando uma distribuição aleatória e uniforme.
27+
Normalmente,`k` é uma constante, muito menor do que`m`,
28+
pelo qual é proporcional ao número de elements a ser adicionado;
29+
a escolha precisa de`k` e a constante de proporcionalidade de`m`
30+
são determinadas pela taxa de falsos positivos planejado do filtro.
31+
32+
Aqui está um exemplo de um filtro Bloom, representando o
33+
conjunto`{x, y, z}`. As flechas coloridas demonstram as
34+
posições no_bit array_ em que cada elemento é mapeado.
35+
O elemento`w` não está definido dentro de`{x, y, z}`,
36+
porque este produz hash para uma posição de array de bits
37+
contendo`0`. Para esta imagem:`m = 18` e`k = 3`.
38+
39+
![Bloom Filter](https://upload.wikimedia.org/wikipedia/commons/a/ac/Bloom_filter.svg)
40+
41+
##Operações
42+
43+
Existem duas operações principais que o filtro Bloom pode operar:
44+
_inserção_ e_pesquisa_. A pesquisa pode resultar em falsos
45+
positivos. Remoção não é possível.
46+
47+
Em outras palavras, o filtro pode receber itens. Quando
48+
vamos verificar se um item já foi anteriormente
49+
inserido, ele poderá nos dizer "não" ou "talvez".
50+
51+
Ambas as inserções e pesquisas são operações`O(1)`.
52+
53+
##Criando o filtro
54+
55+
Um filtro Bloom é criado ao alocar um certo tamanho.
56+
No nosso exemplo, nós utilizamos`100` como tamanho padrão.
57+
Todas as posições são initializadas como`false`.
58+
59+
###Inserção
60+
61+
Durante a inserção, um número de função hash, no nosso caso`3`
62+
funções de hash, são utilizadas para criar hashes de uma entrada.
63+
Estas funções de hash emitem saída de índices. A cada índice
64+
recebido, nós simplismente trocamos o valor de nosso filtro
65+
Bloom para`true`.
66+
67+
###Pesquisa
68+
69+
Durante a pesquisa, a mesma função de hash é chamada
70+
e usada para emitir hash da entrada. Depois nós checamos
71+
se_todos_ os indices recebidos possuem o valor`true`
72+
dentro de nosso filtro Bloom. Caso_todos_ possuam o valor
73+
`true`, nós sabemos que o filtro Bloom pode ter tido
74+
o valor inserido anteriormente.
75+
76+
Contudo, isto não é certeza, porque é possível que outros
77+
valores anteriormente inseridos trocaram o valor para`true`.
78+
Os valores não são necessariamente`true` devido ao ítem
79+
atualmente sendo pesquisado. A certeza absoluta é impossível,
80+
a não ser que apenas um item foi inserido anteriormente.
81+
82+
Durante a checagem do filtro Bloom para índices retornados
83+
pela nossa função de hash, mesmo que apenas um deles possua
84+
valor como`false`, nós definitivamente sabemos que o ítem
85+
não foi anteriormente inserido.
86+
87+
##Falso Positivos
88+
89+
A probabilidade de falso positivos é determinado por
90+
três fatores: o tamanho do filtro de Bloom, o número de
91+
funções de hash que utilizados, e o número de itens que
92+
foram inseridos dentro do filtro.
93+
94+
A formula para calcular a probabilidade de um falso positivo é:
95+
96+
( 1 - e <sup>-kn/m</sup> ) <sup>k</sup>
97+
98+
`k` = número de funções de hash
99+
100+
`m` = tamanho do filtro
101+
102+
`n` = número de itens inserido
103+
104+
Estas variáveis,`k`,`m` e`n`, devem ser escolhidas baseado
105+
em quanto aceitável são os falsos positivos. Se os valores
106+
escolhidos resultam em uma probabilidade muito alta, então
107+
os valores devem ser ajustados e a probabilidade recalculada.
108+
109+
##Aplicações
110+
111+
Um filtro Bloom pode ser utilizado em uma página de Blog.
112+
Se o objetivo é mostrar aos leitores somente os artigos
113+
em que eles nunca viram, então o filtro Bloom é perfeito
114+
para isso. Ele pode armazenar hashes baseados nos artigos.
115+
Depois que um usuário lê alguns artigos, eles podem ser
116+
inseridos dentro do filtro. Na próxima vez que o usuário
117+
visitar o Blog, aqueles artigos poderão ser filtrados (eliminados)
118+
do resultado.
119+
120+
Alguns artigos serão inevitavelmente filtrados (eliminados)
121+
por engano, mas o custo é aceitável. Tudo bem se um usuário nunca
122+
ver alguns poucos artigos, desde que tenham outros novos
123+
para ver toda vez que eles visitam o site.
124+
125+
126+
##Referências
127+
128+
-[Wikipedia](https://en.wikipedia.org/wiki/Bloom_filter)
129+
-[Bloom Filters by Example](http://llimllib.github.io/bloomfilter-tutorial/)
130+
-[Calculating False Positive Probability](https://hur.st/bloomfilter/?n=4&p=&m=18&k=3)
131+
-[Bloom Filters on Medium](https://blog.medium.com/what-are-bloom-filters-1ec2a50c68ff)
132+
-[Bloom Filters on YouTube](https://www.youtube.com/watch?v=bEmBh1HtYrw)

‎src/data-structures/disjoint-set/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
#Disjoint Set
22

33
_Read this in other languages:_
4-
[_Русский_](README.ru-RU.md)
4+
[_Русский_](README.ru-RU.md) |[_Português_](README.pt-BR.md)
5+
56

67
**Disjoint-set** data structure (also called a union–find data structure or merge–find set) is a data
78
structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#Conjunto Disjuntor (Disjoint Set)
2+
3+
_Leia em outro idioma:_
4+
[_English_](README.md) |[_Русский_](README.ru-RU.md)
5+
6+
**Conjunto Disjuntor**
7+
8+
**Conjunto Disjuntor** é uma estrutura de dados (também chamado de
9+
estrutura de dados de union–find ou merge–find) é uma estrutura de dados
10+
que rastreia um conjunto de elementos particionados em um número de
11+
subconjuntos separados (sem sobreposição).
12+
Ele fornece operações de tempo quase constante (limitadas pela função
13+
inversa de Ackermann) para*adicionar novos conjuntos*, para
14+
*mesclar/fundir conjuntos existentes* e para*determinar se os elementos
15+
estão no mesmo conjunto*.
16+
Além de muitos outros usos (veja a seção Applications), conjunto disjuntor
17+
desempenham um papel fundamental no algoritmo de Kruskal para encontrar a
18+
árvore geradora mínima de um gráfico (graph).
19+
20+
21+
![disjoint set](https://upload.wikimedia.org/wikipedia/commons/6/67/Dsu_disjoint_sets_init.svg)
22+
23+
*MakeSet* cria 8 singletons.
24+
25+
![disjoint set](https://upload.wikimedia.org/wikipedia/commons/a/ac/Dsu_disjoint_sets_final.svg)
26+
27+
Depois de algumas operações de*Uniões*, alguns conjuntos são agrupados juntos.
28+
29+
##Referências
30+
31+
-[Wikipedia](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
32+
-[By Abdul Bari on YouTube](https://www.youtube.com/watch?v=wU6udHRIkcc&index=14&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎src/data-structures/doubly-linked-list/README.md

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,7 @@
11
#Doubly Linked List
22

33
_Read this in other languages:_
4-
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md),
6-
[_日本語_](README.ja-JP.md)
4+
[_Русский_](README.ru-RU.md) |[_简体中文_](README.zh-CN.md) |[_日本語_](README.ja-JP.md) |[_Português_](README.pt-BR.md)
75

86
In computer science, a**doubly linked list** is a linked data structure that
97
consists of a set of sequentially linked records called nodes. Each node contains
Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
#Lista Duplamente Ligada (Doubly Linked List)
2+
3+
_Leia em outro idioma:_
4+
[_English_](README.md) |[_简体中文_](README.zh-CN.md) |[_Русский_](README.ru-RU.md)
5+
6+
Na ciência da computação, uma**lista duplamente conectada** é uma estrutura
7+
de dados vinculada que se consistem em um conjunto de registros
8+
sequencialmente vinculados chamados de nós (nodes). Em cada nó contém dois
9+
campos, chamados de ligações, que são referenciados ao nó anterior e posterior
10+
de uma sequência de nós. O começo e o fim dos nós anteriormente e posteiormente
11+
ligados, respectiviamente, apontam para algum tipo de terminação, normalmente
12+
um nó sentinela ou nulo, para facilitar a travessia da lista. Se existe
13+
somente um nó sentinela, então a lista é ligada circularmente através do nó
14+
sentinela. Ela pode ser conceitualizada como duas listas individualmente ligadas
15+
e formadas a partir dos mesmos itens, mas em ordem sequencial opostas.
16+
17+
![Doubly Linked List](https://upload.wikimedia.org/wikipedia/commons/5/5e/Doubly-linked-list.svg)
18+
19+
Os dois nós ligados permitem a travessia da lista em qualquer direção.
20+
Enquanto adicionar ou remover um nó de uma lista duplamente vinculada requer
21+
alterar mais ligações (conexões) do que em uma lista encadeada individualmente
22+
(singly linked list), as operações são mais simples e potencialmente mais
23+
eficientes (para nós que não sejam nós iniciais) porque não há necessidade
24+
de se manter rastreamento do nó anterior durante a travessia ou não há
25+
necessidade de percorrer a lista para encontrar o nó anterior, para que
26+
então sua ligação/conexão possa ser modificada.
27+
28+
##Pseudocódigo para Operações Básicas
29+
30+
###Inserir
31+
32+
```text
33+
Add(value)
34+
Pre: value is the value to add to the list
35+
Post: value has been placed at the tail of the list
36+
n ← node(value)
37+
if head = ø
38+
head ← n
39+
tail ← n
40+
else
41+
n.previous ← tail
42+
tail.next ← n
43+
tail ← n
44+
end if
45+
end Add
46+
```
47+
48+
###Deletar
49+
50+
```text
51+
Remove(head, value)
52+
Pre: head is the head node in the list
53+
value is the value to remove from the list
54+
Post: value is removed from the list, true; otherwise false
55+
if head = ø
56+
return false
57+
end if
58+
if value = head.value
59+
if head = tail
60+
head ← ø
61+
tail ← ø
62+
else
63+
head ← head.next
64+
head.previous ← ø
65+
end if
66+
return true
67+
end if
68+
n ← head.next
69+
while n = ø and value !== n.value
70+
n ← n.next
71+
end while
72+
if n = tail
73+
tail ← tail.previous
74+
tail.next ← ø
75+
return true
76+
else if n = ø
77+
n.previous.next ← n.next
78+
n.next.previous ← n.previous
79+
return true
80+
end if
81+
return false
82+
end Remove
83+
```
84+
85+
###Travessia reversa
86+
87+
```text
88+
ReverseTraversal(tail)
89+
Pre: tail is the node of the list to traverse
90+
Post: the list has been traversed in reverse order
91+
n ← tail
92+
while n = ø
93+
yield n.value
94+
n ← n.previous
95+
end while
96+
end Reverse Traversal
97+
```
98+
99+
##Complexidades
100+
101+
##Complexidade de Tempo
102+
103+
| Acesso| Pesquisa| Inserção| Remoção|
104+
| :-------:| :---------:| :------:| :------:|
105+
| O(n)| O(n)| O(1)| O(n)|
106+
107+
###Complexidade de Espaço
108+
109+
O(n)
110+
111+
##Referências
112+
113+
-[Wikipedia](https://en.wikipedia.org/wiki/Doubly_linked_list)
114+
-[YouTube](https://www.youtube.com/watch?v=JdQeNxWCguQ&t=7s&index=72&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎src/data-structures/graph/README.md

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,7 @@
11
#Graph
22

33
_Read this in other languages:_
4-
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md)
4+
[_简体中文_](README.zh-CN.md) |[_Русский_](README.ru-RU.md) |[_Português_](README.pt-BR.md)
65

76
In computer science, a**graph** is an abstract data type
87
that is meant to implement the undirected graph and
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
#Gráfico (Graph)
2+
3+
_Read this in other languages:_
4+
[_English_](README.md) |[_简体中文_](README.zh-CN.md) |[_Русский_](README.ru-RU.md)
5+
6+
Na ciência da computação, um**gráfico** é uma abstração de estrutura
7+
de dados que se destina a implementar os conceitos da matemática de
8+
gráficos direcionados e não direcionados, especificamente o campo da
9+
teoria dos gráficos.
10+
11+
Uma estrutura de dados gráficos consiste em um finito (e possivelmente
12+
mutável) conjunto de vértices, nós ou pontos, juntos com um
13+
conjunto de pares não ordenados desses vértices para um gráfico não
14+
direcionado ou para um conjunto de pares ordenados para um gráfico
15+
direcionado. Esses pares são conhecidos como arestas, arcos
16+
ou linhas diretas para um gráfico não direcionado e como setas,
17+
arestas direcionadas, arcos direcionados ou linhas direcionadas
18+
para um gráfico direcionado.
19+
20+
Os vértices podem fazer parte a estrutura do gráfico, ou podem
21+
ser entidades externas representadas por índices inteiros ou referências.
22+
23+
![Graph](https://www.tutorialspoint.com/data_structures_algorithms/images/graph.jpg)
24+
25+
##Referências
26+
27+
-[Wikipedia](https://en.wikipedia.org/wiki/Graph_(abstract_data_type))
28+
-[Introduction to Graphs on YouTube](https://www.youtube.com/watch?v=gXgEDyodOJU&index=9&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
29+
-[Graphs representation on YouTube](https://www.youtube.com/watch?v=k1wraWzqtvQ&index=10&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp