{"draftJsState":{"blocks":[{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"3asot"},{"data":{"image":{"id":"63d4f7ac138f071bbd33df5b"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"1upov"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"В программировании алгоритм — это набор инструкций для решения конкретной проблемы или достижения конкретной задачи. Алгоритмы могут быть написаны на любом языке программирования и могут быть как простыми (последовательность основных операций), так и сложными (многоэтапный процесс, включающий различные структуры данных и логику). Основная цель алгоритма — принять входные данные, обработать их и предоставить ожидаемый результат. Алгоритмы можно классифицировать на основе временной и пространственной сложности, метода, используемого для решения проблемы, и типа решаемой проблемы. Примерами алгоритмов являются сортировка, поиск, обход графа, манипуляции со строками, математические операции и многое другое.","type":"unstyled","key":"2cgh4"},{"data":{},"depth":0,"entityRanges":[{"key":0,"length":28,"offset":0}],"inlineStyleRanges":[],"text":"@ai_machinelearning_big_data - машинное обучение в телеграмме.","type":"unstyled","key":"dc6po"},{"data":{},"depth":0,"entityRanges":[{"key":1,"length":39,"offset":0}],"inlineStyleRanges":[],"text":"Алгоритмы, о которых мы будем говорить:","type":"unstyled","key":"d9umh"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Алгоритмы сортировки. Сортировка является фундаментальной операцией в компьютерных науках, и для неё существует несколько эффективных алгоритмов, таких как быстрая сортировка, сортировка слиянием и пирамидальная сортировка.","type":"unordered-list-item","key":"8hemu"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Алгоритмы поиска. Поиск элемента в большом наборе данных — распространенная задача, и для неё существует несколько эффективных алгоритмов, таких как бинарный поиск и хеш-таблицы.","type":"unordered-list-item","key":"a9nkb"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Алгоритмы графов. Алгоритмы графов используются для решения задач, связанных с графами, таких как поиск кратчайшего пути между двумя узлами или определение связности графа.","type":"unordered-list-item","key":"dr6ld"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Динамическое программирование. Динамическое программирование — это метод решения проблем путем их разбиения на более мелкие подзадачи и сохранения решений этих подзадач во избежание избыточных вычислений.","type":"unordered-list-item","key":"d8ra"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Жадные алгоритмы. Жадные алгоритмы используются для решения задач оптимизации, делая локально оптимальный выбор на каждом шаге.","type":"unordered-list-item","key":"5ur9p"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Разделяй и властвуй. Разделяй и властвуй — это парадигма разработки алгоритма, основанная на многоветвящейся рекурсии. Алгоритм «разделяй и властвуй» разбивает проблему на подзадачи того же или родственного типа, пока они не станут достаточно простыми, чтобы их можно было решить напрямую.","type":"unordered-list-item","key":"4499q"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Поиск с возвратом. Это общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.","type":"unordered-list-item","key":"5i44u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рандомизированный алгоритм: Рандомизированные алгоритмы используют случайность для решения проблемы. Это может быть полезно для решения проблем, которые не могут быть решены детерминистически, или для повышения средней сложности задачи.","type":"unordered-list-item","key":"qb90"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Эти алгоритмы широко используются в различных приложениях, и программисту важно хорошо их понимать. Поэтому я постараюсь объяснить их.","type":"unstyled","key":"286c4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"1. Алгоритмы сортировки","type":"header-two","key":"u2se"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":18,"offset":0,"style":"BOLD"}],"text":"Быстрая сортировка: Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает «основной» элемент из массива и разбивает остальные элементы на два подмассива. Затем подмассивы сортируются рекурсивно.","type":"unstyled","key":"adhe9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def quicksort(arr):\n if len(arr) <= 1:\n return arr\n pivot = arr[len(arr) // 2]\n left = [x for x in arr if x < pivot]\n middle = [x for x in arr if x == pivot]\n right = [x for x in arr if x > pivot]\n return quicksort(left) + middle + quicksort(right)\n\nprint(quicksort([3,6,8,10,1,2,1]))","type":"unstyled","key":"ctqr4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Сортировка слиянием: Алгоритм сортировки слиянием — это алгоритм «разделяй и властвуй», который делит массив на две части, сортирует две половины, а затем снова объединяет их.","type":"unstyled","key":"4m538"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def merge_sort(arr):\n if len(arr) <= 1:\n return arr\n mid = len(arr) // 2\n left = merge_sort(arr[:mid])\n right = merge_sort(arr[mid:])\n return merge(left, right)\n\ndef merge(left, right):\n result = []\n i = 0\n j = 0\n while i < len(left) and j < len(right):\n if left[i] < right[j]:\n result.append(left[i])\n i += 1\n else:\n result.append(right[j])\n j += 1\n result += left[i:]\n result += right[j:]\n return result\nprint(merge_sort([3,6,8,10,1,2,1]))","type":"unstyled","key":"ehc4s"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":24,"offset":0,"style":"BOLD"}],"text":"Пирамидальная сортировка: Пирамидальная сортировка — это алгоритм сортировки на основе сравнения, который строит пирамиду из входных элементов, а затем многократно извлекает её максимальный элемент и помещает его в конец отсортированного выходного массива.","type":"unstyled","key":"c53i8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def heap_sort(arr):\n n = len(arr)\n for i in range(n, -1, -1):\n heapify(arr, n, i)\n for i in range(n-1, 0, -1):\n arr[i], arr[0] = arr[0], arr[i]\n heapify(arr, i, 0)\n\ndef heapify(arr, n, i):\n largest = i\n l = 2 * i + 1\n r = 2 * i + 2\n if l < n and arr[i] < arr[l]:\n largest = l\n if r < n and arr[largest] < arr[r]:\n largest = r\n if largest != i:\n arr[i], arr[largest] = arr[largest], arr[i]\n heapify(arr, n, largest)\nprint(heap_sort([3,6,8,10,1,2,1]))","type":"unstyled","key":"5gc1q"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"2. Алгоритмы поиска","type":"header-two","key":"5lijl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":14,"offset":0,"style":"BOLD"}],"text":"Бинарный поиск: Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном списке. Он работает путем многократного деления пополам искомой части массива, пока не будет найдено искомое значение.","type":"unstyled","key":"2u23i"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def binary_search(arr, x):\n low = 0\n high = len(arr) - 1\n mid = 0\n while low <= high:\n mid = (high + low) // 2\n if arr[mid] < x:\n low = mid + 1\n elif arr[mid] > x:\n high = mid - 1\n else:\n return mid\n return -1\nprint(binary_search([1,2,3,4,5,6,7], 4))","type":"unstyled","key":"au0k9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":11,"offset":0,"style":"BOLD"}],"text":"Хеш-таблицы: Хэш-таблица — это структура данных, которая сопоставляет ключи со значениями, используя хеш-функцию для вычисления индекса в массиве сегментов или слотов, из которых можно найти желаемое значение.","type":"unstyled","key":"8ojgi"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"class HashTable:\n def __init__(self):\n self.size = 10\n self.keys = [None] * self.size\n self.values = [None] * self.size\n\n def put(self, key, data):\n index = self.hash_function(key)\n while self.keys[index] is not None:\n if self.keys[index] == key:\n self.values[index] = data # update\n return\n index = (index + 1) % self.size\n self.keys[index] = key\n self.values[index] = data\n\n def get(self, key):\n index = self.hash_function(key)\n while self.keys[index] is not None:\n if self.keys[index] == key:\n return self.values[index]\n index = (index + 1) % self.size\n return None\n\n def hash_function(self, key):\n sum = 0\n for pos in range(len(key)):\n sum = sum + ord(key[pos])\n return sum % self.size\n\nt = HashTable()\nt.put(\"apple\", 10)\nt.put(\"orange\", 20)\nt.put(\"banana\", 30)\nprint(t.get(\"orange\"))","type":"unstyled","key":"b6bgv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"3. Графический алгоритм","type":"header-two","key":"6d2u4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":17,"offset":0,"style":"BOLD"}],"text":"Алгоритм Дейкстры: Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути между узлами в графе.","type":"unstyled","key":"b0lks"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"import heapq\n\ndef dijkstra(graph, start):\n heap = [(0, start)]\n visited = set()\n while heap:\n (cost, v) = heapq.heappop(heap)\n if v not in visited:\n visited.add(v)\n for u, c in graph[v].items():\n if u not in visited:\n heapq.heappush(heap, (cost + c, u))\n return visited\n\ngraph = {\n 'A': {'B': 2, 'C': 3},\n 'B': {'D': 4, 'E': 5},\n 'C': {'F': 6},\n 'D': {'G': 7},\n 'E': {'G': 8, 'H': 9},\n 'F': {'H': 10},\n 'G': {},\n 'H': {}\n}\nprint(dijkstra(graph, 'A'))","type":"unstyled","key":"15rul"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"4. Динамическое программирование","type":"header-two","key":"13gvf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":28,"offset":0,"style":"BOLD"}],"text":"Последовательность Фибоначчи: Классическим примером проблемы, которую можно решить с помощью динамического программирования, является последовательность Фибоначчи.","type":"unstyled","key":"36ne8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def fibonacci(n):\n if n <= 0:\n return 0\n elif n == 1:\n return 1\n else:\n return fibonacci(n-1) + fibonacci(n-2)\n \n \nprint(fibonacci(10))","type":"unstyled","key":"r6cq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"5. Жадне алгоритмы","type":"header-two","key":"456dm"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":20,"offset":0,"style":"BOLD"}],"text":"Кодирование Хаффмана: Кодирование Хаффмана — это алгоритм сжатия данных, который формулирует основную идею сжатия файлов.","type":"unstyled","key":"ae2j7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"from collections import Counter, namedtuple\n\ndef huffman_encoding(data):\n \"\"\"\n Generates a Huffman encoded string of the input data\n \"\"\"\n # Create a frequency counter for the data\n freq_counter = Counter(data)\n # Create a namedtuple for the Huffman tree nodes\n HuffmanNode = namedtuple(\"HuffmanNode\", [\"char\", \"freq\"])\n # Create a priority queue for the Huffman tree\n priority_queue = PriorityQueue()\n # Add all characters to the priority queue\n for char, freq in freq_counter.items():\n priority_queue.put(HuffmanNode(char, freq))\n # Combine nodes until only the root node remains\n while priority_queue.qsize() > 1:\n left_node = priority_queue.get()\n right_node = priority_queue.get()\n combined_freq = left_node.freq + right_node.freq\n combined_node = HuffmanNode(None, combined_freq)\n priority_queue.put(combined_node)\n # Generate the Huffman code for each character\n huffman_code = {}\n generate_code(priority_queue.get(), \"\", huffman_code)\n # Encode the input data\n encoded_data = \"\"\n for char in data:\n encoded_data += huffman_code[char]\n return encoded_data, huffman_code\nprint(huffman_encoding(\"aaaaabbbcccc\"))","type":"unstyled","key":"cnj4a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"6. Разделяй и властвуй","type":"header-two","key":"3g7po"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":19,"offset":0,"style":"BOLD"}],"text":"Сортировка слиянием: уже была объяснена выше…","type":"unstyled","key":"dr1t2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"7. Поиск с возвратом","type":"header-two","key":"1nqgl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":17,"offset":0,"style":"BOLD"}],"text":"Проблема N-ферзей. Проблема N-ферзей — это классическая проблема, которую можно решить с помощью поиска с возвратом. Цель состоит в том, чтобы разместить N-ферзей на шахматной доске NxN таким образом, чтобы ни один ферзь не мог атаковать другого ферзя.","type":"unstyled","key":"88pv6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def solveNQueens(n):\n def could_place(row, col):\n # check if a queen can be placed on board[row][col]\n # check if this row is not under attack from any previous queen in that column\n for i in range(row):\n if board[i] == col or abs(board[i] - col) == abs(i - row):\n return False\n return True\n\ndef backtrack(row=0, count=0):\n for col in range(n):\n if could_place(row, col):\n board[row] = col\n if row + 1 == n:\n count += 1\n else:\n count = backtrack(row + 1, count)\n return count\n board = [-1 for x in range(n)]\n return backtrack()\nprint(solveNQueens(4))","type":"unstyled","key":"argt8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Этот алгоритм начинает размещать фигуры в первом ряду и для каждого размещённого ферзя проверяет, не атакован ли он каким-либо предыдущим ферзём. Если нет, он переходит к следующей строке и повторяет процесс. Если ферзь находится в позиции, где он подвергается атаке, алгоритм отступает и пробует другую позицию. Это продолжается до тех пор, пока все ферзи не будут размещены на доске, не атакуя друг друга.","type":"unstyled","key":"esguf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"8. Рандомизированный алгоритм","type":"header-two","key":"1jitq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":36,"offset":0,"style":"BOLD"}],"text":"Рандомизированная быстрая сортировка: вариант алгоритма быстрой сортировки, в котором точка опоры выбирается случайным образом.","type":"unstyled","key":"9pi9e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"import random\n\ndef randomized_quicksort(arr):\n if len(arr) <= 1:\n return arr\n pivot = random.choice(arr)\n left = [x for x in arr if x < pivot]\n middle = [x for x in arr if x == pivot]\n right = [x for x in arr if x > pivot]\n return randomized_quicksort(left) + middle + randomized_quicksort(right)\n\nprint(randomized_quicksort([3,6,8,10,1,2,1]))","type":"unstyled","key":"cccku"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Это некоторые из наиболее часто используемых алгоритмов, с которыми должен быть знаком каждый программист. Понимание этих алгоритмов и их реализации может помочь программисту принимать лучшие решения, когда речь идет о разработке и реализации эффективных решений.","type":"unstyled","key":"9s4r1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"Jj8ia1rfQefJqBOz2s0Y"}],"entityMap":{"0":{"data":{"url":"http://t.me/ai_machinelearning_big_data"},"mutability":"MUTABLE","type":"LINK"},"1":{"data":{"url":"https://uproger.com/8-luchshih-algoritmov-python/"},"mutability":"MUTABLE","type":"LINK"}}},"mentions":[]}