Алгоритмы и структуры данных. Подгруппа 105-1: различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Нет описания правки
Строка 9: Строка 9:


====Домашнее задание (12.01 - 26.01)====
====Домашнее задание (12.01 - 26.01)====
Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами от 0 до 2^32. Числа распределены равномерно. Для первых 6 задач необходимо
Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами. Для первых 6 задач необходимо
* написать алгоритм на любом языке программирования или на псевдокоде,
* написать алгоритм на любом языке программирования или на псевдокоде,
* описать что можно считать наилучшим, средним и худшим случаями,
* описать что можно считать наилучшим и наихудшим случаями,
* для каждого из трёх случаев подсчитать отдельно количество операций сравнения и swap.
* для каждого из двух случаев подсчитать отдельно количество операций сравнения и swap.


=====Задачи=====
=====Задачи=====
# Даны три числа, требуется вернуть наименьшее.
# Даны три числа, требуется вернуть наименьшее.
# Даны три числа, требуется отсортировать их.
# Даны три числа, требуется отсортировать их.
# Дана последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x.
# Дана последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Примечание: если таких значений i несколько, вернуть любое; если ничего не найдено, вернуть -1.
# * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена.
# * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена.
# Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки, который бы учитывал специфику входных данных.
# Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки, который бы учитывал специфику входных данных.
# * Дано 32 битное число, записанное в двоичной системе. Требуется найти максимальный ненулевой бит. При оценке среднего случая постарайтесь примерно предсказать необходимо количество операций.
# * Дано 32 битное число, записанное в двоичной системе. Требуется найти максимальный ненулевой бит. Можно обращаться к i-тому биту и сравнивать биты с нулём. В дополнение к заданиям в преамбуле предскажите количество операций, которые нужно в среднем сделать, считая, что числа распределены равномерно.
# * Даны 32 битные неотрицательные числа m и n в двоичной записи. Требуется вывести True, если m < n, иначе False. Можно обращаться к i-тому биту и сравнивать биты. При оценке среднего случая постарайтесь примерно предсказать необходимо количество операций.
# * Даны 32 битные неотрицательные числа m и n в двоичной записи. Требуется вывести True, если m < n, иначе False. Можно обращаться к i-тому биту и сравнивать биты. В дополнение к заданиям в преамбуле предскажите количество операций, которые нужно в среднем сделать, считая, что числа распределены равномерно.
# Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи. Подсчитайте количество рекурсивных вызовов.
# Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи (как на занятии). Подсчитайте количество рекурсивных вызовов.
#* Напишите функцию, вычисляющую n-ое число Фибоначчи, у которой число операций — полином от n, и которая использует количество памяти, независящее от n.


==Полезные ссылки==
==Полезные ссылки==

Версия от 18:51, 12 января 2015

Материалы к занятиям

В каждом домашнем задании для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками. Решения после установленного дедлайна не принимаются.

Занятие 1 (12.01.15)

  1. Числа Фибоначчи. Определение. Примитивный рекурсивный алгоритм вычисления i-ого числа. Оценка числа операций. Анализ причин неэффективности. Алгоритм с запоминанием вычисленных ранее значений. Оценка числа операций. Сравнение с предыдущим. (подробнее: глава 0, страницы 8-10 из книги <<Алгоритмы>>, см. список рекомендованной литературы)
  2. Задача о ханойской башне. Постановка задачи. Рекурсивный алгоритм. Рекуррентная формула для числа перемещений. Замкнутая формула для числа перемещений (+ доказательство). Доказательство того, что эту задачу нельзя решить используя меньшее число перемещений дисков.
  3. Сортировка пузырьком. Алгоритм. Подсчёт количество операций сравнения и обмена (swap). Анализ наилучшего и наихудшего случаев (Википедия)

Домашнее задание (12.01 - 26.01)

Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами. Для первых 6 задач необходимо

  • написать алгоритм на любом языке программирования или на псевдокоде,
  • описать что можно считать наилучшим и наихудшим случаями,
  • для каждого из двух случаев подсчитать отдельно количество операций сравнения и swap.
Задачи
  1. Даны три числа, требуется вернуть наименьшее.
  2. Даны три числа, требуется отсортировать их.
  3. Дана последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Примечание: если таких значений i несколько, вернуть любое; если ничего не найдено, вернуть -1.
  4. * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена.
  5. Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки, который бы учитывал специфику входных данных.
  6. * Дано 32 битное число, записанное в двоичной системе. Требуется найти максимальный ненулевой бит. Можно обращаться к i-тому биту и сравнивать биты с нулём. В дополнение к заданиям в преамбуле предскажите количество операций, которые нужно в среднем сделать, считая, что числа распределены равномерно.
  7. * Даны 32 битные неотрицательные числа m и n в двоичной записи. Требуется вывести True, если m < n, иначе False. Можно обращаться к i-тому биту и сравнивать биты. В дополнение к заданиям в преамбуле предскажите количество операций, которые нужно в среднем сделать, считая, что числа распределены равномерно.
  8. Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи (как на занятии). Подсчитайте количество рекурсивных вызовов.
    • Напишите функцию, вычисляющую n-ое число Фибоначчи, у которой число операций — полином от n, и которая использует количество памяти, независящее от n.

Полезные ссылки

Источник — https://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных._Подгруппа_105-1&oldid=1192