Задачи по многопоточности

Вот еще список задачек на многопоточность
Реализацию предлагаю обсуждать в комментариях

Пинг-понг

Смоделируйте игру “пинг-понг” по следующим упрощенным правилам:

• играют два потока
• игра заключается в том, что один поток посылает сообщение “ Ping ”, а второй отвечает ему “Pong”.
• при этом, пока один делает “Ping”, второй ждет. Как только сообщение послано, первый поток начинает ждать, а второй отсылает “ Pong” и т.д. Фактически они поочередно блокируют друг друга.
• пусть по рандому, в методе, который делает ответ, происходит ошибка. Тогда считаем, что поток, в котором произошла ошибка - пропустил очко.
• это очко начисляем противоположному потоку.
• игра продолжается до тех, пор пока один из потоков не наберет 5 очков. Как только это произошло, игра прерывается и на консоль выводится имя победителя.

Реализация любая. Можно ввести и третий поток – судью. Можно не вводить. Как считаете правильней так и делайте.

Вариант развития - волейбол, потоки сгруппированы по командам, один поток из команды подбирает мяч, производит ряд пасов, в итоге производится "Pong" на команду противника, и т.д.

АТС

Есть АТС и абоненты (потоки), которых АТС обслуживает.Абоненты могут совершать друг другу звонки, при этом, если два абонента разговаривают, то третий, при попытке дозвониться одному из них, должен получить сигнал "занято".
АТС имеет ограниченную пропускную способность линий, т.е. может обслуживать одновременно не более N активных соединений между абонентами.

Далее описана реализация, которая обсуждалась на занятии. Кто-нибудь может сделать альтернативную реализацию.

Каждый абонент является потоком, который при старте подключается к АТС, и ему присваивается номер. Подключение к АТС должно происходить вызовом метода connect или register,  в этом методе ссылка на вызвавший поток должна быть добавлена в список адонентов.
После регистрации абонент засыпает на рандомное время.

По истечении времени поток просыпается и выбирает случайным образом номер абонента для дозвона, количество номеров нужно запрашивать у АТС, исходя из этого количества генерировать номер для дозвона. 
Поток вызывает у АТС метод call, в этом методе проверяется не занят ли принимающий абонент. Если занят возвращается сигнал "занято". (вариант для усложнения - при получении сигнала "занято", звонящий генерирует ожидание на небольшое время, и пытается дозвониться на тот же номер.)
Еще вариант для усложнения - некоторые номера могут быть не закреплены ни за одним потоком, в этом случае потоку нужно вернуть сигнал "номер не обслуживается", и абонент или прекращает дозвон и засыпает, или перегенерирует номер, и продолжает дозвон (на выбор)

Если принимающий абонент зарегистрирован и свободен, то АТС "будит" его, и предлагает принять вызов. (тут тоже можно ввести усложняющую опцию - принимающий может отсутствовать дома, или игнорировать звонящего, эта ситуация может определяться рандомно)

Если принимающий абонент принимает вызов, то звонящий генерирует время разговора, и засыпает на это время, принимающий засыпает на неопределенное время (есть такое негласное правило - первым должен ложить трубку тот кто звонит). После пробуждения, звонящий прекращает звонок (метод endCall у АТС), при этом АТС будит принимающего, и он переходит в основной режим - спячка с таймаутом, по истечении которого абонент совершает звонок.
При завершении звонка АТС вновь может направлять на обоих абонентов входящие звонки.

Упрощенные состояния абонента приведены на диаграмме:

Определение занят ли абонент можно сделать разными способами, например атс может хранить у себя состояние для каждого абонента. Или же это состояние должно храниться как поле объекта потока, и АТС должно запрашивать значение через subscriber.getState()
 

Занятия 13, 14 и 15

Ознакомились с обобщениями в Java - Generics.
Знакомство вышло не полное - только основные вещи, этого должно бвть достаточно для понимания обобщений в коллекциях.
БОлее подробно рекомендую почитать у Хорстманна в главе 12. Вся двенадцатая глава посвящена обобщениям.

Начали знакомство с коллекциями, расмотрели основные методы класса Collection, итераторы.
Читать главу 13 до заголовка "Списки-массивы"

