KAN`ский блог Мысли вслух…
  • Мар
    8

    Вот простой пример алгоритма для решения задачи составления расписания:

    1. Определение входных данных:
      • Список задач, которые необходимо распределить по времени.
      • Доступные ресурсы или исполнители, которые могут выполнить эти задачи.
      • Ограничения и приоритеты для каждой задачи.
    2. Формализация задачи:
      • Представление задач и ресурсов в виде структур данных (например, списки, массивы, графы).
      • Определение ограничений, таких как время начала и завершения, зависимости между задачами и доступные ресурсы.
    3. Выбор алгоритма решения:
      • Выбор подходящего алгоритма в зависимости от характеристик задачи (например, генетические алгоритмы, жадные алгоритмы, локальные поиски).
    4. Разработка целевой функции:
      • Определение критериев оптимальности для расписания (например, минимизация времени выполнения, максимизация использования ресурсов).
    5. Реализация алгоритма:
      • Написание кода для алгоритма, который учитывает входные данные, ограничения и целевую функцию.
      • Применение операций добавления, перемещения и удаления задач для поиска оптимального расписания.
    6. Тестирование и оценка результатов:
      • Проведение тестирования алгоритма на различных входных данных.
      • Оценка качества полученных расписаний с точки зрения оптимальности и выполнения заданных ограничений.

    Пример псевдокода алгоритма на основе жадного подхода:

    def greedy_schedule(tasks, resources):
        sorted_tasks = sorted(tasks, key=lambda x: x['priority'], reverse=True)
        schedule = []
    
        for task in sorted_tasks:
            assigned = False
            for resource in resources:
                if resource['available_time'] >= task['duration']:
                    schedule.append((task['name'], resource['name']))
                    resource['available_time'] -= task['duration']
                    assigned = True
                    break
            if not assigned:
                schedule.append((task['name'], None))  # Маркируем задачу как невыполнимую
    
        return schedule
    
    # Пример входных данных: задачи и ресурсы
    tasks = [
        {'name': 'Task1', 'priority': 2, 'duration': 3},
        {'name': 'Task2', 'priority': 1, 'duration': 2},
        {'name': 'Task3', 'priority': 3, 'duration': 1},
        {'name': 'Task4', 'priority': 2, 'duration': 4},
    ]
    
    resources = [
        {'name': 'Resource1', 'available_time': 10},
        {'name': 'Resource2', 'available_time': 5},
        {'name': 'Resource3', 'available_time': 8},
    ]
    
    # Вызов функции для составления расписания
    schedule = greedy_schedule(tasks, resources)
    
    # Вывод полученного расписания
    for task, resource in schedule:
        if resource:
            print(f"Task '{task}' assigned to Resource '{resource}'")
        else:
            print(f"Task '{task}' cannot be assigned to any resource")
    

    Это лишь пример алгоритма для задачи составления расписания. Для более сложных задач могут потребоваться более сложные алгоритмы и методы оптимизации.

    No Comments
  • Мар
    8

    Вот перечень основных типов алгоритмов на графах:

    1. Алгоритмы обхода графа:
      • Обход в глубину (DFS)
      • Обход в ширину (BFS)
    2. Алгоритмы кратчайшего пути:
      • Алгоритм Дейкстры (Dijkstra)
      • Алгоритм Беллмана-Форда (Bellman-Ford)
      • Алгоритм Флойда-Уоршелла (Floyd-Warshall)
    3. Алгоритмы поиска минимального остовного дерева:
      • Алгоритм Прима (Prim)
      • Алгоритм Крускала (Kruskal)
    4. Алгоритмы нахождения кратчайшего пути в невзвешенном графе:
      • Поиск кратчайшего пути в невзвешенном графе (BFS)
    5. Алгоритмы нахождения потока максимальной пропускной способности:
      • Алгоритм Форда-Фалкерсона
      • Алгоритм Эдмондса-Карпа
    6. Алгоритмы поиска путей в графе:
      • Алгоритм A* (A-star)
      • Алгоритм поиска в ширину с ограничением глубины (DLS)
      • Алгоритм итеративного углубленного поиска (IDS)
    7. Алгоритмы поиска максимального потока в графе:
      • Алгоритм Эдмондса-Карпа
      • Алгоритм Диница
    8. Алгоритмы поиска минимального покрытия вершин графа:
      • Алгоритм Кёнига
    9. Алгоритмы сортировки топологического порядка:
      • Алгоритм Кана
      • Алгоритм Тарьяна
    10. Алгоритмы поиска кратчайших путей в ориентированном ациклическом графе (DAG):
      • Алгоритм Дейкстры (Dijkstra) (для графов без отрицательных ребер)
      • Алгоритм Беллмана-Форда (Bellman-Ford)
      • Алгоритм Топологической сортировки

    Это лишь обзор основных типов алгоритмов на графах, каждый из которых может иметь множество вариаций и модификаций в зависимости от конкретных задач.

    В дополнение к предыдущему списку, вот еще несколько типов алгоритмов на графах:

    1. Алгоритмы поиска клик в графе:
      • Полный перебор (например, алгоритм Брон-Кербош)
      • Методы на основе битовых масок
      • Рекурсивные алгоритмы
    2. Алгоритмы поиска гамильтонова цикла:
      • Полный перебор
      • Методы на основе бэктрекинга
      • Методы на основе генетических алгоритмов
    3. Алгоритмы нахождения разрезов в графе:
      • Алгоритм Форда-Фалкерсона
      • Алгоритмы минимального разреза графа
    4. Алгоритмы поиска сильно связных компонент:
      • Алгоритм Тарьяна
      • Алгоритм Косарайю
    5. Алгоритмы поиска мостов и точек сочленения:
      • Алгоритмы поиска мостов
      • Алгоритмы поиска точек сочленения
    6. Алгоритмы поиска пути с минимальной стоимостью в графе с ограничениями:
      • Алгоритм A* (A-star)
      • Алгоритмы поиска пути в графах с ограничениями
    7. Алгоритмы решения задач коммивояжера (TSP):
      • Полный перебор
      • Методы на основе динамического программирования
      • Методы на основе эвристик и метаэвристик (например, муравьиные алгоритмы, генетические алгоритмы)
    8. Алгоритмы оптимизации маршрутов:
      • Алгоритмы Дейкстры и Беллмана-Форда для поиска кратчайших путей
      • Методы на основе динамического программирования для оптимизации маршрутов
      • Эвристические алгоритмы оптимизации маршрутов

    Это лишь дополнительные типы алгоритмов на графах, которые могут использоваться для различных задач, таких как анализ сетей, маршрутизация, планирование маршрутов, оптимизация и многое другое.

    No Comments
  • Мар
    8

    Алгоритм Флойда-Уоршелла используется для нахождения кратчайших путей между всеми парами вершин во взвешенном ориентированном графе с положительными или отрицательными весами рёбер. Вот пример его реализации на Python:

    INF = float('inf')
    
    def floyd_warshall(graph):
        """
        Алгоритм Флойда-Уоршелла для поиска кратчайших путей между всеми парами вершин в графе.
        :param graph: взвешенный граф в виде матрицы смежности
        :return: матрица расстояний между всеми парами вершин
        """
        n = len(graph)
        dist = [[INF] * n for _ in range(n)]
    
        # Заполняем матрицу начальными значениями
        for i in range(n):
            for j in range(n):
                dist[i][j] = graph[i][j]
    
        # Проходим по всем вершинам и обновляем расстояния
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
        return dist
    
    # Пример графа в виде матрицы смежности
    graph = [
        [0, 3, INF, 7],
        [8, 0, 2, INF],
        [5, INF, 0, 1],
        [2, INF, INF, 0]
    ]
    
    # Выполняем алгоритм Флойда-Уоршелла
    result = floyd_warshall(graph)
    
    # Выводим результат
    print("Матрица кратчайших расстояний между всеми парами вершин:")
    for row in result:
        print(row)
    
    

    Этот код реализует алгоритм Флойда-Уоршелла для нахождения кратчайших путей между всеми парами вершин в графе. Входной параметр `graph` представляет собой взвешенный граф в виде матрицы смежности. Функция `floyd_warshall` возвращает матрицу расстояний между всеми парами вершин.

    No Comments
  • Мар
    8

    Ваш план изучения алгоритмов и структур данных на C++ может быть организован следующим образом:

    1. **Оценка текущих знаний и уровня**: Прежде чем начать учебный процесс, оцените свои текущие знания и понимание алгоритмов и структур данных на C++. Убедитесь, что вы уверены в базовых концепциях и основах C++, таких как указатели, ссылки, операторы, циклы и условные операторы.

    2. **Повторение основ**: Вспомните основы языка C++ и его стандартной библиотеки, такие как контейнеры (std::vector, std::list, std::map, std::set и т. д.) и алгоритмы (std::sort, std::find, std::binary_search и т. д.).

    3. **Изучение алгоритмов**: Начните с изучения основных алгоритмов, таких как сортировка (например, сортировка пузырьком, сортировка вставками, быстрая сортировка, сортировка слиянием), поиск (например, поиск в ширину, поиск в глубину, двоичный поиск), алгоритмы на графах (например, алгоритм Дейкстры, алгоритм Флойда-Уоршелла), алгоритмы динамического программирования и т. д.

    4. **Практические задания**: Решайте практические задачи, используя изученные алгоритмы. Можете использовать онлайн-платформы для решения задач, такие как LeetCode, Codeforces, HackerRank, и т. д.

    5. **Изучение структур данных**: После того как вы изучили основные алгоритмы, перейдите к изучению основных структур данных, таких как массивы, связанные списки, стеки, очереди, деревья (двоичные деревья поиска, AVL-деревья, красно-черные деревья), хеш-таблицы, кучи (пирамиды), графы и т. д.

    6. **Реализация и практика**: Реализуйте изученные структуры данных и алгоритмы самостоятельно на языке C++. Проанализируйте их сложность времени и пространства. Попробуйте решить различные задачи, используя эти структуры данных и алгоритмы.

    7. **Чтение и исследование**: Прочтите дополнительные материалы, книги и ресурсы о алгоритмах и структурах данных на C++. Исследуйте более сложные алгоритмы и их применение в реальных сценариях.

    8. **Проекты**: Работайте над проектами, которые требуют применения алгоритмов и структур данных. Это может быть разработка игр, веб-приложений, алгоритмических задач и т. д.

    9. **Обратная связь и улучшение**: Получайте обратную связь от других программистов, участвуйте в код-ревью и обсуждайте свой код. Постоянно стремитесь улучшить свои знания и навыки в области алгоритмов и структур данных.

    10. **Постоянное обучение**: Не останавливайтесь на достигнутом. Продолжайте изучать новые алгоритмы, практиковаться и совершенствовать свои навыки. Обмен опытом с другими программистами также может быть очень полезным.

    No Comments
  • Май
    1
    test os VM HT cores/threads result losses
    cinebench linux Kvm-def 8 4452 14.04%
    cinebench linux VirtualBox 8 4779 7.72%
    cinebench linux Kvm-def + 8 4873 5.91%
    cinebench linux VirtualBox + 8 4890 5.58%
    cinebench linux Kvm+cpu host + 8 5032 2.84%
    cinebench linux Kvm+libvirt + 8 5179 0.00%
    cinebench linux Kvm+libvirt + 12-24 8658 9.40%
    cinebench linux Kvm+libvirt 12 7619 20.27%
    cinebench windows VirtualBox + 8 4907 5.25%
    cinebench windows VirtualBox + 12-24 8287 13.28%
    cinebench windows VirtualBox 12 7164 25.03%
    cinebench windows windows + 12-24 9556 0.00%
    cinebench windows windows 12 7994 16.35%
    sysbench windows VirtualBox + 8 6808 4.25%
    sysbench windows VirtualBox + 12-24 10160 47.41%
    sysbench linux linux + 8 7110 0.00%
    sysbench linux linux + 12-24 19321 0.00%
    sysbench linux linux 12 10695 44.65%
    sysbench linux Kvm+libvirt + 8 7036 1.04%
    sysbench linux Kvm+libvirt + 12-24 18897 2.19%
    sysbench linux Kvm+libvirt 12 10530 45.50%
    sysbench linux VirtualBox + 8 6880 3.23%
    sysbench linux VirtualBox + 12-24 15358 20.51%
    sysbench linux VirtualBox 12 10195 47.23%

    cinebench R23
    Sysbench 1.20
    intel xeon e5-2673

     

    Выбор между KVM (Kernel-based Virtual Machine) и VirtualBox зависит от конкретных потребностей пользователя, однако многие аспекты говорят в пользу KVM.

    Во-первых, KVM — это гипервизор уровня ядра, интегрированный в ядро Linux, что позволяет ему работать очень близко к железу хост-системы. Это обеспечивает лучшую производительность и эффективное использование ресурсов системы. В отличие от VirtualBox, который работает поверх операционной системы и обладает некоторыми ограничениями, KVM имеет прямой доступ к аппаратному обеспечению, что делает его более производительным и гибким.

    Во-вторых, KVM предлагает более продвинутые функции управления виртуальными машинами, такие как динамическое изменение ресурсов, живая миграция и поддержка современных технологий виртуализации, таких как Intel VT-x и AMD-V. Эти возможности делают KVM более подходящим для развертывания в производственных средах и центрах обработки данных.

    Кроме того, KVM обеспечивает лучшую совместимость с различными операционными системами, включая Linux, Windows и другие Unix-подобные системы. Это делает его универсальным инструментом для виртуализации, который может быть использован в различных сценариях.

    Наконец, KVM является частью экосистемы Linux, что обеспечивает поддержку сообщества и доступ к обширному выбору инструментов и ресурсов. Это также означает, что KVM интегрирован с другими компонентами и технологиями Linux, что упрощает его использование в современных инфраструктурах.

    В целом, хотя VirtualBox может быть подходящим выбором для десктопной виртуализации и тестирования, KVM обеспечивает более высокую производительность, функциональность и совместимость, что делает его предпочтительным решением для серьезных проектов виртуализации и облачных вычислений.

    No Comments
  • Окт
    6

    Закралось, тут у меня сомнения относительно производительности операций создания и заполнения векторов, решил провестий простой тест, код ниже. Результаты несколько меня удивили:
    В Debug-mode:

    The above code block-1 was executed in 0.0500 second(s)
    The above code block-2 was executed in 44.5400 second(s)

    В Realese-mode:

    The above code block-1 was executed in 0.0440 second(s)
    The above code block-2 was executed in 0.1030 second(s)

    Каждый тест запускался по 10 раз, отображены средние результаты.
    Read the rest of this entry »

    Комментарии к записи Сравнение vector и простой массив int[] отключены
  • Июн
    4

    Решил намедни перетестировать и формализовать свою торговую стратегию, что из этого получилось смотрим ниже. Read the rest of this entry »

    Комментарии к записи Активные инвестиции, улучшаем результаты Марковица отключены
  • Апр
    20

    Практика и теория показала, что при самостоятельном инвестировании выбрать время входа, стоп, да и даже выбрать бумаги или прочие активы для инвестиций — задача очень и очень сложная. Конечно, данная задача имеет решение, но простому смертному, не обладающим хотя бы 4-6 часами в день на анализ, её скорее всего не решить. А ведь хочется чтобы с трудом заработанные деньги, не были за зря съедены инфляцией, хочется обеспечить детям хорошее будущее, а себе достойную старость. Как это сделать, вот в чем основной вопрос….
    Read the rest of this entry »

    Комментарии к записи Инвестиционные портфели ценных бумаг ( теория Марковица ) отключены
  • Мар
    28

    установка ubuntu 10.10 на desktop в vmware

    Filed under: Без рубрики;

    Ролик показывает процесс установки ubuntu 10.10, установка проходит на десктоп в виртуальной машине vmware. Read the rest of this entry »

    Комментарии к записи установка ubuntu 10.10 на desktop в vmware отключены
  • Фев
    26

    Итак, на свой компьютер с Windows 7 установил Ubuntu 10.10, этот linux установил свой загрузчик grub и сделал себя первым при загрузке системы. Ноутбуком пользуется супруга и ей не удобно каждый раз выбирать виндовс при загрузке. Нужно изменить порядок загрузки операционных систем. Как же и где изменить загрузчик ubuntu , чтобы первым грузился Win 7 ? Read the rest of this entry »

    Комментарии к записи Загрузчик grub для windows 7 и ubuntu 10.10 изменяем порядок загрузки отключены