Практикум на ЭВМ

171 (2015/2016) группа

Максим Журавлев

Студент TODO №1 №2 №3 №4 №5 №6 №7 №8 №9 №10 Тест 1 Тест 2
20 Endian check bitAnd bitXor thirdBits fitsBits sign getByte logicalShift addOK bang conditional isPower2 floatBits1 floatBits2 floatBits3 O(n) vs O(n*log(n)) vs O(n^2) Exploit Связный список Проверка на цикл Hash table Подсчет слов BST strxxx 2 3 1 2 3
Блинов Сергей 20
Волков Григорий
Ирина Лень
Калабкин Евгений
Кантеев Леонид
Кеворкянц Павел
Кострюков Алексей
Костюков Юрий
Лебедев Михаил
Милосердов Владимир
Минаев Александр
Мусатян Сабрина
Поляков Александр
Смрнов Кирилл
Степанова Любовь
Тюляндин Иван
Фадеева Анастасия
Чернов Андрей
Чугаев Анатолий
Шабанов Владимир
Шумилов Пётр

Задачи

Тест 2. 11.12.15
  1. Удалить из входного текста некоторую букву и вывести получившийся текст. Текст и буква вводятся с консоли.

  2. Два неотрицательных числа заданы в двоичной форме в массивах. Элементы обоих массивов — булевые (0, 1). Написать программу, которая определяет, какое число больше.

  3. Вывести на консоль все однострочные комментарии С++ (вида "// комментарий \n") из входного файла (вместе с символами "//"). До комментария в строке может быть значимый текст, его выводить не надо, строки без комментариев не выводить. Конец строки представляется символом \n, могут быть полезны функции fgetc и feof.

Тест 1. 27.11.15
  1. strxxx

    Реализовать функции стандартной библиотеки работы со строками:
    - strlen
    - strcmp
    - strcpy
    - strcat

  2. Подсчитать количество вхождений каждой строки в потоке ввода

  3. Даны 2n+1 строк, из которых одна уникальная, остальные встречаются ровно два раза.
    Найти уникальную строку.
    Подсказка: вспомните работу с битами, одна из операций необходимые свойства.

Домашняя работа 10. 25.11.15
  1. BST

    Реализовать АТД "множество" на основе двоичного дерева поиска. Программа должна позволять в интерактивном режиме добавлять значения целого типа в множество, удалять значения, проверять, принадлежит ли значение множеству, печатать текущие элементы множества в возрастающем и убывающем порядках, а также в формате (a b c), где a — значение в узле, а b и c — аналогичные представления поддеревьев правого и левого потомка. Пример: "(5 (2 null null) (10 null (12 null null)))". Такой вывод бывает крайне полезен при отладке операций над деревом.

Домашняя работа 9. 12.11.15
  1. Hash table

    Реализовать набор функций для работы с hash table: создать (хеш-функция передается как параметр) и удалить таблицу, установить, удалить и извлечь элемент, собрать статистику (количество непустых ячеек, количество элементов, средняя длина цепочки, минимальная ненулевая длина цепочки, максимальная длина цепочки,...)

  2. Подсчет слов

    Подсчитать количество различных слов, использованных в тексте любой достаточно большой классической книги из public domain, и количество использований каждого. Под словом понимается любая последовательность символов ненулевой длины между пробелами(табуляциями, переносами строк,...), очищенная от знаков препинания. Разные словоформы - разные слова. Замерьте и соберите в таблицу время выполнения и статистику, упомянутую в предыдущей задаче, для разных хеш-фунций (заведомо неудачные: константа, сумма символов - и одну из рекомендуемых к практическому использованию)

Домашняя работа 8. 06.11.15
  1. Связный список

    Реализовать набор функций для работы со односвязными списками. К нему сделать интерфейс - консольное приложение, заполняющее список данными пользователя. Команды
    a <число> - добавляет число в список,
    r <число> - удаляет первое число, равное введенному, из списка,
    p - выводит содержимое списка на экран,
    q - выход из программы с очисткой памяти.

  2. Проверка на цикл

    Реализовать функцию, определяющую наличие цикла в данном односвязном списке. Допускается использование фиксированного количества дополнительной памяти. Для тестирования добавить в интерфейс предыдущей программы вызов проверки и создание цикла.

Домашняя работа 7. 26.10.15
  1. Exploit

    Реализовать атаку buffer overflow, написав заведомо небезопасную функцию чтения.
    В коде следующие функции:
    - main,
    - input,
    - other.
    main вызывает input, специально подобранный ввод приводит к вызову other (перезаписан адрес возврата). Other печатает что-нибудь, дабы продемонстрировать, что была вызвана. Корректное продолжение работы не требуется.
    main или input печатают любую необходимую информацию: адреса функций, содержимое стека.
    Совет: считывайте очередной int в массив, используя while(!stop) { <...>; data[i++] = x;}. Это проще, чем scanf("%s", ...).
    Отчетность - код + скриншот.

Домашняя работа 6. 18.10.15
Доклад Алексея Шипилёва о типовых ошибках и лучших практиках измерения производительности. Есть Java специфичные места.
Слайды к докладу (или, возможно, к такому же докладу на другой конференции)
  1. O(n) vs O(n*log(n)) vs O(n^2)

    Реализовать три сортировки (обращаю внимание, на паре было сказано про две): подсчетом, основанную на сравнениях с асимптотической сложностью O(n*log(n)) и основанную на сравнениях с асимптотической сложностью O(n2). Измерить время работы и заполнить таблицу на наборах входных данных разного размера: 5, 10, 100, 1k, 10k, 100k, 1M, 10M, 100M. Допускается значение n/a - не дождались ответа.
    Update:
    В день постановки задачи - 18.10.2015 - динамическое выделение памяти еще не пройдено. Желающим приступить, не дожидаясь пары, искать по ключевым словам malloc / free.

Домашняя работа 5. 18.10.15
Статья с таблицей, упомянутой на прошлой паре
Еще одна статья с таблицей, упомянутой на прошлой паре
  1. Code review

    Проверить код первого задания у одногруппников с позициями в списке группы +5 и +10 относительно вашей. Обсудить замечания тех, кто проверил вас. Улучшить свой код.
    Замечания и ответы высылать письмами. В поле "копия" ящик преподавателя. Не забываем использовать кнопку "Ответить всем".

Домашняя работа 4. 06.10.15
  1. floatBits3

    Вывести битовое представление float, используя приведение указателей

Домашняя работа 3. 06.10.15
  1. floatBits1

    Вывести битовое представление float, используя union и int

  2. floatBits2

    то же, используя union и битовые поля

Домашняя работа 2. 06.10.15
  1. Endian check

    Определить, на какой платформе, запущена программа: little- или big-endian.

  2. bitAnd

    Эта и последующие в соответствие с отосланным файлом

  3. bitXor
  4. thirdBits
  5. fitsBits
  6. sign
  7. getByte
  8. logicalShift
  9. addOK
  10. bang
  11. conditional
  12. isPower2
Домашняя работа 1. 02.10.15
  1. Задачи контрольной

    Реализовать задачи контрольной работы на с учетом сказанного на разборе.
    Первый и последний раз допускается "родной" язык программирования, если он отличается от С, но лучше на С.
    Update:
    Разделения задания на задачи не будет.

© 2014-2018 HwProj