Домашка:
1. Ранее созданные интерфейс SimpleList и класс SimpleArrayList сделать обобщеными.
2. Создать класс SimpleLinkedList реализующий интерфейс SimpleList (требования описаны в итогах занятий 6-9). Класс должен быть обобщенным.
3. Добавить в оба класса-списка итератор.
должен корректно работать следующий код:

SimpleList<String> stringList = new SimpleLinkedList<String>();
list.add("good");
list.add("bad");
list.add("good");
list.add("bad");
list.add("good");
for(String str: stringList){
    if (str.equals("good")) {
        System.out.println("good");
    }
} 

Занятие 12

На двенадцатом занятии изучили механизм обработки исключений
Рассмотрели иерархию классов исключений (Throwable, Error, Exception, RuntimeException), классификацию (checked-unchecked), способы декларирования исключений в методах (throws), генерацию исключений (throw) и их обработку (try-catch-finally).
К сожалению не успели рассмотреть создание собственных классов исключений
К прочтению рекомендуется глава 11 у Хорстманна, или официальный туториал - http://docs.oracle.com/javase/tutorial/essential/exceptions/

Домашка

В ранее реализованных заданиях - "Ханойская башня" и "список-массив/связный список" добавить обработку ошибок при помощи искючений.
Т.к. создание собственных классов исключений еще не рассмотрели, то допускается использование исключений из библиотеки Java SE
Но я все же рекомендую использовать собственные классы исключений.

Самостоятельное изучение

У Хорстманна в главе 11 также рассмотрены диагностические утверждения (assertion), протоколирование при помощи класса java.util.logging.Logger, и приемы отладки приложений
Эти темы мы проходить не будем, я рекомендую изучить их самостоятельно.

Занятия 10-11

На 10 и 11 занятиях рассмотрели

• Enum (перечисления)
• Методы с переменным числом параметров
• Шаблон проектирования Listener (слушатель), также называемый Callback. Рассмотрели пример реализации слушателя из книги Хорстманна.
• Вложенные классы. Статические вложенные классы, доступ к приватным полям внешнего класса из вложенных классов.

К прочтению рекомендуются главы 5 и 6 Хорстманна.
Для самостоятельного изучения оставили рефлексию (описана в главе 5) и программирование графики при помощи пакета Swing (главы 7-8)
К рефлексии мы возможно вернемся, если будет время.

Итоги занятий 6-9

Пройденный материал

Наследование. Суперклассы, подклассы.
Последовательность инициализации классов с учетом конструкторов суперклассов.
Динамическое связывание.
Приведение типов
Абстрактные классы
Глобальный суперкласс Object. Методы equals(), hashCode(), toString()
Интерфейсы
Обобщенные списки-массивы. Интерфейс List, класс ArrayList
Классы оболочки - Integer, Double, Boolean и.т.д.

Домашние задания

1. Выбрать предметную область которая вам хорошо знакома. Выделить несколько классов (3-5, больше не нужно) для построения иерархии суперклассов и подклассов. Определить в классах поля, 5-7, не более. Определить конструкторы.

2. На занятии рассмотрели интерфейс MyComparable, в котором описан метод compareTo(). Метод принимает на вход объект для сравнения.
При вызове  obj1.compareTo(obj2) должен вернуть '-1' если obj1 меньше obj2, '1' - если больше, '0' если объекты эквивалентны.
В одном из своих классов реализовать интерфейс MyComparable, в метод compareTo() включить логику сравнения объектов этого класса. Можно сравнивать по конкретному полю, или по нескольким сразу - на ваше усмотрение.
Реализовать метод для сортировки объектов этого класса с использованием интерфейса MyComparable. Метод сортировки должен принимать на вход массив объектов соответствующих спецификации MyComparable.

Прошу не путать этот интерфейс с java.lang.Comparable, который используется в стандартных сортировщиках.

3. Описать интерфейс SimpleList. Создать собственную реализацию массива-списка SimpleArrayList, соответствующую спецификации SimpleList. SimpleArrayList должен хранить данные внутри в виде примитивного массива, но при этом обеспечивать расширяемость списка. Для SimpleArrayList предусмотреть два конструктора, конструктор по умолчанию должен создавать внутренний массив стандартного размера, например 10, конструктор с параметром должен создавать внутренний массив с размером, который указал пользователь.

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

