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

Commita6a4d01

Browse files
feat: added ukranian translations for graph, heap, linked-list, priority-queue, queue, stack. trie (trekhleb#965)
1 parent025b9a3 commita6a4d01

File tree

14 files changed

+313
-14
lines changed

14 files changed

+313
-14
lines changed

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,9 @@ _Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
55
[_Русский_](README.ru-RU.md),
66
[_Français_](README.fr-FR.md),
7-
[_Português_](README.pt-BR.md)
7+
[_Português_](README.pt-BR.md),
8+
[_Українська_](README.uk-UA.md)
9+
810

911
In computer science, a**graph** is an abstract data type
1012
that is meant to implement the undirected graph and
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
#Граф
2+
3+
**Граф** в інформатиці - абстрактний тип даних, який має реалізовувати концепції спрямованого та неспрямованого
4+
графа у математиці, особливо у галузі теорії графів.
5+
6+
Структура даних графа складається з кінцевого (і можливо, що змінюється) набору вершин або вузлів, або точок, спільно з
7+
набором ненаправлених пар цих вершин для ненаправленого графа або набором спрямованих пар для спрямованого графа.
8+
Ці пари відомі як ребра, арки або лінії для ненаправленого графа та як стрілки, спрямовані ребра, спрямовані
9+
арки чи спрямовані лінії для спрямованого графа. Ці вершини можуть бути частиною структури графа, або зовнішніми
10+
сутностями, представленими цілими індексами або посиланнями.
11+
12+
Для різних областей застосування види графів можуть відрізнятися спрямованістю, обмеженнями на кількість зв'язків та
13+
додатковими даними про вершини або ребра. Багато структур, що становлять практичний інтерес у математиці та
14+
інформатики можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою
15+
орієнтованого графа, в якому вершини – це статті, а дуги (орієнтовані ребра) – гіперпосилання.
16+
17+
![Граф](./images/graph.jpeg)
18+
19+
*Made with[okso.app](https://okso.app)*
20+
21+
##Посилання
22+
23+
-[Граф у математиці на Wikipedia](https://uk.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0))
24+
-[Структура даних Graph / Граф](https://www.youtube.com/watch?v=D0U8aFEhgKQ)

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,9 @@ _Read this in other languages:_
77
[_Français_](README.fr-FR.md),
88
[_Português_](README.pt-BR.md),
99
[_Türkçe_](README.tr-TR.md),
10-
[_한국어_](README.ko-KR.md)
10+
[_한국어_](README.ko-KR.md),
11+
[_Українська_](README.uk-UA.md)
12+
1113

1214
In computer science, a**heap** is a specialized tree-based
1315
data structure that satisfies the heap property described
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
#Купа (структура даних)
2+
3+
У комп'ютерних науках купа - це спеціалізована структура даних на кшталт дерева, яка задовольняє властивості купи:
4+
якщо B є вузлом-нащадком вузла A, то ключ (A) ≥ ключ (B). З цього випливає, що елемент із найбільшим ключем завжди
5+
є кореневим вузлом купи, тому іноді такі купи називають max-купами.
6+
7+
![MaxHeap](./images/max-heap.jpeg)
8+
9+
![Array Representation](./images/array-representation.jpeg)
10+
11+
Якщо порівняння перевернути, то найменший елемент завжди буде кореневим вузлом, такі купи називають min-купами.
12+
13+
![MinHeap](./images/min-heap.jpeg)
14+
15+
*Made with[okso.app](https://okso.app)*
16+
17+
Не існує жодних обмежень щодо того, скільки вузлів-нащадків має кожен вузол купи. На практиці їх
18+
число зазвичай трохи більше двох. Купа є максимально ефективною реалізацією абстрактного типу даних, який
19+
називається чергою із пріоритетом.
20+
21+
Вузол на вершині купи, який не має батьків, називається кореневим вузлом.
22+
23+
##Посилання
24+
25+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%9A%D1%83%D0%BF%D0%B0_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%B8%D1%85))

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ _Read this in other languages:_
88
[_한국어_](README.ko-KR.md),
99
[_Español_](README.es-ES.md),
1010
[_Turkish_](README.tr-TR.md),
11+
[_Українська_](README.uk-UA.md)
1112

1213
In computer science, a**linked list** is a linear collection
1314
of data elements, in which linear order is not given by
Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
#Зв'язаний список
2+
3+
Зв'язаний список — базова динамічна структура даних в інформатиці, що складається з вузлів, кожен з яких містить як дані, так посилання («зв'язку») на наступний вузол списку. Дана структура дозволяє ефективно додавати та видаляти елементи на довільній позиції у послідовності у процесі ітерації. Більш складні варіанти включають додаткові посилання, що дозволяють ефективно додавати та видаляти довільні елементи.
4+
5+
Принциповою перевагою перед масивом є структурна гнучкість: порядок елементів зв'язкового списку може збігатися з порядком розташування елементів даних у пам'яті комп'ютера, а порядок обходу списку завжди явно задається його внутрішніми зв'язками. Суть переваги у тому, що у багатьох мовах створення масиву вимагає вказати його заздалегідь. Зв'язковий список дозволяє обійти це обмеження.
6+
7+
Недоліком зв'язкових списків є те, що час доступу є лінійним (і важко для реалізації конвеєрів). Неможливий швидкий доступ (випадковий).
8+
9+
![Linked List](./images/linked-list.jpeg)
10+
11+
*Made with[okso.app](https://okso.app)*
12+
13+
##Псевдокод основних операцій
14+
15+
###Вставка
16+
17+
```text
18+
Add(value)
19+
Pre: value - значення, що додається
20+
Post: value поміщено в кінець списку
21+
n ← node(value)
22+
if head = ø
23+
head ← n
24+
tail ← n
25+
else
26+
tail.next ← n
27+
tail ← n
28+
end if
29+
end Add
30+
```
31+
32+
```text
33+
Prepend(value)
34+
Pre: value - значення, що додається
35+
Post: value поміщено на початок списку
36+
n ← node(value)
37+
n.next ← head
38+
head ← n
39+
if tail = ø
40+
tail ← n
41+
end
42+
end Prepend
43+
```
44+
45+
###Поиск
46+
47+
```text
48+
Contains(head, value)
49+
Pre: head - перший вузол у списку
50+
value - значення, яке слід знайти
51+
Post: true - value знайдено у списку, інакше false
52+
n ← head
53+
while n != ø and n.value != value
54+
n ← n.next
55+
end while
56+
if n = ø
57+
return false
58+
end if
59+
return true
60+
end Contains
61+
```
62+
63+
###Вилучення
64+
65+
```text
66+
Remove(head, value)
67+
Pre: head - перший вузол у списку
68+
value - значення, яке слід видалити
69+
Post: true - value видалено зі списку, інакше false
70+
if head = ø
71+
return false
72+
end if
73+
n ← head
74+
if n.value = value
75+
if head = tail
76+
head ← ø
77+
tail ← ø
78+
else
79+
head ← head.next
80+
end if
81+
return true
82+
end if
83+
while n.next != ø and n.next.value != value
84+
n ← n.next
85+
end while
86+
if n.next != ø
87+
if n.next = tail
88+
tail ← n
89+
end if
90+
n.next ← n.next.next
91+
return true
92+
end if
93+
return false
94+
end Remove
95+
```
96+
97+
###Обход
98+
99+
```text
100+
Traverse(head)
101+
Pre: head - перший вузол у списку
102+
Post: елементи списку пройдені
103+
n ← head
104+
while n != ø
105+
yield n.value
106+
n ← n.next
107+
end while
108+
end Traverse
109+
```
110+
111+
###Зворотний обхід
112+
113+
```text
114+
ReverseTraversal(head, tail)
115+
Pre: head и tail відносяться до одного списку
116+
Post: елементи списку пройдено у зворотному порядку
117+
if tail != ø
118+
curr ← tail
119+
while curr != head
120+
prev ← head
121+
while prev.next != curr
122+
prev ← prev.next
123+
end while
124+
yield curr.value
125+
curr ← prev
126+
end while
127+
yield curr.value
128+
end if
129+
end ReverseTraversal
130+
```
131+
132+
##Складність
133+
134+
###Тимчасова складність
135+
136+
| Читання| Пошук| Вставка| Вилучення|
137+
| :--------:| :-------:| :--------:| :-------:|
138+
| O(n)| O(n)| O(1)| O(n)|
139+
140+
###Просторова складність
141+
142+
O(n)
143+
144+
##Посилання
145+
146+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%97%D0%B2%27%D1%8F%D0%B7%D0%B0%D0%BD%D0%B8%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA)
147+
-[YouTube](https://www.youtube.com/watch?v=6snsMa4E1Os)

‎src/data-structures/priority-queue/README.md

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -6,20 +6,21 @@ _Read this in other languages:_
66
[_日本語_](README.ja-JP.md),
77
[_Français_](README.fr-FR.md),
88
[_Português_](README.pt-BR.md),
9-
[_한국어_](README.ko-KR.md)
9+
[_한국어_](README.ko-KR.md),
10+
[_Українська_](README.uk-UA.md)
1011

11-
In computer science, a**priority queue** is an abstract data type
12-
which is like a regular queue or stack data structure, but where
13-
additionally each element has a "priority" associated with it.
14-
In a priority queue, an element with high priority is served before
15-
an element with low priority. If two elements have the same
12+
In computer science, a**priority queue** is an abstract data type
13+
which is like a regular queue or stack data structure, but where
14+
additionally each element has a "priority" associated with it.
15+
In a priority queue, an element with high priority is served before
16+
an element with low priority. If two elements have the same
1617
priority, they are served according to their order in the queue.
1718

18-
While priority queues are often implemented with heaps, they are
19-
conceptually distinct from heaps. A priority queue is an abstract
19+
While priority queues are often implemented with heaps, they are
20+
conceptually distinct from heaps. A priority queue is an abstract
2021
concept like "a list" or "a map"; just as a list can be implemented
2122
with a linked list or an array, a priority queue can be implemented
22-
with a heap or a variety of other methods such as an unordered
23+
with a heap or a variety of other methods such as an unordered
2324
array.
2425

2526
##References
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#Черга з пріоритетом
2+
3+
Черга з пріоритетом (англ. priority queue) - абстрактний тип даних в інформатиці,
4+
для кожного елемента якого можна визначити його пріоритет.
5+
6+
У черзі з пріоритетами елемент із високим пріоритетом обслуговується раніше
7+
елемент з низьким пріоритетом. Якщо два елементи мають однаковий пріоритет, вони
8+
обслуговуються відповідно до їх порядку в черзі.
9+
10+
Черга з пріоритетом підтримує дві обов'язкові операції – додати елемент та
11+
витягти максимум (мінімум).
12+
13+
Хоча пріоритетні черги часто реалізуються у вигляді куп (heaps), вони
14+
концептуально відрізняються від куп. Черга пріоритетів є абстрактною
15+
концепцією на кшталт «списку» чи «карти»; так само, як список може бути реалізований
16+
у вигляді зв'язкового списку або масиву, так і черга з пріоритетом може бути реалізована
17+
у вигляді купи або безліччю інших методів, наприклад, у вигляді невпорядкованого масиву.
18+
19+
##Посилання
20+
21+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%A7%D0%B5%D1%80%D0%B3%D0%B0_%D0%B7_%D0%BF%D1%80%D1%96%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BE%D0%BC)

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,8 @@ _Read this in other languages:_
66
[_日本語_](README.ja-JP.md),
77
[_Français_](README.fr-FR.md),
88
[_Português_](README.pt-BR.md),
9-
[_한국어_](README.ko-KR.md)
9+
[_한국어_](README.ko-KR.md),
10+
[_Українська_](README.uk-UA.md)
1011

1112
In computer science, a**queue** is a particular kind of abstract data
1213
type or collection in which the entities in the collection are
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#Черга
2+
3+
Черга (англ. queue) – структура даних в інформатиці, в якій елементи
4+
зберігаються у порядку їх додавання. Додавання нових елементів(enqueue)
5+
здійснюється на кінець списку. А видалення елементів (dequeue)
6+
здійснюється із початку. Таким чином черга реалізує принцип
7+
"першим увійшов – першим вийшов" (FIFO). Часто реалізується операція читання
8+
головного елемента (peek), яка повертає перший у черзі елемент,
9+
при цьому не видаляючи його. Черга є прикладом лінійної структури
10+
даних чи послідовної колекції.
11+
12+
Ілюстрація роботи з чергою.
13+
14+
![Черга](./images/queue.jpeg)
15+
16+
*Made with[okso.app](https://okso.app)*
17+
18+
##Список літератури
19+
20+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%A7%D0%B5%D1%80%D0%B3%D0%B0_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%B8%D1%85))
21+
-[YouTube](https://www.youtube.com/watch?v=ll4QLNSPn60)

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,8 @@ _Read this in other languages:_
66
[_日本語_](README.ja-JP.md),
77
[_Français_](README.fr-FR.md),
88
[_Português_](README.pt-BR.md),
9-
[_한국어_](README.ko-KR.md)
9+
[_한국어_](README.ko-KR.md),
10+
[_Українська_](README.uk-UA.md)
1011

1112
In computer science, a**stack** is an abstract data type that serves
1213
as a collection of elements, with two principal operations:
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
#Стек
2+
3+
Стек (англ. stack - стопка) - абстрактний тип даних, що представляє собою
4+
список елементів, організованих за принципом LIFO (останнім прийшов – першим вийшов).
5+
6+
Стек має дві ключові операції:
7+
***додавання (push)** елемента в кінець стеку, та
8+
***видалення (pop)**, останнього доданого елемента.
9+
10+
Додаткова операція для читання головного елемента (peek) дає доступ
11+
до останнього елементу стека без зміни самого стека.
12+
13+
Найчастіше принцип роботи стека порівнюють зі чаркою тарілок: щоб узяти другу
14+
зверху потрібно зняти верхню.
15+
16+
Ілюстрація роботи зі стеком.
17+
18+
![Стек](./images/stack.jpeg)
19+
20+
*Made with[okso.app](https://okso.app)*
21+
22+
##Посилання
23+
24+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BA)
25+
-[YouTube](https://www.youtube.com/watch?v=4jh1e1YCbYc)

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,8 @@
33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
55
[_Русский_](README.ru-RU.md),
6-
[_Português_](README.pt-BR.md)
6+
[_Português_](README.pt-BR.md),
7+
[_Українська_](README.uk-UA.md)
78

89
In computer science, a**trie**, also called digital tree and sometimes
910
radix tree or prefix tree (as they can be searched by prefixes),
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#Префіксне дерево
2+
3+
**Префіксне дерево** (Також промінь, навантажене або суфіксне дерево) в інформатиці - впорядкована деревоподібна
4+
структура даних, яка використовується для зберігання динамічних множин або асоціативних масивів, де
5+
ключем зазвичай виступають рядки. Дерево називається префіксним, тому що пошук здійснюється за префіксами.
6+
7+
На відміну від бінарного дерева, вузли не містять ключів, що відповідають вузлу. Являє собою кореневе дерево, кожне
8+
ребро якого позначено якимось символом так, що для будь-якого вузла всі ребра, що з'єднують цей вузол з його синами,
9+
позначені різними символами. Деякі вузли префіксного дерева виділені (на малюнку вони підписані цифрами) і вважається,
10+
що префіксне дерево містить цей рядок-ключ тоді і тільки тоді, коли цей рядок можна прочитати на шляху з
11+
кореня до певного виділеного вузла.
12+
13+
Таким чином, на відміну від бінарних дерев пошуку, ключ, що ідентифікує конкретний вузол дерева, не явно зберігається в
14+
цьому вузлі, а неявно задається положенням цього вузла в дереві. Отримати ключ можна виписуванням поспіль символів,
15+
помічають ребра по дорозі від кореня до вузла. Ключ кореня дерева - порожній рядок. Часто у виділених вузлах зберігають
16+
додаткову інформацію, пов'язану з ключем, і зазвичай виділеними є тільки листя і, можливо, деякі
17+
внутрішні вузли.
18+
19+
![Префіксне дерево](./images/trie.jpg)
20+
21+
*Made with[okso.app](https://okso.app)*
22+
23+
На малюнку представлено префіксне дерево, що містить ключі. «A», «to», «tea», «ted», «ten», «i», «in», «inn».
24+
25+
##Посилання
26+
27+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D1%96%D0%BA%D1%81%D0%BD%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE)

0 commit comments

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