Методы интерфейса SimpleList:
add(Object) - добавляет объект в конец списка
add(int, Object) - добавляет новый элемент по указанному индексу. При этом не затирая существующий элемент по этому индексу, а сдвигая его и все последующие вправо.
remove(int) - удаляет элемент, находящийся по указанному индексу. При этом все последующие элементы должны сдвигаться влево.
size() - возвращает количество элементов в списке (не путать с размером внутреннего массива)
get(int) - возвращает элемент, находящийся по указанному индексу.
set(int, Object) - заменяет элемент, находящийся по указанному индексу, на переданный объект.
equals(Object) - проверка эквивалентности, сравнивает поэлементно два списка.

Созданный массив должен уметь хранить объекты одного из созданных вами классов. В описанных мной методах Object замените на свой класс.
Все методы доступа и модифицирующие методы должны проверять корректность переданных данных. В случае ошибки, пока используем System.exit(). В дальнейшем научимся использовать исключения.

Требования к домашке

Отныне вводится новое требование к выполняемым заданиям - все классы должны быть описаны в пакетах. Имена пакетов на ваше усмотрение, но желательно придерживаться общих конвенций. Пакеты проходили на 5-м занятии.

Итоги 4 и 5 занятий

На четвертом и пятом занятиях рассмотрены основные принципы ООП.
Детально прошлись по инкапсуляции
Кратко рассмотрели пакеты и путь поиска классов (classpath).

К прочтению рекомендуется вся 4-я глава Хорстманна
В конце этой главы приводится подробная информация по пакетам, classpath, и встроенной возможности документирования - эта часть рекомендуется к самостоятельному изучению.

В качестве примера рассмотрели задачу о Ханойской башне

Для решения задачи логика программы разделена на два модуля - игрок и игра.
Вначале игрок создает новый экземпляр игры с указанием количества дисков в башне.
Игра предоставляет игроку возможность переместить диск с одного стержня на другой - метод move(), в аргументы которого передается имя диска-источника, и имя диска назначения.
Игрок, выполняя последовательные вызовы метода move(), перемещает башню с водного стержня на другой.

На занятии рассмотрели реализацию игры - класс Tower

Домашнее задание

Расширить логику класса Tower. Реализовать проверку правил игры - больший диск нельзя класть на меньший, с пустого стержня нельзя пытаться снять диск.
При попытке пользователя выполнить неправильное действие, нужно вывести на экран сообщение об ошибке.

Так как для реализации этой логики потребуется производить множество одинаковых проверок для каждого стержня, то следует всю логику, относящуюся к стержню, вынести в отдельный класс - Rod.
Стержень предоставляет для игры возможность поместить на стержень диск, и снять диск со стержня. Соответственно - метод putDisc, в аргумент метода передается размер диска, и takeOffDisc - не принимает аргументов, возвращает размер снятого диска.
При инициализации, игра создает три экземпляра класса Rod, и один из них наполняет дисками.
При вызове игроком метода move, игра должна снять диск с одного стержня и поместить его на другой.

Диаграмма классов:

Как вариант - реализовать в методах putDisc и takeOffDisc возврат кода ошибки, в случае неудачного помещения или снятия диска.

Реализовать логику игрока - запросить у пользователя высоту башни, и вывести трассировку решения задачи для указанной высоты.

Регулярные выражения

Я рекомендую самостоятельно разобраться с регулярными варыжениями. Не обязательно выучивать наизусть все подстановочные символы, достаточно понять основные принципы.

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

Помимо Хорстманна есть еще оффициальный туториал - Regular Expressions (англ.)
Вся справочная информация по классам пакета java.util.regex - http://docs.oracle.com/javase/7/docs/api/java/util/regex/package-summary.html
Например - класс Pattern с описанием всех подстановочных символов.

Дискретная математика

Для желающих параллельно изучить дискретку рекомендую книжку Андерсона - "Дискретная математика и комбинаторика"

Андерсон, Джеймс А. Дискретная математика и комбинаторика. 2004 год. 960 стр. 8.1 Мб.
Книга представляет собой современный учебник по дискретной математике. Кроме таких разделов, как математическая логика, теория множеств, комбинаторика, теория графов, теория алгоритмов и вычислений, традиционно включаемых в основной курс дискретной математики, она содержит обширные сведения по теории вероятностей, алгебре и теории чисел. Особое внимание уделено теории доказательств. Чтение книги требует некоторой математической культуры, хотя для изучения основных глав достаточно знаний по математике в объеме средней школы. Материал сопровождается многочисленными примерами, в конце каждого раздела приводится большое количество упражнений. Книга адресована в первую очередь преподавателям и студентам технических специальностей. Она будет также полезна тем, кто интересуется дискретной математикой и желает изучить ее самостоятельно.

Скачать

Требования к выполнению домашек

Выполненные задания можете присылать мне на почту для проверки.

Первые задания могут быть реализованы одним классом, в одном методе, поэтому текст программы можно вставлять в тело письма. Программы со множеством классов следует паковать в архив.

Если вы вставляете в текст письма часть или полный текст программы, то позаботьтесь о форматировании, куски программ следует оформлять моноширным шрифтом (например Courier New или Consolas). Для удобства копирования и вставки кусков кода можно использовать плагин к IDEA - 'Copy' on steroids

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

Также прошу перед отсылкой убирать из текста закомментированные куски кода.

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

Итоги первых трех занятий

Темы, рассмотренные на первых трех занятиях

Установка JDK и IntelliJ IDEA
Примитивные типы данных
Операции
Массивы
Блоки операций
Условные операторы if...else, if...else...if, switch
Циклы while, do...while, for, foreach
Ввод-вывод

Рекомендуется к прочтению 1-3 главы Хорстманна.
Все дальнейшие отсылки на Хорстманна будут относиться к 9-му изданию 2014 года.

Домашка

1. Генератор простых чисел.

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

2. Детектор палиндромов.

   Программа запрашивает у пользователя слово или выражение. Если введенное слово или выражение является палиндромом, то программа выводит "это палиндром", в противном случае "это не палиндром"
   
   После проверки палиндрома программа должна запрашивать от пользователя новый палиндром, и так пока пользователь не введет exit.

3. Текстовый фильтр.

   Программа принимает на вход слово-фильтр, и путь к текстовому файлу, который требуется отфильтровать. (Входные данные можно передавать как параметры командной строки, описано у Хорстманна на стр. 120, или запрашивать у пользователя в интерактивном режиме через сканнер)
   Программа построчно читает файл, проверяет есть ли в строке слово-фольтр, если есть - программа выводит строку на экран, иначе программа переходит к следующей строке.

4. Сортировка текстового файла

   Программа принимает на вход путь к файлу содержимое которого нужно отсортировать. (как параметр командной строки, или через сканнер)
   
   Программа сравнивает все прочитанные из файла строки и выводит их на экран в отсортированном в алфавитном порядке виде.
   
   Следует использовать небольшие файлы, на несколько десятков строк.

5. Калькулятор

   Программа запрашивает у пользователя простое математическое выражение, вычисляет выражение, выводит результат.
   
   По желанию реализовать один из вариантов.
   
   Попроще - программа запрашивает по очереди первый операнд, второй операнд и операцию.
   
   Посложнее - выражение с двумя операндами вводится одной строкой в традиционном виде, например 2 + 2 (операторы и операнд отделяются пробелом).
   
   Следует обрабатывать ввод нечисловых значений, и запрашивать повторный ввод.

Для некоторых заданий протребуются функции работы со строками, сравнение, проверка вхождения подстроки и т.п. Об этом нужно почитать у Хорстманна на стр. 77-83

Возникшие вопросы присылайте на мою почту или оставляйте здесь в комментариях

UPD.
Инициализация Scanner для чтения файла, и PrintStream для записи в файл может быть еще проще:

Scanner fileIn = new Scanner(new File("c:\\filein.txt"));
PrintStream fileOut = new PrintStream("c:\\fileout.txt");

Не забываем про throws IOException при работе с файлами

public static void main(String[] args) throws IOException {

И не забываем импортировать классы:

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

Июнь 2014, Начинаем курс по Java Elementary

Рекомендуемая литература:

Java 2. Кей Хорстманн, Гари Корнелл. 8-е (том 1) или 9-е издание (том 1, том 2).
Core Java. Cay S. Horstmann, Gary Cornell. 8-th (vol.1, vol.2) or 9-th edition.

Философия Java. Брюс Эккель. 4-е издание
Thinking in Java. Bruce Eckel. 4-th edition

Java 2. Наиболее полное руководство. Герберт Шилдт 7-е издание, 8-е издание,

Документация:

The Java™ Tutorials

• Getting started - установка, настройка, первая программа
• Learning The Java Language - описание языка

Java API - http://docs.oracle.com/javase/7/docs/api/